Show The Graduate Center Menu
 
 

Algorithms

Instructor

Distinguished Professor Gabor T. Herman

Rationale

Analysis of algorithms involves characterizing the amount of resources consumed by an algorithm, measured as a function of input length, and typically bounded in the worst case. The most common resources considered are running time and space used, but others may be considered as well, such as number of random bits used or number of blocks read from secondary storage. In algorithm design, we seek algorithms that have good worst-case resource requirements and other attractive qualities, such as optimality or approximation guarantees, good performance “in practice,” parallelizability, and simplicity.

Course description

This course covers the design and analysis of algorithms for a number of fundamental problems, such as sorting, order statistics, minimum spanning trees, shortest paths, matching, maximum flow, minimum cut, satisfiability, knapsack, set covering, and linear programming. Common algorithm design techniques will be emphasized, including greedy, divide-and-conquer, and dynamic programming, as well as formulating problems as linear programs and the use of randomness. Some efficient data structures will also be examined, primarily hash tables, but also heaps and binary search trees. Finally, we will briefly discuss the halting problem, NP-completeness, and reductions.
Implementation projects might be assigned, applying algorithms to real-world applications.

List of topics

  • Growth of Functions:

    • Asymptotic Notation

    • Recurrence Relations

  • Divide-and-Conquer:

    • Sorting

    • Heapsort

    • Order Statistics

  • Greedy Algorithms:

    • Activity Selection

    • Minimum Spanning Tree: Prim, Kruskal, Boruvka

    • Matroids

    • Knapsack

    • Set Covering

  • Randomized Algorithms:

    • Quicksort

    • Satisfiability

  • Iterative Algorithms:

    • PageRank

    • k-Means

    • Steepest Descent

  • Dynamic Programming:

    • Longest Common Subsequence

    • Knapsack

    • Independent Set

    • Dijkstra Algorithm for Shortest Paths

  • Data Structures:

    • Heaps

    • Binary Search Trees

    • Hash Tables

    • Disjoint Sets

  • Network Flows:

    • Ford-Fulkerson

    • Bipartite Matching

    • Max Flow/Min Cut

  • Linear Programming (and Integer Programming):

    • Standard and Other Forms

    • Simplex

    • Duality

  • Computability and Complexity:

    • Halting Problem

    • Polynomial Time

    • Complexity Classes P and NP

    • NP-Completeness

    • Reductions

Learning Objectives

The student should be able to:

  • Explain and analyze the performance guarantees (in terms of optimality and efficiency) of standard algorithms for sorting, minimum spanning trees, shortest paths, maximum flow, hashing, and knapsack

  • Understand and program divide-and-conquer algorithms and the use of search trees

  • Understand the principles of greedy algorithms and matroids

  • Know the mathematical definitions needed for the specification of minimum spanning trees and be able to analyze and program algorithms for finding such trees

  • Seek solutions to newly encountered problems by applying basic algorithm design techniques, such as divide-and-conquer, greedy, dynamic programming; and judge which approaches are most appropriate or promising for the problem at hand

  • Formulate problems as (possibly integer) linear programs

  • Investigate or make informed judgments about whether a given problem is likely to be NP-complete

Assessment

The course grade will be determined by homework (and, possibly, in-class) problem sets (which may include programming) (65%) and a final exam (35%).

Textbook

Introduction to Algorithms (latest edition); Cormen, Leiserson, Rivest, and Stein; MIT Press.

References

Algorithm Design (latest edition); Kleinberg and Tardos; Pearson.