BLG 336E,
Analysis of Algorithms II, Spring 2016
Istanbul
Technical University, Computer Eng. Dept.
Lecturers
Sanem Sarıel, sariel@itu.edu.tr
Şerif Bahtiyar, bahtiyars@itu.edu.tr
Schedule: Tuesday 9:30-12:30
Classrooms: CRN 21886: 5305, CRN 21887: 4104
Office
hours: Please
email us to set an appointment to meet.
Teaching Assistants: Doğan Altan, Ezgi Yıldırım, Hasan Kıvrak
Web
site: http://web.itu.edu.tr/sariel/courses/aoa2.html
Ninova:
http://ninova.itu.edu.tr/tr/dersler/bilgisayar-bilisim-fakultesi/4573/blg-336e/
Announcements,
Course slides, Homework assignments
Make sure you
are added to Ninova site and check your ITU e-mail once every week!
Contact the
course assistants if you are not added to Ninova.
Programming
Projects: Will be in C++.
There will be explicit instructions on which files to submit, how it should be
compiled, example cases etc. Some examples will be provided so that you can
test your program yourselves. However, your program will be graded based on how
good it is in solving the given problem.
A project that does not compile or does
not provide the necessary files will get zero, no exceptions! Projects
not submitted through the online submission system will not get accepted, even
if they are a couple of minutes late. So, please submit to ninova ahead of the
due second.
Plagiarism
(copying (parts) of projects from each
other or internet resources) is strictly discouraged. You may discuss the
problem with your classmates, but you must write your own code. You must not
take somebody else’s code and modify it and submit it. If we realize that you
did copy, you will get zero from that project, you may get an FF from the
course and the Student Affairs Office will be informed.
Reference
Book:
- J.
Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2006.
Other
References:
-Introduction
to Algorithms, Cormen, Leiserson and Rivest, The MIT Pres/McGraw-Hill.
-Fundamentals
of Algorithmics,Brassards and Bratley, Prentice Hall (Available at the Central
Library, QA9.58.B73 1996).
- Algorithms and Complexity,
Wilf.
Topics Covered
(Tentative list. Please see ninova pages for the latest slides):
|
Week |
Date |
Topics |
|
1 |
Feb 9 |
Introduction.
Some representative problems. |
|
2 |
Feb 16 |
Introduction.
Some representative problems. (Quiz1) |
|
3 |
Feb 23 |
Basics of algorithm
analysis. (Problem session 1) |
|
4 |
Mar 1 |
Graphs. (Project 1 announced) |
|
5 |
Mar 8 |
Greedy
algorithms-I. (Problem
session 2) |
|
6 |
Mar 15 |
Greedy
algorithms-II. (Quiz2) |
|
7 |
Mar 22 |
Divide and
conquer (Problem session 3) |
|
8 |
Mar 29 |
MIDTERM |
|
9 |
Apr 5 |
Dynamic
Programming I (Project
2 announced) |
|
10 |
Apr 12 |
Dynamic
Programming II (Quiz3) (Problem session 4) |
|
11 |
Apr 19 |
Network
Flow-I |
|
12 |
Apr 26 |
Network Flow
II (Problem session 5) (Project 3 announced) |
|
13 |
May 3 |
NP and
computational intractability-I |
|
14 |
May 10 |
NP and
computational intractability-II (Problem session
6) |
1 Midterm
(25%)
3 Programming
Projects (30%)
3 Quizzes
(%10) [Quiz1: %3, Quiz2:%4, Quiz3:%3]
Final
(35%)
Please
note:
All the exams
are closed books and notes.
Use C++ and
object oriented approach in your assignments.
In order to be
able to take the final exam for BLG336E you have to have a weighted average
score of 30 (over 100) for midterm and projects and you have to attend 70% of
the classes. Otherwise you will get a VF from the course.