General Information | Course Description | Learning Objectives | Course Material | Prerequisites | Academic Integrity

General Information

Lectures: MWF 9:05am–9:55am, Uris Hall G01, map
Course Staff:

• Instructor: Prof. Michael Kim
  Office Hours: Fridays, 1-3pm in Gates 203
• Head TA: Ellie Fassman
  Office Hours: Mondays, 10:30a-12:30p in Upson 102
• Course Coordinator: Kimberly Budd, Gates Hall 401
• All email correspondences should be sent to cs4820sp25@gmail.com.
  Emails sent to the Course Staff's personal accounts will not be answered in a timely manner.

Exam Dates

• Prelim 1: Thursday, February 13, 7:30pm
• Prelim 2: Thursday, March 27, 7:30pm
• Final: TBD

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. Roughgarden. Algorithms Illuminated.
• T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms.
• D. Kozen. The Design and Analysis of Algorithms.

Prerequisites

The prerequisites for the course 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. 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. 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 basic coding. 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.

Academic Integrity

In CS 4820, you are expected to uphold 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.