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: Eva Tardos, email.
  Office Hours: Tuesdays 10:30-11:30 and Fridays 10-11 in Gates 316
• Head TAs: Ramiro Deo-Campo Vuong; Santiago Lai; Sylvan Martin; Joey Rivkin
  Office Hours: in Rhodes 503 see below
• Course Coordinator: Amy Elser, Gates Hall 401, email
• Course email: cs4820sp26@gmail.com. Please use this for course-related matters. Post on Ed first (private posts are visible to all TAs). Use the course email for sensitive issues that should not be shared with the whole staff only the instructor, PhD/MS TAs and the course coordinator. In exceptional cases where you want only the instructor to see your message, you may use the personal email above.

Exam Dates

• Prelim 1: Thursday, February 12, 7:30pm-9:00pm
• Prelim 2: Tuesday, March 24, 7:30pm-9:00pm
• 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;
• Recognize resource management as well as partition problems that can be reduced 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/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 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/5820, 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.

This course is participating in Accepting Responsibility (AR), which is a pilot supplement to the Cornell Code of Academic Integrity (AI). For details about the AR process and how it supplements the AI Code, see the AR website.