Course Information

About

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 students 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 underlies 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.

Time and Location

BBM202

Section 1: Wednesday at 09:40-12:30@D8
Section 2: Wednesday at 09:40-12:30@D9
Section 3: Wednesday at 09:40-12:30@D10

BBM204

Thursday at 14:40-16:30@Zoom

Instructors

         

Erkut Erdem (Section 1) · erkut@cs.hacettepe.edu.tr
Adnan Ozsoy (Section 2) · adnan.ozsoy@hacettepe.edu.tr
Suat Ozdemir (Section 3) · ozdemir@cs.hacettepe.edu.tr

Teaching Assistants

    

Ali Burak Erdogan · burakerdogan@cs.hacettepe.edu.tr

Alperen Cakin · alperencakin@cs.hacettepe.edu.tr

Selma Dilek · selma@cs.hacettepe.edu.tr

Student Assistants

         

Mehmet Berat Ersari · b21992943@cs.hacettepe.edu.tr

Mohamed Hedi Elfkir · b21903585@cs.hacettepe.edu.tr

Sura Nur Erturkmen · b21946127@cs.hacettepe.edu.tr

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/spring2023/bbm202
https://piazza.com/hacettepe.edu.tr/spring2023/bbm204

Course Requirements and Grading

Grading for BBM202 will be based on

In BBM204, the grading will be based on

Policies

A student who do not submit more than 2 assignments will fail BBM204 directly with an F1 grade. You are responsible for all material presented in lectures. 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.

Text Books

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

  • Algorithm Design, Jon Kleinberg and Eva Tardos, Addison-Wesley Professional, 2005

Schedule (Tentative)

Week Date Topic Notes
1 Mar 1 Course Introduction [slides],
Undecidability [slides],
Analysis of Algorithms [slides]
Reading: SW 1.4
Reading: Turing Machines, Universality, Halting Problem
2 Mar 8 Elementary Sorting Algorithms [slides]
Mergesort [slides]
Reading: SW 2.1, 2.2
3 Mar 15 Quicksort [slides]
Heapsort[slides]
Reading: SW 2.3, 2.4
PA1 out
4 Mar 22 Hashing, Search Applications [slides] Reading: SW 3.4, 3.5
5 Mar 29 Dynamic Programming Reading: KT 6.1-6.7
PA1 due
6 Apr 5 Greedy Programming Reading: KT 4.1-4.3
PA2 out
7 Apr 12 Undirected Graphs
Directed Graphs
Reading: SW 4.1, 4.2
8 Apr 19 Minimum Spanning Trees Reading: SW 4.3
PA2 due
9 Apr 26 Midterm Review Midterm Exam
PA3 out
10 May 3 Shortest Path Reading: SW 4.4
11 May 10 Substring Search
Regular Expressions
Reading: SW 5.3, 5.4
PA3 due
12 May 17 String Sorting Reading: SW 5.1
PA4 out
13 May 24 Data Compression Reading: SW 5.5
14 May 31 Reductions, Intractability Reading: SW 6
PA4 due

Previous editions