Announcements

  1. (Dec. 31; 4:19 pm) Final Place information is published.
  2. (Dec. 11; 6:15 pm) HW5 is published.
  3. (Dec. 9; 10:26 pm) Section 1 Quiz 6 solution.
  4. (Nov. 23; 6:28 pm) HW4 is published.
  5. (Nov. 16; 12:16 pm) Section 1 Quiz 5 solution.
  6. (Nov. 11; 6:52 pm) Midterm 1 grades have been announced.
  7. (Nov. 6; 6:11 am) HW3 is published.
  8. (Oct. 27; 4:12 pm) Section 1 Quiz 3 & Quiz 4 solutions.
  9. (Oct. 23; 4:14 pm) Section 1 Quiz 1 & Quiz 2 solutions.
  10. (Oct. 19; 11:28 pm) HW2 is published. Due date: Nov. 3 by 23:59.
  11. (Oct. 15; 12:12 pm) Two copies of the textbook is now available in the reserve section of the library, for library use only.
  12. (Oct. 7; 7:01 pm) Midterm 1 & Midterm 2 Time and Place information is published.
  13. (Oct. 7; 7:01 pm) Section 1 Book Weight Estimations. The Wisdom of Crowds experiment.
  14. (Oct. 2; 1:17 pm) HW1 is published.
  15. (Sep. 30; 5:38 pm) Please register to the Moodle system: You will submit your assignments using Moodle.
  16. (Sep 10; 12:17 pm) Course page is online: Welcome to the class.

Course Description

The course picks up from where the first semester course left by discussing concepts related to algorithmic efficiency on basic abstract data types and some sorting algorithms that utilize recursion. Then, the course introduces the abstract data types of trees, tables, priority queues, and graphs, and shows how one can implement them in C++ using fundamental data structures by emphasizing run-time complexity analysis.

Section 1

Instructor: Fazlı Can (Office: EA 511, Email: canf[at]cs.bilkent.edu.tr)
Lectures: Tue 10:40-12:30 (B Z08), Fri 9:40-10:30 (B Z08)

Section 2

Instructor: Erman Ayday(Office: EA 529, Email: erman[at]cs.bilkent.edu.tr)
Lectures: Tue 15:40-16:30 (B Z08), Fri 13:40-15:30 (B Z08)

Teaching Assistants

Graders

Office Hours

Texts

  1. Frank M. Carrano, Timothy Henry, Data Abstraction and Problem Solving with C++: Walls and Mirrors, 6th edition, Pearson, 2013. Textbook.
  2. Frank M. Carrano, Data Abstraction and Problem Solving with C++: Walls and Mirrors, 5th edition, Addison-Wesley, 2006.
  3. Mark A. Weiss, Data Structures & Algorithm Analysis in C++, 3rd edition, Addison Wesley, 2006. (recommended)
  4. Harvey M. Deitel and Paul J. Deitel, C++ How to Program, 8th edition, Prentice Hall, 2011. (recommended)

Lectures

Topics

Contents: Carrano-Henry Book, Sixth Ed., Related Chapter

Algorithm Efficiency and Sorting

[ Slides, Slides ]
  • Algorithm Efficiency and Sorting Algorithm Efficiency: Ch. 10, 11
  • Sorting animation
  • 3 Weeks

Trees

[ Slides ]
  • Bınary Search Tree: Ch. 15, 16
  • 2 Weeks

Heaps

[ Slides ]
  • Heaps: Ch. 17
  • 2 Weeks

Balanced Search Trees

[ Slides: Part 1 | Part 2 ]
  • AVL, 2-3, 2-3-4, Red-Black Trees: Ch. 19
  • 3 Weeks

Hashing

[ Slides ]
  • Hashing: Ch. 18
  • 1 Week

Graphs

[ Slides ]
  • Graphs: Ch.20
  • 3 Weeks

Exams

Homework (tentative schedule)

  1. Assignment 1: Algorithm Analysis using Sorting Algorithms
  2. Assignment 2: Mostly Binary Search Trees
  3. Assignment 3: Heaps and AVL Trees - Sample files for the Heaps program: file1, file2, file3, file4, file5
  4. Assignment 4: AVL, 2-3, and 2-3-4 trees - Sample files for the AVL program: Dubliners
  5. Assignment 5: Graphs

Homework assignments will be posted on this page about 10 days before their due date. Assignments are expected to be turned in by 23:59 on the due date. You should upload your solutions to the homework assignments using the online submission form (link will be provided) before the deadline. No late submission will be accepted.

Please make sure you fully understand the Bilkent University Policy on Academic Honesty (in Turkish) and the Rules and Regulations of the Higher Education Council (YOK) (in Turkish). Cheating and plagiarism on exams, quizzes, and homework assignments will be punished according to these regulations.

Grading Policy

Quiz & Attand.:15%
Homework:10%
Midterm exam 1:25%
Midterm exam 2:25%
Final exam:25%

To avoid FZ and take the final exam a student must 1. collect at least 26 points (40% of total 65) from the weighted sum of the quiz and midterm grades, and 2. attend at least 70% of classes; otherwise, the student will receive the FZ grade.

Advice

When you are in doubt, ask. Use office hours. If you cannot visit us during office hours, you can always ask questions or arrange meetings by e-mail. Study regularly for the course and attend classes. Do your assignments on time and pay attention to the instructions for submitting assignments. Always make sure that the code you submitted does compile and run correctly.

Related Links