BBM 202 - Algorithms (Spring 2016)

Lectures: Tue 10:00-10:50@D2,D3,D4, Thu 13:00-14:50@D2
Practicum (BBM204): Thu 15:00-16:50 @D1,D2,D3,D4

“What I mean is that if you really want to understand something, the best way is to try and explain it to someone else. That forces you to sort it out in your own mind. And the more slow and dim-witted your pupil, the more you have to break things down into more and more simple ideas. And thats really the essence of programming. By the time you’ve sorted out a complicated idea into little steps that even a stupid machine can deal with, you’ve certainly learned something about it yourself.”
~Douglas Adams, in Dirk Gently’s Holistic Detective Agency (1987)

Instructors:

Adnan Ozsoy (Sec. 1)

aozsoy-at-cs.hacettepe.edu.tr
Z08

Erkut Erdem (Sec. 2)

erkut-at-cs.hacettepe.edu.tr
114

Gonenc Ercan (Sec. 3)

gonenc-at-cs.hacettepe.edu.tr
212

Teaching Assistants:

Ali Caglayan

alicaglayan-at-cs-hacettepe.edu.tr
226

Cumhur Yigit Ozcan

cumhuryigitozcan-at-cs-hacettepe.edu.tr
122

Levent Karacan

karacan-at-cs-hacettepe.edu.tr
Z03 (Computer Vision Lab.)

Selman Bozkir

selman-at-cs-hacettepe.edu.tr
Multimedia Information Retrieval Lab.

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

60% Three Midterm Exams (12+32+16%)
40% Final Exam

Schedule (Tentative)

Week	Date	Topic	From the book	Notes
1	Feb 9	Introduction		Slides: (pdf, 4pp)
	Feb 11	Analysis of Algorithms	1.4	Slides: (pdf, 4pp)
2	Feb 16	Elementary Sorting Algorithms	2.1	PA1 out: (pdf) Slides: (pdf, 4pp)
	Feb 18	Mergesort	2.2	Slides: (pdf, 4pp)
3	Feb 23	Quicksort	2.3	Slides: (pdf, 4pp)
	Feb 25	Heapsort	2.4	Slides: (pdf, 4pp)
4	Mar 1	Elementary Search Algorithms	3.1	PA1 due Slides: (pdf, 4pp)
	Mar 3	Binary Search Trees	3.2	PA2 out: Slides: (pdf, 4pp)
5	Mar 8	1st Midterm Exam
	Mar 10	Balanced Trees	3.3	Slides: (pdf, 4pp)
6	Mar 15	Balanced Trees (cont'd)	3.3
	Mar 17	Hashing, Search Applications	3.4, 3.5	PA2 due, PA3 out Slides: (pdf, 4pp)
7	Mar 22	Undirected Graphs	4.1	Slides: (pdf, 4pp)
	Mar 24	Undirected Graphs (cont'd)	4.1
8	Mar 29	Directed Graphs	4.2	Slides: (pdf, 4pp)
	Mar 31	Directed Graphs (cont'd)		PA3 due
9	Apr 5	Minimum Spanning Trees	4.3	Slides: (pdf, 4pp)
	Apr 7	2nd Midterm Exam		PA4 out
10	Apr 12	Minimum Spanning Trees (cont'd)	4.3
	Apr 14	Shortest Path	4.4	Slides: (pdf, 4pp)
11	Apr 19	Shortest Path	4.4
	Apr 21	String Sorting	5.1	PA4 due Slides: (pdf, 4pp)
12	Apr 26	Tries, Substring Search	5.1, 5.2	Slides: (pdf, 4pp) Slides: (pdf, 4pp)
	Apr 28	Regular Expressions	5.4	PA5 out Slides: (pdf, 4pp)
13	May 3	3rd Midterm Exam	5.5
	May 5	Data Compression	5.5	Slides: (pdf, 4pp)

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/spring2016/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.