BLG381E, Advanced Data Structures, Fall 2012

Istanbul Technical University, Computer Eng. Dept.

Lecturers	Zehra Çataltepe, cataltepe@itu.edu.tr (CRN: 11309) Hazım Kemal Ekenel, ekenel@itu.edu.tr (CRN: 11313)
Schedule	Wednesday 13:30-16:30
Classrooms	Cataltepe: 4102, Ekenel: 2102
Office hours	Please email us to set an appointment to meet.
Teaching Assistant	Atakan Aral (aralat@itu.edu.tr) Mustafa Ersen (ersenm@itu.edu.tr)
Web site	www3.itu.edu.tr/~cataltepe/ADS
Ninova	http://ninova.itu.edu.tr/tr/dersler/bilgisayar-bilisim-fakultesi/170/blg-381e/ Announcements, Course slides, Homework assignments Make sure you are added to Ninova site and check your ITU e-mail once every week!

Textbook

Introduction to Algorithms, T.H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, MIT Press, 2001, ISBN: 0-262-03293-7. (see also Chapter Notes (McGraw Hill))

Tentative Course Outline

(Homework and exam dates may change during the term. Please make sure that you check your ITU email address and ninova regularly!)

Week 1, Sept 26: Ch1: Role of Algorithms in Computing, Ch 2: Getting Started (reading material: Secondary storage devices)

Week 2, Oct 3: Ch3. Growth of Functions

Week 3, Oct 10: Ch4. Recurrences, RECITATION1, Project1 handed out

Week 4, Oct 17: Ch5. Probabilistic Analysis and Randomized Algorithms

Week 5, Oct 24: No class, (Holiday, Kurban Bayramı)

Week 6, Oct 31: Ch6. Heapsort, RECITATION2, Project2 handed out.

Week 7, Nov 7: Ch7. Quicksort, Ch8. Sorting in Linear Time,

Week 8, Nov14: Ch9. Medians and Order Statistics, Ch10. Elementary Data Structures (Review)

RECITATION3,

Week 9, Nov 21: MIDTERM

Week 10, Nov 28: Ch11. Hash Tables

Week 11, Dec 5: Ch12. Binary Search Trees (Review) Ch 13. Red-Black Trees, 2-3 Trees, 2-3-4 Trees, Project3 handed out RECITATION4

Week 12, Dec 12: Ch13 contd., Ch14. Augmenting Data Structures,

Week 13, Dec 19: Ch17. Amortized Analysis, Ch 18. B Trees

Week 14, Dec 26: Ch 19. Binomial Heaps, Ch 20. Fibonacci Heaps, RECITATION5

Grading

Midterm exam

(closed book and notes)

30%

Projects

due on Tuesdays by 5pm, submit through Ninova.

Use C++ and object oriented approach in your assignments.

30%

Final Exam

(closed book and notes)

In order to be able to take the final exam for BLG381E you have to have a weighted average score of 20 (over 100) for midterm and projects. Otherwise you will get a VF from the course.

40%