Computer Science 477/677
Design and Analysis of Algorithms
Spring 2004
Assignments

Revised May 17, 2004

Tuesday, January 20, 2004

I will assume that you are familiar with the material in Chapter 1 of your textbook.. You should be, if you've learned the material in the prerequisite courses. Yet, I will still spend some time today going over some of the more difficult topics in that Chapter.

Also today, we will discuss efficiency of algorithms. Read Sections 2.1 through 2.6 of your textbook, pages 57-67, before class.

Thursday, January 22, 2004

Today, we will continue our discussion of efficiency of algorithms, with an emphasis on timing analysis.

Tuesday, January 27, 2004

Turn in Assignment 1 at the beginning of class today.

Today we will discuss several of the topics in Chapter 4, pages 98-146 in your textbook.

The most difficult topic we will discuss is amortized complexity, which is in Section 4.6. I plan to spend most of the time discussing recurrences, introduced in Section 4.7.

Thursday, January 29, 2004

Today we will continue the discussion of recurrences.

Tuesday, February 3, 2004

Today we will continue the discussion of recurrences.

Thursday, February 5, 2004

Turn in Assignment 2 at the beginning of class today.

Today we will continue the discussion of recurrences. I will prove the master theorem today.

If time permits, we will discuss amortized analysis.

Tuesday, February 10, 2004

Today we will discuss sorting and searching.

Thursday, February 12, 2004

Today we will continue our discussion of sorting algorithms.

Tuesday, February 17, 2004

Today we will continue our discussion of sorting algorithms.

Thursday, February 19, 2004

Today we will try to finish our discussion of sorting algorithms.

Tuesday, February 24, 2004

First Examination today. Read the study guide.

Thursday, February 26, 2004

Today we will begin the discussion of priority queues and search structures.

Tuesday, March 2, 2004

I will hand back the exam today.

Today we will continue the discussion of priority queues and search structures.

Thursday, March 4, 2004

We will continue the discussion of priority queues and search structures.

Tuesday, March 9, 2004

Today I will introduce the rather large subject of graph algorithms, and data structures which implement graphs. Read Section 5.4 of your textbook.

Thursday, March 11, 2004

Turn in Assignment 3 at the beginning of class today.

Read Chapter 5 (pages 147-186) before March 16, except for Section 5.8.

Tuesday, March 16, 2004

Today we will continue the discussion of graphs and graph algorithms.

Thursday, March 18, 2004

Tuesday, March 23, 2004

Thursday, March 25, 2004

Turn in Assignment 4 at the beginning of class today.

We will continue our discussion of minimum path problems, including finishing the discussion of Floyd's algorithm.

Tuesday, March 30, 2004

Second Examination today. Read the study guide.

The exam will contain graph algorithm questions.

If a question that you see on one of these old exams is not related to anything we've covered in class so far this semester, then don't worry: it will not be on our March 30 exam.

Spring 1999: First Examination

Spring 1999: Second Examination

Spring 1999: Final Examination

Spring 2001: First Examination

Spring 2001: Second Examination

Spring 2001: Final Examination

Fall 2002: First Examination

Fall 2002: Second Examination

Fall 2002: Final Examination

Wednesday, March 31, 2004

The exams are graded now. The total possible was 145 points.

Thursday, April 1, 2004

I will hand back the graded examination today.

Tuesday, April 13, 2004

Today I will introduce the concept of dynamic programming. This is a technique whose name (I was told, so I am really not sure) was chosen for political reasons, and gives no clue as to what the method really is about. Read Chapter 8 of your textbook.

We have already done some dynamic programming. The linear time algorithm for finding the sublist of maximum sum that we did in class at the beginning of the semester uses dynamic programming. Dijkstra's algorithm is not exactly a form of dynamic programming, but uses similar concepts.

Many experienced programmers (I am absolutely stunned by the number) claim to have never heard of dynamic programming. But some of them use it anyway, as it is really a "natural" method that a clever programmer could come up with on his own. However, many never do.

It is difficult to overestimate the practical importance of dynamic programming. The need for it occurs constantly in real-life applications, and those who don't use it sometimes write programs whose time complexity is greater than necessary, by a truly staggering amount.

Thursday, April 15, 2004

I am in my office now, at Thu Apr 15 10:18:46 PDT 2004.

Today we will continue the discussion of dynamic programming.

Tuesday, April 20, 2004

Today we will continue our discussion of dynamic programming.

If you want to compute the product of a list of numbers (such as 3*5*22344*113402*12) does it matter in what order you do the multiplcation? (Assume that you are using the multiplication algorithm you learned in elementary school, whose time complexity for multiplying N by M is O(log(N)log(M)).

Thursday, April 22, 2004

Turn in Assignment 5 at the beginning of class today.

Today, I will discuss backtracking. We will give Graham's Scan as an example of a backtracking algorithm.

If time permits, I will introduce the concept of a greedy algorithm. Examples of greedy algorithms that we have already done include Prim's algorithm and Kruskal's algorithm. Another example that we will introduce will be Huffman's algorithm for optimal prefix coding.

Tuesday, April 27, 2004

Just a reminder: I now delete all email messages, without reading them, unless I know exactly who they are from. So, please use your real name and be sure to write "CSC 477" or "677" in the subject heading.

Today we will cover the subject of NP-completeness and NP-hardness. (This will be done differently and with less rigor than in 456/656.)

Everybody's heard of the concept, but few can define it. Can you?

I will introduce the concept of parallel algorithms today if we have time. How much time does it take to find the maximum of n numbers if n processors are working on the problem simultaneously?

Thursday, April 29, 2004

Turn in Assignment 6 at the beginning of class today.

Tuesday, May 4, 2004

Today and Thursday we will introduce some new material and clean up some previously overlooked topics.

A linear time algorithm for finding the median. (Using this algorithm to choose the cut value, quicksort runs in Theta(n log n) time. But you'd never use it that way.)

Dynamic data structures. The simplest example is a linked list with "move-to-front."

We have already discussed balancing schemes for binary search trees that guarantee that the height is always Theta(log n).

A more complex example, but with the same spirit as the move-to-front scheme for lists, is thesplay tree.

Thursday, May 6, 2004

Tuesday, May 11, 2004

Final Examination: 6:00-8:00

challenge problems are absolutely due today.

Read the study guide.

Monday, May 17, 2004

The final grades are now finished.