Analysis of Algorithms

Office: Room 4327

Classroom: 3212

Time: 10AM1PM 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, NPCompleteness, 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
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, AddisonWesley.