May 31, 2006
the correction of the test
There is a mistake in the test. Question 5 is about quick sort, not binary search. I will see if I can make the change before the test is distributed. sorry about that.
Exam 1 Study GuideHere is the list of things to study for the midterm exam:
- Understand the concepts from the homeworks
- Go through the lecture notes to find emphasized topics - make sure you understand those topics
- Be prepared to discuss what you learned about efficient programming from the projects (and don't worry about phylogenetics specific questions, there aren't any)
- NP-completeness: how to prove it and what does it mean
- big-O, big-Theta and big-Omega, and how they relate to one another
- parts of a greedy algorithm
- greedy algorithms for minimum spanning trees, sorting, and knapsack loads and how they work
- Equation 7.1 (The "Master Theorem" - pp 223-224)
- parts of a divide and conquer algorithm
- binary search
- quicksort, the pivot selection problem and worst-case behavior of quicksort
- solving non-homogeneous recurrence relations
- performing the change of variables operation on recurrence relations
- dynamic programming
- principle of optimality
Understand that this is a superset of the subjects on the exam, as it is basically just straight from the schedule. So not everything listed will be on the exam, but if you study everything listed, it will help you to be well prepared for the exam.
There was a miscommunication in the CS office and the test got into the testing center a little late. The testing center will have the test available tomorrow, but not exactly when it opens. sorry about the inconvenience.
1. Section 3.2, first question, on page 10 of the Recurrence Relations notes
2. Consider figure 8.4 for filling a knapsack using dynamic programming. Let's use a new set of objects whose weights are 1, 2, and 4 units, and whose values are 1, 7, and 15, respectively. If we can carry a maximum of 12 units of weight, construct a new table like 8.4 to determine the optimal load in a knapsack (using DP) with these objects. Analyze the new table to determine which objects will be included in the optimal load.
3. 8.13 (on extracting equivalent optimal solutions to 0/1 knapsack from the DP table)
4. 8.17 page 279
Due Friday, June 2.
May 30, 2006
Homework keys 4, 5, 6, and 7
May 27, 2006
Update on Project 3
For those who are experiencing a problem with two layer 5s in problem 1, core 2, here is an updated version of the database with the layers renumbered properly.
You can also just make it so that when you see a duplicate layer number, you always go with the last duplicate you saw - in this instance the limestone would end up being layer 5, and the sandstone layer 5 would be thrown away. I think that's what the professors ended up going with last semester.
Good luck, and also, since Monday is a university holiday, I don't think it counts as a late day (as the TMCB is completely closed).
May 24, 2006
Homework #7 due Friday, May 26
Homework problems from the recurrence relations handout - all the problems from both parts 1 and 2 (parts 1.2 and 2.3 respectively).
May 19, 2006
TA Hours for Friday
Since I'm going to be doing the class today (Friday), I won't be holding my regular hours. If you weren't planning on coming, but have questions about project 2, I suggest you come to class, as we will spend some time discussing it. See you there.
May 17, 2006
no homework today and friday
No homework today and friday. Good luck on your project.
May 15, 2006
Homework #7: Due Wed May 17 (More intense)
7.10 (write down how you became convinced)
7.12 (be sure that your proof of the correct big-O bound is solid)
May 12, 2006
1. Problem 6.18
1. Problem 7.2
2. Problem 7.7
3. Use equation 7.1 to give a bound on the running time of a divide and conquer algorithm that splits a problem into pieces that are 1/5 the size of the original problem, solves 4 of the pieces and requires ?(n^2) to recombine subproblems at each level. Suppose that you could recombine the subproblems using an ?(n) algorithm if you solved all 5 subproblems rather than only 4. Which algorithm has a better bound?
Due Monday, May 15
May 10, 2006
Homework 3 key
Homework 3 RTF
May 09, 2006
Question 1 Simulate each step of Dijkstra's algorithm, and turn in a table similar to the table in the middle of page 199, on the following directed graph consisting of 5 vertices labeled 1,2,3,4,5 and the following 5 edges
1 to 2 is connected by an edge with cost 6
1 to 3 is connected by an edge with cost 4
2 to 4 is connected by an edge with cost 3
1 to 4 is connected by an edge with cost 9
1 to 5 is connected by an edge with cost 20
4 to 5 is connected by an edge with cost 6
Question 2 Implementing Dijkstra's algorithm requires finding the smallest element in a set (line 8 of pseudocode on page 199) and removing an element from a set (line 9). Discuss the datastructures and algorithms that you might use to implement these operations in the intelligent scissors project. In your discussion, address the efficiency implications of your decisions.
due Friday, May 10.
May 08, 2006
New Description of project 1
The following link gives the new project description. It is just a subset of the original description. It takes off the things you don't need to do.
1. Problem 6.1 page 214
2. how that the greedy algorithm for making change in Section 6.1 will or will not always make correct change for the Nephite coinage system given in Alma 11.
3. get really comfortable with VS 2005.
i. Read through the highlights of set of documents linked from this page at MSDN: Introduction to C#
ii. Work through this "Hello, World" example at MSDN: Hello, World
iii. Extend your "Hello, World" example:
For this assignment, please simply submit a screenshot of your final sorting GUI and indicate which sorting algorithm you implemented.
Read sections 6.3 and 6.4 on Spanning Trees and Shortest Paths.
due Wed, May 10.
May 05, 2006
Consider the following algorithm for getting a drink of water in an apartment in which n roomates share n cups.
Procedure get-drink (dirty: int, clean: int, n:int)
if (clean = 0) then
for (j = 1 to n) do wash-cup(j);
dirty = 0;
clean = n;
return (dirty+1, clean-1,n)
Question 1 Suppose that rather than using the get-drink algorithm above, the roomates decided to implement a "you use it, then you wash it" policy instead. Under policy, one would get a drink of water then immediately wash the cup so that all cups were clean at all times. Compare and contrast the amount of time required to get a drink of water under both policies. How does this related to the design of algorithms and data structures?
Question 2 Problem 4.19 page 142
Question 3 Problem 12.35
Question 4 problem 12.49
due Monday, May 8.
May 04, 2006
Ryan's TA Hours
My hours will be as follows:
Monday from 4 to 7 P.M.
Tuesday from 2 to 5 P.M.
Wednesday from 4 to 7 P.M.
Thursday from 3 to 5 P.M.
Friday from 12 to 2 P.M.
I may be available earlier than 3 on Thursdays (hopefully not any later than 3 though). This schedule is tentative, so it may change during the course of the term. Also, I have a wedding to go to tomorrow so I will not be here. If there are any questions about the homework due tomorrow, you can email me (see the syllabus for my address) and I will try to answer your questions.
May 03, 2006
Homework is 1.21, 2.2, 2.3, 2.4, 3.5, 3.20
Due Friday, May 5.