Show The Graduate Center Menu
 
 

Algorithms

Instructor: Distinguished Professor Gabor T. Herman

  • Office: Room 7301.07

  • Classroom: TBA

  • Time: 2-4PM Tuesdays


Course Description

Algorithm analysis evaluates time and memory resource requirements of a proposed algorithm as a function of input length. Algorithm design studies techniques for constructing algorithms with minimal resource requirements. This course covers mainly the design and analysis for a number of important and common algorithms, including divide and conquer, randomized algorithms, sorting, hash tables, binary search trees, dynamic programming, greedy algorithms, data structures for disjoint sets, graph algorithms, spanning trees and shortest paths. In addition, hands-on projects will be assigned to the students to implement fundamental and advanced computer algorithms in real applications.


Topic List

  • Growth of Functions

  • Divide-and-Conquer

  • Probabilistic Analysis and Randomized Algorithms

  • Heapsort

  • Sorting in Linear Time

  • Hash Tables

  • Binary Search Trees

  • Dynamic Programming

  • Greedy Algorithms

  • Data Structures for Disjoint Sets

  • Elementary Graph Algorithms

  • Minimum Spanning Trees

  • Single Source Shortest Paths


Learning Goals

The student should be able to:

  • Understand and program the most efficient algorithms for sorting and prove their optimality

  • Understand and program divide and conquer algorithms using tree search methods

  • Understand the principles of greedy algorithms

  • Know the definitions of graphs and analyze and program graph traversal algorithms and calculate minimum spanning trees


Assessment

  • There will be a homework assignment on each of the thirteen topics listed in the Topic List. These will be oriented toward testing the understanding and ability to program of the various algorithms as stated in the Learning Goals. These assignments will determine 65% of the final grade.

  • There will be a final exam consisting of problems the solution of which should demonstrate the student's understanding of various algorithms from the Topic List. This will be responsible for 35% of the final grade.


Text Book

Introduction to Algorithm (Latest Edition), Cormen, Leiserson, Rivest, and Stein, MIT press