BLG 336E, Analysis of Algorithms II, Spring 2018
Istanbul Technical University, Computer Eng. Dept.
Lecturers
Zehra
Çataltepe, cataltepe@itu.edu.tr
Sanem
Sarıel, sariel@itu.edu.tr
Schedule: Tuesday
9:30-12:30
Classrooms: CRN21548
(Sariel): 6309, CRN21549 (Cataltepe): 4104
Office hours: Please
email us to set an appointment to meet.
Teaching Assistants: Cagatay
Koc (kocca@itu.edu.tr), Emrullah Gazioglu (egazioglu@itu.edu.tr), Kubra Cengiz (kcengiz@itu.edu.tr)
Web site: web.itu.edu.tr/~cataltepe/aoa2/index.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. If you can not submit to ninova, your homework will not be accepted.
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 6 |
Introduction. Some representative problems.
(01Intro.ppt,Prerequisites.pptx, 01stable-matching.ppt) |
|
2 |
Feb 13 |
Introduction. Some representative problems.
(01stable-matching.ppt) |
|
3 |
Feb 20 |
Basics of algorithm analysis. (Problem session 1) |
|
4 |
Feb 27 |
Graphs. (Project
1 announced) |
|
5 |
Mar 6 |
Greedy algorithms-I. (Problem session 2) |
|
6 |
Mar 13 |
Greedy algorithms-II. |
|
7 |
Mar 20 |
MIDTERM |
|
8 |
Mar 27 |
SPRING BREAK |
|
9 |
Apr 3 |
Divide and conquer (Project 2 announced) (Problem
session 3) |
|
10 |
Apr 10 |
Dynamic Programming I |
|
11 |
Apr 17 |
Dynamic Programming II (Problem session 4) |
|
12 |
Apr 24 |
Network Flow-I (Project 3 announced) |
|
13 |
May 1 |
National Holiday, Labor Day |
|
14 |
May 8 |
Network Flow II (Problem session 5) |
|
15 |
May 15 |
NP and computational intractability-I, II (Problem session 6) |
1 Midterm (30%)
3 Programming Projects (30%)
Final (40%)
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 25/100 (=12.5/50) over midterm and
the first two projects. Otherwise you will get a VF from the course.