BLG 372E - Analysis of Algorithms, Spring 2008

Department of Computer Engineering , Istanbul Technical University

Instructors: Dr.Sema Oktug and Dr. Zehra Cataltepe

Assistants:  Melike Erol (melike.erol@itu.edu.tr), Zehra Gürbüz (gurbuzz@itu.edu.tr)

Schedule: Fri. 10:00-12:50 (Rooms: 5302 (ZC), 5304(SO)) 

Grading (tentative): 
If you miss more than 4 classes you will get a VF from the course. 
1 Midterm (30%)  
2 Projects (22%)  
Pop Quizzes (8%)
Final (40%)   
 
 
Reference Book: 
-  J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2006.
 

Other References:
-Fundamentals of Algorithmics,Brassards and Bratley, Prentice Hall (Available at the Central Library, QA9.58.B73 1996).

-Introduction to Algorithms, Cormen, Leiserson and Rivest, The MIT Pres/McGraw-Hill.
- Algorithms and Complexity , Wilf. You may download free from www.upenn.edu.

 

Topics Covered:

Week

Topics

1

Introduction. Some representative problems.

2

Basics of algorithm analysis.

3

Graphs. (Problem session)

4

Greedy algorithms-I.

5

Greedy algorithms-II. (Problem session)

(Project #1 will be announced)

6

Divide and conquer-I. (Problem session)

7

Midterm  (March 21, 2008) 

8

Divide and conquer-II.

9

Dynamic programming.  (Project#2 will be announced) (Problem session)

10

Network Flow-I.

11

Network Flow-II. (Problem session)

12

NP and computational intractability-I.

13

NP and computational intractability-II. (Problem session)

Prepared by Sema Oktug and Zehra Cataltepe, Feb. 2008.