CSCI 256 - Spring 2025

Algorithm Design and Analysis

Home | Lectures | Problem Sets | Handouts | CS@Williams

Home

Course Description

This course is about mathematical modeling of computational problems, developing common algorithmic techniques to solve them, and about analyzing the correctness and running time of the algorithms. By clearly formulating and carefully analyzing the structure of a problem, it is often possible to dramatically decrease the computational resources needed to solve it. In addition, by analyzing algorithms you can provide provable guarantees of their performance. We will study several algorithm design strategies that build on data structures and programming techniques introduced in CS 136 and mathematical tools introduced in MATH 200. The course will roughly cover the following topics in order: graph algorithms, greedy algorithms, divide-and-conquer, dynamic programming, NP completeness and problem reductions, approximation algorithms and randomized algorithms. At the end of the course, the students should be able to:

• Analyze worst-case running time and space usage of algorithms using asymptotic analysis.
• Formulate real-world optimization problems mathematically (using concepts like sets and graphs) and apply algorithmic paradigms such as divide-and-conquer and dynamic programming to solve them.
• Identify and prove that certain computational problems are NP-hard or NP-complete, that is, show that they are unlikely to admit an efficient solution.
• Design and analyze simple randomized algorithms for computational problems.

Readings

The primary text for the course is Algorithm Design by Jon Kleinberg and Éva Tardos, Addison-Wesley 2006. There will be secondary, optional readings from the Algorithms textbook by Jeff Erickson freely available online.

Course Requirements, Evaluation and Grading

Students will be evaluated based upon their overall performance in the course, according to the table above. Exams and problem sets will be graded on the correctness, clarity, thoroughness, and appropriateness of responses.

Daily Homeworks. Each lecture there will be a homework released (on paper) for students to complete by the next lecture. They will also be released on the Glow page for the course. These homeworks are intended to practice the basics of the topics covered in class, such as how algorithms work on particular inputs. They should be done entirely individually. Answers to each homework will be posted after the homework is due.

Problem Sets. Much of the learning in this course happens through practice on new and sometimes challenging problems. Weekly problem sets will be assigned to be completed in pairs. The released assignments, along with the corresponding due dates, are listed on the Problem Sets page. There is also a handout giving some tips on how assignments will be graded, both for proof correctness and for correct latex usage.

Midterms and Final Exam. All exams in this course will be in-person. Midterms will be during your normally scheduled class time. The first midterm exam will be on March 10, and the second will be on April 24. The final exam will be in the assigned slot during finals period.

Special Accommodations

Students with disabilities of any kind who may need accommodations for this course are encouraged to contact Katy Evans (Interim Director of Accessible Education) at 597-4672. Also, students experiencing mental or physical health challenges that are significantly affecting their academic work or well-being are encouraged to contact me and to speak with a dean so we can help you find the right resources. The deans can be reached at 597-4171. If you need accommodations for religious observances, you are encouraged to reach out to me. However, last-minute requests are unlikely to be granted.

Computer Science Honor Code

The Honor Code as it applies to non-programming assignments is outlined here (see the section Avoiding Violations). Further information is also given in the syllabus.

Computer Ethics

Students should be aware of and abide by the College's statement on Computer Ethics. Violations including uninvited access to private information and malicious tampering or theft of computer equipment or software are subject to disciplinary action.