This course introduces basic concepts of design and analysis of computer algorithms: the basic principles and techniques of computational complexity (worst-case and average behavior, space usage, and lower bounds on the complexity of a problem), and algorithms for fundamental problems. It also introduces the areas of NP-completeness and parallel algorithms.

조유정, 정영섭, 김상일, 김민협.

The class meets Monday, Wednesday, and Friday from 10:00 to 10:50 in room 102 in the IT building (N1). Lectures are given in English.

The final grade will be composed as follows (small changes reserved):

- Programming Homework (10%), Paper Homework (10%), Midterm (30%), Final (40%), Participation (10%).

Students who take CS300 for the second time cannot receive a grade better than B+.

There will be a midterm and a final exam.

The midterm exam is on April 26 from 10:00 to 12:00 in room 1501 in the "old" CS building E3-1.

The final exam is on June 21 from 10:00 to 12:00 in room 1501 in the "old" CS building E3-1.

Here is a rough list of what we will cover in each week of the semester.

Week 1 | Introduction, graph basics and representation, DFS |

Week 2 | Direct graphs, strongly connected components, BFS |

Week 3 | Shortest paths |

Week 4 | Reductions, recursion, divide-and-conquer |

Week 5 | Sorting |

Week 6 | Introduction to dynamic programming |

Week 7 | More dynamic programming: edit distance, Huffman trees |

Week 8 | Midterm exam |

Week 9 | Greedy algorithms |

Week 10 | Minimum spanning trees |

Week 11 | Introduction to randomized algorithms |

Week 12 | Hash tables |

Week 13 | Lower bounds and adversary arguments |

Week 14 | Polynomial time reductions, SAT |

Week 15 | NP-Completeness |

Week 16 | Final Exam |

Please check the bulletin board regularly for announcements. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)

The class will mostly use the book Algorithms by Dasgupta, Papadimitriou, Vazirani. The international edition is quite inexpensive, and there is also a Korean translation. The draft version is available online for free. Students are not required to buy the book.

We will also make use of Jeff Erickson's lecture notes and lecture notes by Avrim Blum.

The material covered in the lectures so far:

03-04 | Introduction | slides | ||

03-06 | No class | |||

03-08 | No class | |||

03-11 | No class | |||

03-13 | Karatsuba's algorithm | notes by Avrim Blum | Book 2.1 | |

03-15 | Strassen's algorithm, Big-Oh, Omega, Theta | notes by Avrim Blum | Book 2.5, 0.3 | |

03-18 | Solving recursions | Book 2.2 | ||

03-20 | Master theorem, recursion examples | Book 2.2 | ||

03-22 | Closest point problem, Median | Book 2.4 | ||

03-25 | Selection problem: randomized and deterministic | notes by Jeff Erickson | Book 2.4 | |

03-27 | Graphs, DFS | Book 3.1, 3.2 | ||

03-29 | Directed graphs, DAGs | Book 3.3 | ||

04-01 | Strongly connected components | Book 3.4 | ||

04-03 | Condensed graph (Meta-Graph), computing SCCs | Book 3.4 | ||

04-05 | Breadth-First Search | Book 4.1, 4.2 | ||

04-08 | Dijkstra's Algorithm | Book 4.3, 4.4 | ||

04-10 | Bellman-Ford algorithm, shortest-path in DAGs | Book 4.6, 4,7 | ||

04-12 | Negative cycles; MSTs and Prim's algorithm | Book 4.6.2, 5.1.1, 5.1.5 | ||

04-15 | Kruskal's algorithm | Book 5.1.2, 5.1.3 | ||

04-17 | Properties of minimum spanning trees | |||

04-19 | Homework review | |||

04-26 | Midterm exam, April 26, 10:00–12:00, room 1501 in E3-1 | |||

04-29 | Midterm review, 2-Approximation for TSP | |||

05-01 | Greedy algorithms for scheduling problems | notes by Jeff Erickson | ||

05-03 | More examples of greedy scheduling algorithms | |||

05-06 | Maximum independent set in interval graphs, Recursion without repetition, memoization, dynamic programming | notes by Jeff Erickson | ||

05-08 | Shortest path in DAG, Longest increasing sequence | Book 6.1, 6.2 | ||

05-10 | Edit distance | Book 6.3 | ||

05-13 | Knapsack | Book 6.4 | ||

05-15 | Matrix chain multiplication, optimal binary search tree | Book 6.5, Exercise 6.20 | ||

05-17 | No class (Buddha's birthday) | |||

05-20 | Reliable shortest paths, Floyd-Warshall all-pairs shortest paths, Independent Set in trees | Book 6.6, 6.7 | ||

05-22 | No class (Spring festival) | |||

05-24 | Huffman coding, Greedy set cover | Book 5.2, 5.4 | ||

05-27 | Lower bounds, decision trees | notes by Jeff Erickson | ||

05-29 | Adversary arguments | notes by Jeff Erickson | ||

05-31 | Reductions: Unique, MinIndSet, MaxClique, VertexCover | notes by Jeff Erickson 29.8, 29.9 | Book 7.1.3 box on reductions, Book 8.2, 8.3 | |

06-03 | Homework review | |||

06-05 | Reductions: Hamiltonian path to Hamiltonian cycle, Hamiltonian cycle to TSP, Vertex cover to Hamiltonian cycle | Jeff's notes 29.11 | Book 8.3 | |

06-07 | No class (Bridge holiday) | |||

06-10 | Reduction: Circuit-SAT to 3-SAT, 3-SAT to IndSet, Hamiltonian Cycle to Circuit-SAT | Jeff's notes 29.7 | ||

06-12 | P and NP, NP-hardness, NP-completeness | |||

06-14 | Question hour | |||

06-21 | Final exam, June 21, 10:00–12:00, room 1501 in E3-1 |

There will be one programming homework in this course. Programming can be done in most major imperative programming languages, such as Java, C, C++, Scala, or Python. Programming projects are submitted using an electronic submission server.

There will also be several small theoretical homework assignments, where you can test your understanding of the course material. You will have about one week to complete one assignment and they can be turned in in either Korean or English. Homeworks 1, 2, 3 are checked by the TAs, but not graded and do not count for the final grade. Homeworks 4 and following are graded and will count for the final course grade.

Homeworks must be submitted on paper in the homework box next to room 403 in the new IT Building (N1).