Show The Graduate Center Menu

Analysis of Algorithms

 
 

Analysis of Algorithms

Instructor: Professor Amotz Bar-Noy

  • Office: Room 4327

  • Classroom: 3212

  • Time: 10AM-1PM Thursdays

 

Course Description

Students will learn several fundamental techniques and principles of efficient algorithm design and tools and methods to analyze the complexity of algorithms. Topics covered include:  Order Statistics, Sorting, Divide and Conquer, Greedy Algorithms, Dynamic Programming, Graphs, Social Graphs, Graph Traversals, Minimum spanning Trees, NP-Completeness, Euler and Hamiltonian paths, Graph Coloring.
 

Topic List

Learning Goals

The student should be able to:

  • Understand and program the most efficient algorithms for sorting and computation of order statistics and be able to 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 algorithmsand calculate minimum spanning trees

  • Use the appropriate formalisms for proving problems are hard and be able to use the formalisms for proving that problems are NP-complete


Assessment

  • 50% Final Exam

  • 30% Midterm Exam

  • 10% Quizzes

  • 10% Homework


Text Book

  • Main textbook:

    • "Introduction to Algorithms (third edition)," by Cormen, Leiserson, Rivest, and Stein, MIT press. (Second edition and even first edition are fine).

  • Other books:

    • "Algorithms," by Dasgupta, Papadimitriou, and Vazirani, McGraw Hill (free copyhttp://beust.com/algorithms.pdf).

    • "Algorithm Design," by Kleinberg and Tardos, Addison Wesley.

    • "Algorithm Design," by Goodrich and Tamassia, Wiley.

    • "Computer Algorithms: Introduction to Design and Analysis (3rd Edition)," by Baase and Van Gelder, Addison Wesley.

    • "Introduction to Algorithms a Creative Approach," by Manber, Addison-Wesley.