General Information | Course Description | Course Material Copyright | Course Conduct | Accommodations
General Information
Lectures: MWF 9:05am–9:55am, Ives Hall G01, mapInstructors:
- Bobby Kleinberg, Gates Hall 317, email
Office Hour: Fridays, 10am - Sasha Golovnev, Gates Hall 307,
email
Office Hour: Thursdays, 10am
Course Description
This course develops techniques used in the design and analysis of algorithms, with an emphasis on problems arising in computing applications. Example applications are drawn from systems and networks, artificial intelligence, computer vision, data mining, and computational biology. This course covers four major algorithm design techniques (greedy algorithms, divide and conquer, dynamic programming, and network flow), computability theory focusing on undecidability, computational complexity focusing on NP-completeness, and algorithmic techniques for intractable problems, including identification of structured special cases, approximation algorithms, and local search heuristics. This course continues to build on work in previous courses on proof writing and asymptotic running time analysis of algorithms.
Learning Objectives
On completing this course, students should be able to:
- Identify problems solvable with a greedy algorithm, design and prove the correctness of such an algorithm, and supply asymptotic running time for a variety of given algorithms.
- Recognize problems to which divide and conquer or dynamic programming approaches may apply, design algorithms with these approaches, and analyze their computational efficiency;
- Reduce resource management as well as partition problems to network flow or cut problems, implement correct strategies for finding optimal flows/cuts, and understand the properties of these strategies;
- Apply randomization to produce tractable algorithms for several specific computationally challenging problems;
- Recognize whether or not certain problems are computationally intractible (e.g. NP-Hard, undecidable), and use reductions from known problems to establish intractability;
- Use approximation algorithms to efficiently produce near-optimal solutions for intractable problems, and bound how close these algorithms are to being optimal;
- Be able to recognize, implement, and understand the properties of several famous and important algorithms including
- Gale-Shapley method for stable matchings,
- Prim's and Kruskal's algorithms for finding minimum spanning trees,
- Bellman-Ford's algorithm for finding shortest paths in a graph, and
- Ford-Fulkerson's algorithm for finding max flows in networks.
Course Material
The textbook for the course is Algorithm Design by Jon Kleinberg and Éva Tardos (available at Cornell Store). Although this book was designed for this course, there will be topics covered in lecture that are not in the text and there will be topics in the text that are not covered in lecture. You are responsible for topics covered in lecture and for any assigned reading in the text.
The following books are also useful references.
- T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms.
- S. Dasgupta, C. Papadimitriou, and U. Vazirani.Algorithms.
- A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of Computer Algorithms.
- M. Garey and D. Johnson. Computers and Intractability.
- D. Kozen. The Design and Analysis of Algorithms.
Prerequisites
The prerequisites for CS 4820 are, either having an A– or better in both CS 2800 and CS 2110, or having successfully completed all three of CS 2800, CS 2110, and CS 3110. Students in CS 5820 should have completed coursework in their undergraduate program covering the same topics. We assume that everyone is familiar with the material in CS 2110, CS 3110, and CS 2800, and we will use it as necessary in CS 4820/5820. This includes elementary data structures, probability (conditional probability, expectation, variance), sorting, and basic terminology involving graphs (including the concepts of depth-first search and breadth-first search), and coding in Python or Java. Some of these are reviewed in the text. The lectures and homework involve the analysis of algorithms at a fairly mathematical level. We expect everyone to be comfortable reading and writing proofs at the level of CS 2800. Some homeworks include programming exercises that involve writing code in Python or Java.
Course Material Copyright
Course materials posted on this website, Ed Discussions, or Gradescope, are intellectual property belonging to the author. Students are not permitted to post course materials on the web, share them on any online platform, buy, sell, or distribute them outside of Cornell without the express permission of the instructor. Such unauthorized behavior constitutes academic misconduct.
Course Conduct
We understand that our members represent a rich variety of backgrounds and perspectives. Cornell University is committed to providing an atmosphere for learning that respects diversity. We expect students to communicate in a respectful manner with the instructors, course staff, and fellow students, in a way the honors the unique experiences, values, and beliefs represented by different members of our community.
Academic Integrity
Any violation of academic integrity will incur severe penalities. You are allowed to collaborate on the homework to the extent of formulating ideas as a group. However, you are expected to write up (and understand) the homework on your own, and you should acknowledge the names of the students with whom you collaborated.
From Cornell's code of academic integrity:
Absolute integrity is expected of every Cornell student in all academic undertakings. Integrity entails a firm adherence to a set of values, and the values most essential to an academic community are grounded on the concept of honesty with respect to the intellectual efforts of oneself and others. Academic integrity is expected not only in formal coursework situations, but in all University relationships and interactions connected to the educational process, including the use of University resources. […]
A Cornell student's submission of work for academic credit indicates that the work is the student's own. All outside assistance should be acknowledged, and the student's academic position truthfully reported at all times. In addition, Cornell students have a right to expect academic integrity from each of their peers.