BIL 741, 2010-2011 Spring

Advanced Analysis of Algorithms I 

Lectures: Wednesday 13:00-15:45 @D5

Instructor: Erkut Erdem

Office: 114

Office Hours: Mon 09:00-10:30

e-mail: erkut@cs.hacettepe.edu.tr

Course Description:

Complexity of algorithms. Recurrence relations. Solving recurrences. Analysis of selected sorting and graph algorithms. Major algorithm design paradigms. Divide and conquer. Greedy approach. Dynamic programming. Backtracking. Branch and bound. NP-complete and NP-hard problems. Selected advanced algorithmic problems. 

Textbook:

• Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, 3rd Edition, MIT Press, 2009

Tentative Outline

• Analysis of Algorithms
• Introduction
• Growth of Functions
• Recurrence Relations
• Major Algorithm Design Paradigms
  • Divide and Conquer
  • Greedy Approach
  • Dynamic Programming
  • Backtracking
  • Branch and Bound
• NP-Completeness
• Additional advanced algorithmic problems

Assignments Policy

There will be written and programming assignments, which have to be done individually. Completing these assignments is a key to be successful in this course.

Grading Policy

Assignments 30%, Midterm 30%, Final %40

Resources

Homework Assignments

• Assignment #1 Due on Wednesday, March 23rd, 2011
• Assignment #2 Due on Wednesday, March 30th, 2011

Please follow the course newsgroup news.cs.hacettepe.edu.tr/dersler.bil741 for announcements.