BBM 202 - Algorithms (Spring 2014)

Lectures: Tue 13:00-13:45@D4, Thu 09:00-10:45@D2 (Section 2)
Practicum (BBM204): Fri 13:00-14:45 @D3 (Sections 4-5)

“It has often been said that a person does not really understand something until he teaches it to someone else. Actually a person does not really understand something until he can teach it to a computer, i.e. express it as an algorithm The attempt to formalise things as algorithms lead to a much deeper understanding than if we simply try to comprehend things in the traditional way.”
   ~Donald E. Knuth, in American Mathematical Monthly (1974)

Instructor: Erkut Erdem

erkut-at-cs-hacettepe.edu.tr
114
+90 312 297 7500, 149

Course Description

The subject matter of this course concerns fundamental algorithms in computer science. The course is structured around key topics including analysis of algorithms, sorting, searching, graph algorithms, string processing, dynamic programming, combinatorial search and NP-completeness.

The goal of this course is to teach student how to develop algorithms in order to solve the complex problems in the most efficient way. The students are expected to develop a foundational understanding and knowledge of key concepts that underly important algorithms in use on computers today. The students will also be expected to gain hand-on experience via a set of programming assignments supplied in the complementary BBM 204 Software Practicum.

Textbook

Algorithms, 4th Edition, R. Sedgewick and K. Wayne, Addison-Wesley Professional, 2011

Grading

  • 56% Three Midterm Exams (12+32+12%)
  • 40% Final Exam
  • 4% Class participation

Schedule (Tentative)

Week Date Topic From the book Notes
1 Feb 18 Introduction Slides: (pdf, 4pp)
Feb 20 Analysis of Algorithms 1.4 Slides: (pdf, 4pp)
2 Feb 25 Elementary Sorting Algorithms 2.1 Slides: (pdf, 4pp)
Feb 27 Mergesort 2.2 Slides: (pdf, 4pp)
3 Mar 4 Quicksort 2.3 Slides: (pdf, 4pp)
Mar 6 Priority Queues and Heapsort 2.4 PA1 out
Slides: (pdf, 4pp)
4 Mar 11 Elementary Search Algorithms 3.1 Slides: (pdf, 4pp)
Mar 13 Binary Search Trees 3.2 Slides: (pdf, 4pp)
5 Mar 18 1st Midterm Exam Questions: (pdf)
Mar 20 Balanced Trees 3.3 PA1 due, PA2 out
Slides: (pdf, 4pp)
Demos: Kd tree
6 Mar 25 Hashing 3.4 Slides: (pdf, 4pp)
Mar 27 Search Applications 3.5 Slides: (pdf, 4pp)
7 Apr 1 Undirected Graphs 4.1 Slides: (pdf, 4pp)
Apr 3 Directed Graphs 4.2 PA2 due
Slides: (pdf, 4pp)
8 Apr 8 Review
Apr 10 2nd Midterm Exam Questions: (pdf)
9 Apr 15 Minimum Spanning Trees 4.3 Slides: (pdf, 4pp)
Apr 17 Shortest Path 4.4 PA3 out (sample I/O)
Slides: (pdf, 4pp)
10 Apr 22 String Sorts 5.1 Slides: (pdf, 4pp)
Apr 24 Tries 5.2 Slides: (pdf, 4pp)
11 Apr 29 Substring Search 5.3 Slides: (pdf, 4pp)
May 1 No class (Worker's Day) PA3 due
12 May 6 3rd Midterm Exam Questions: (pdf)
May 8 Regular Expressions 5.4 PA4 out (sample I/O)
Slides: (pdf, 4pp)
13 May 13 Data Compression 5.5 Slides: (pdf, 4pp)
May 15 Reductions 6.5 Slides: (pdf, 4pp)
14 May 20 Intractability 6.6 Slides: (pdf, 4pp)
May 22 Advanced topics PA4 due

Communication:

The course webpage will be updated regularly throughout the semester with lecture notes, programming and reading assignments and important deadlines. All other course related communications will be carried out through Piazza. Please enroll it by following the link https://piazza.com/hacettepe.edu.tr/spring2014/bbm202

Policies:

Attendance to lectures is required. You are responsible for all material presented in lecture. Some of the course material might not be covered in the textbook.

All work on assignments must be done individually unless stated otherwise. You are encouraged to discuss with your classmates about the given assignments, but these discussions should be carried out in an abstract way. That is, discussions related to a particular solution to a specific problem (either in actual code or in the pseudocode) will not be tolerated.

In short, turning in someone else’s work, in whole or in part, as your own will be considered as a violation of academic integrity. Please note that the former condition also holds for the material found on the web as everything on the web has been written by someone else.

© 2014 Hacettepe University