# 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.

### 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.