Since their invention, computers have been used to solve problems more efficiently than can be achieved by hand due to their ability to execute a sequence of instructions (an algorithm) with blazing speed. In this course, we will focus on problems so difficult that even the incredible speeds at which computers can perform basic instructions are not sufficient to achieve the desired performance. For these problems, it is also crucial that we find the right set of instructions — the right algorithm — to execute.
Some introductions to algorithms treat the subject like a trip to a museum, where you see a number of famous algorithms, learning about them and their history. That is not the plan for this course. Instead, the goal of this course is to teach you techniques that you can use in practice to solve algorithmic problems of the types that you are most likely encounter.
In particular, we will discuss algorithm design and modeling techniques. The former are approaches that you can use to design new algorithms. The particular approaches that we will discuss are
Finally, we will discuss some issues of computational compexity. In particular, we will discuss what it means for an algorithm to be "efficient", and we will look at an important class of problems, the NP-complete problems, for which we do not believe there are efficient algorithms. For those problems (and some others), we will consider algorithms that are not efficient in this sense but are still quite useful in practice for solving them when they arise.
The class meets three times a week for lectures. The lectures may be a combination of powerpoint and whiteboard. Lecture notes will be made available online whenever possible, but they are sometimes brief and insufficient to learn the material. The lesson is: do not miss classes, and do take notes.
There will be several homework assignments, half done on paper and half involving programming. See the homework page for details on each assignment. It will be updated during the course as new assignments are made available. All due dates are also shown on the course calendar.
The course will have a final exam but no midterm. See the exams page for more information about the exam, later in the quarter.
Course grades will be set based on performance on the homework assignments and final exam using the following weighting:
| 25% | written assignments |
| 50% | coding assignments |
| 25% | final exam |
The coding assignments are given the most weight since they focus on those skills that are most important to the course goals, namely, teaching you how to apply the design and modeling techniques that we discuss in order to implement new algorithms for problems that arise in practice.
The required textbook for this course is
If you would like a different presentation of some of the ideas in Algorithm Design, another good book to look at is Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. That book is likewise a useful reference. (See also the video lectures mentioned below.)
Some of the topics discussed may not be covered in the textbook. For the more advanced ideas mentioned, the most likely sources for the material are
Tim Roughgarden's video lectures on algorithms are available on youtube. These cover a good fraction of what we will discuss in the course and are definitely worth a look if you prefer videos to textbook reading.
Homework assignments may be turned in late, but there will be a 10 percent penalty for each late day. We understand that emergencies do arise, however, so each student is allowed a total of three free late days (each giving an additional 24 hours) to use during the quarter with no penalty. Once you use up your late days, no additional extensions are granted for any reason! Late days are a safety net in case of a true emergency, not as a convenience. You should plan to use no late days during the entire quarter so that they remain available in case of emergency.
Programming is a necessary and important part of this course. We will assume familiarity with Java and with all of the material from CSE 371 (a prerequisite for this course), especially:
This course website will be used extensively to provide you with course information, such as the schedule mentioned above, homework assignments, and many other things. There is a also discussion board that everyone should use to keep in touch outside of class. Please see the main webpage of the course for details.
You are encouraged to discuss the content of this course with anyone you like; however, unless otherwise stated, each homework assignment is to be done individually. In particular, the solution that you submit for each assignment must be solely your own.
Read through our academic integrity policy for a more detailed discussion. You are responsible for knowing the information in that document.
Any attempt to misrepresent the work you submit will be dealt with via the appropriate University mechanisms, and your instructor will make every attempt to ensure the harshest allowable penalty.
Some excerpts from the campus policies. Take them seriously: "You must use all UW [computing] resources in strict accordance with local, state, and federal laws. These laws cover such areas as illegal access to computer systems, networks, and files; copyright violations; and harassment issues... Software and information resources provided through the university for use by faculty, staff, and students may be used on computing equipment only as specified in the various software licenses. Unauthorized use of software, images, or files is regarded as a serious matter and any such use is without the consent of the University of Washington...If abuse of computer software, images, or files occurs, those responsible for such abuse will be held legally accountable."