Announcements

  1. (Jan 28) Course page is online.
  2. (Feb 17) Homework assignment 1 is available.
  3. (Mar 1) Homework assignment 2 is available.
  4. (Mar 21) Homework assignment 3 is available.
  5. (Apr 11) Homework assignment 4 is available.
  6. (Apr 27) Homework assignment 5 is available.

Course Description

The course picks up from where CS 201 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: Selim Aksoy (Office: EA 422, Email: )
Lectures: Tue 15:40-17:30 (EB 101), Fri 13:40-15:30 (EB 101)

Section 2

Instructor: Çiğdem Gündüz Demir (Office: EA 423, Email: gunduz[at]cs.bilkent.edu.tr)
Lectures: Tue 10:40-12:30 (EB 101), Fri 8:40-10:30 (EB 101)

Section 3

Instructor: Mustafa Özdal (Office: EA 420, Email: mustafa.ozdal[at]cs.bilkent.edu.tr)
Lectures: Tue 13:40-15:30 (EB 101), Thu 15:40-17:30 (EB 101)

Teaching Assistants

Office Hours

Texts

  1. Frank M. Carrano and Timothy Henry, Data Abstraction and Problem Solving with C++: Walls and Mirrors, 6th edition, Pearson, 2013. (required)
  2. Frank M. Carrano, Data Abstraction and Problem Solving with C++: Walls and Mirrors, 5th edition, Addison-Wesley, 2006. (old version)
  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, any edition, Prentice Hall, 2011 or newer. (recommended)

Lectures

Topics

Contents

Algorithm Analysis

[ Slides ]
  • Measuring the Efficiency of Algorithms (Ch. 10 of Carrano-Henry)

Sorting

[ Slides ]
  • Sorting Algorithms and Their Efficiency (Ch. 11 of Carrano-Henry)
  • Sorting animation

Trees

[ Slides ]
  • Binary Search Trees (Ch. 15, 16 of Carrano-Henry)

Heaps

[ Slides ]
  • Heaps (Ch. 17 of Carrano-Henry)

Balanced Search Trees

[ Slides: Part 1 | Part 2 ]
  • AVL, 2-3, 2-3-4, Red-Black Trees (Ch. 19 of Carrano-Henry)

Hashing

[ Slides ]
  • Hashing (Ch. 18 of Carrano-Henry)

Graphs

[ Slides ]
  • Graphs (Ch. 20 of Carrano-Henry)

Exams

Homework

  1. Assignment 1: Due 23:59 on February 29, 2016
  2. Assignment 2: Due 23:59 on March 14, 2016
  3. Assignment 3: Due 23:59 on March 31, 2016
  4. Assignment 4: Due 23:59 on April 24, 2016
  5. Assignment 5: Due 23:59 on May 9, 2016

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 before the deadline.

For late assignments, each student will be given a total of three grace days (whole or partial) for the whole semester. Once these late days have been exhausted, no late assignments will be accepted. As an example, if Student A submits her/his 1st assignment 29 hours late, s/he will have used two late days and have only one day left. If Student A then submits her/his 2nd assignment 5 hours late, s/he will have used her/his remaining late day. If Student A submits her/his 3rd assignment 1 minute late, this assignment will not be accepted. Note that no late submission will be allowed for the last homework.

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:15%
Homework:10%
Midterm exam 1:25%
Midterm exam 2:25%
Final exam:25%

In order to be able to take the final exam, a student must collect at least 26 points (40% of total 65) from the weighted sum of the quiz and midterm grades; 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