• The class will focus on examples that develop skills at broadly applicable techniques: amortized analysis, randomized algorithms, greedy strategies, dynamic programming, divide-and-conquer, solving a problem by reduction, NP-completeness proofs, approximation algorithms, and advanced data structures. Even though you may have studied some of these techniques in CS320 and CS420, we will look at more sophisticated and beautiful applications of them than you have seen.

Prerequisites:

The official prerequisites for this course are a grade of 'C' or better in an undergraduate algorithms course, and graduate-student status in the Computer Science Department. However, I often let in undergraduate students and people from other departments who have met the prerequisite or who can demonstrate that they have picked up an equivalent background. See me after class if you would like to discuss whether an override is appropriate.

Student Responsibilities:

We encourage you to talk with other students about your assignments and questions, but make sure you complete your homework assignments independently.

Grading

Thirty percent will consist of your midterm grade, forty percent will consist of your final exam grade, and thirty percent will consist of the average of your lab (homework) grades. Because I post solutions, I don't accept late homeworks, so to get you out of any unforeseen mishaps, I will throw out your lowest homework grade in computing the homework average. Even if you give me a legitimate reason for turning it in late, I will tell you to use this "freebie."

The thrust of the course is to give you practice at coming up with the insights that allow you to develop an algorithm or programming approach to a problem. The problems I give on homeworks range from extremely easy to extremely hard. A common misconception is that I expect you to solve all of them successfully. You should view each problem as an opportunity to explore a topic, try to come up with your own ideas, and score some points if you're successful at finding a solution. This partially simulates the experience of doing research in the topic. They are not intended to be stressful, and you should try to have fun with them. If you can engage your curiosity, you will be more likely to ask yourself questions that will lead you to a solution.

Homework and exam scores are curved to give a distribution of grades that is consistent with those in other graduate classes at CSU.

Because answers will involve proofs and require detailed study to for me to critique and grade them effectively, I will choose a subset of assigned homework problems to grade on each assignment. I will announce the subset after they are turned in. The subset will always consist of a mixture of easy, medium, and hard problems.