EECS 586, Design and Analysis of Algorithms

Audience

In decreasing order of frequency, historically the students in this class have been

Gradute students in Computer Science and Engineering: For these students, this class can satisfy the Theory distributional requirements for the MS and PhD degrees, and helps satisfy the 500-level course requirements.
Graduate students from other disciplines: For these students, this class can satisfy cognate requirements, and it can satisfy computer science requirements for students in the scientific computing program administered through LaSC (Laboratory for Scientific Computing). If you are interested in this program feel free to talk with me about it.
Undergraduate students: For CSE undergraduates it can satisfy computer-oriented technical elective requirements, and can be used to satisfy theory requirements (though this is not recommended unless you are good and you should talk to me before you try this). Students in other majors might also take it, though this is quite rare.

Most of the students enrolled are in the first category. For all students, the course can satisfy that burning desire to learn more about algorithms and computer science.

This is a core graduate computer science course, both here and elsewhere, and I make an attempt to show how algorithms relate to a wide range of software and hardware concerns. You'll find that the material is useful in other courses, in research, and in software projects outside the university. In some cases you'll use specific algorithms from class, while in many other situations you'll need to design a new algorithm using the techniques taught in the class.

Content

We will cover the design and analysis of efficient algorithms to solve fundamental computational problems in searching, sorting, graph theory, geometry, optimization, and decision theory. We cover a variety of algorithmic design principles, such as greedy algorithms, divide-and-conquer, and dynamic programming. We also cover the ways in which one analyzes the efficiency of algorithms, through the use of "generalized O-notation" for worst-case, expected-case, and competitive analyses, and some techniques for proving that an algorithm is an optimal solution to a problem.

Prerequisites

You should be able to program well in some standard procedural language such as C, C++, Fortran, or Java, had experience in data structures at least equivalent to EECS 280, and preferably had at least one class that used 280 as a prerequisite. In class we'll use pseudo-code, so the computer language you've used is not critical.

In terms of mathematical background, you should have had least EECS 203 or its equivalent and done well in it. Any additional upper level courses in theoretical computer science, logic, or discrete mathematics in which you had to do proofs will be helpful. In addition to discrete mathematics we will also make use of calculus and basic probability theory.

Texts

Introduction to Algorithms by Corman, Leiserson, Rivest and Stein. Most of the course will be based on this book.
Computers and Intractability by Garey and Johnson. This will be used near the end of the course.

There will also be additional handouts as the course progresses.

Work required

You will have several homework assignments, each with a few problems. You will generally be given 1 week in which to answer them. There are no tests, because I am most concerned with how well you can solve a problem if you have sufficient time to think about it, rather than what you can do in just a few minutes.

Because course grades are based solely on the homeworks and class participation, all homework must be your own work. For the assigned problems are not allowed to work with anyone else, nor search the literature. You may ask the help of the GSI, professor, or of your classmates in understanding the material, and in understanding the questions asked, but you may not ask (or give) help in how to actually do the assigned problems. For anything that is not an assigned homework problem you are allowed (and encouraged) to talk with others. For example, you may want to get together with others to solve some of the unassigned problems in the book.

All assignments are due at the beginning of class on the day assigned. If you are not able to attend class on that day, you may turn the assignment in to the professor or GSI earlier in the day. During class we will go over the assignment, so that you have immediate feedback on how to solve the problems. This is done by selecting volunteers to present their solution.

Grading

All grading is relative. Historically there are few A+ grades each year, and few grades below B. The most common grades are A- and B+, and the median tends to be near the boundary between these grades. The professor assigns course grades, but the GSI and/or grader do all of the grading of the individual assignments. If you have a question about the grade on a particular problem, see the GSI or grader. Requests for regrading must come within 1 week of when the assignment was returned, and need to be accompanied by a short explanation of why a regrade is being requested.

Homework Assignments

Course Material

Extra Credit Problems

These are quite difficult, and rarely recieve partial credit, so attempt them only after you have solved the homework assignments.

A dynamic resource location problem.

Happy Hour

Students in this class are invited to the Computer Science and Engineering Graduate student (CSEG) happy hour. It starts at 4:30pm Fridays in 2817 CSE. This is a good place to meet other students and faculty in a more friendly social setting, with free food and refreshments.