BLG 372E - Analysis of Algorithms, Spring 2009
Department of Computer Engineering ,
Istanbul Technical University
Instructors: Dr.Sema
Oktug and Dr.
Zehra Cataltepe
Assistants: Çiçek Çavdar (cavdarc@itu.edu.tr)
Schedule: Fri. 9:30-12:30 (Rooms: 5205 (ZC), 5302(SO))
Grading (final):
1 Midterm
(33%)
3 Programming
Projects (5+5+7=17%)
2 Pop Quizzes
(6%)
Final (44%)
Important Notice: You must be registered to the course at the ninova page in order to return homeworks and have access to the slides. Check to make sure that you are registered at the end of the first week and if you are not registered, let Sema Oktug (oktug@itu.edu.tr) know asap.
Important
Notice:Plagiarism (copying of
homeworks from each other or internet resources) is strictly discouraged, if we
realize that you did copy your homework, you will get zero from that
homework, you may get an FF from the course and the Student Affairs
Office will be informed.
Programming Projects: Will be in C++. There will be explicit instructions
on which files to submit, how it should be compiled, test cases etc. A project
that does not compile or does not provide the necessary files will get zero.
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 (Please see
ninova pages for the latest slides):
|
Week |
Date |
Topics |
|
1 |
Feb 6 |
Introduction. Some
representative problems. |
|
2 |
Feb 13 |
Introduction. Some
representative problems. |
|
3 |
Feb 20 |
Basics of algorithm
analysis. |
|
4 |
Feb 27 |
Graphs. (Problem session) (Project
1 announced) |
|
5 |
Mar 6 |
Greedy algorithms-I. (Problem session) |
|
6 |
Mar 13 |
Greedy algorithms-II. |
|
7 |
Mar 20 |
Midterm (Project 2 announced) |
|
8 |
Mar 27 |
Divide and conquer-I. |
|
9 |
Apr3 |
Divide and conquer-II. (Problem session) |
|
10 |
Apr 10 |
Dynamic programming. (Problem
session) (Project 3 announced) |
|
11 |
Apr17 |
Network Flow-I. |
|
12 |
Apr24 |
Network Flow-II. (Problem session) |
|
13 |
May1 |
NP and computational intractability-I.
(Project 4 announced) |
|
14 |
May 8 |
NP and computational
intractability-II. (Problem session) |
Prepared by Sema Oktug and
Zehra Cataltepe, Feb. 2009.