Introduction to Algorithms (CS300)

Spring Semester 2018

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.

Course information

Lecturer:
Otfried Cheong. Office: E3-1 3434, Phone: 3542.
Teaching assistants

Jiwon Park, Taegyoung Lee, Yoonsung Choi.

Lectures

The class meets Monday and Wednesday from 13:00 to 14:15. Lectures are given in English.

Grading policy

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

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

There will be a midterm and a final exam.

Syllabus

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

Piazza

Class announcements will be made on KLMS.

For asking questions and discussion the course material, however, we will be using Piazza.

Here is our Piazza class page.

If you do not understand something, it is important that you ask questions. Piazza allows you to ask questions and get answers from the instructor, the teaching assistants, and your classmates. You can ask questions anonymously, so don't be shy and ask!

Both Korean and English are acceptable on Piazza :-). You make it easier for me if you write in English, but if the TAs can answer your question, then Korean is just fine.

To ask questions, you need to register on Piazza and enroll as a student for CS300. To do so, go to the CS300 enrollment page. Select "Join as student". You will then need to use your KAIST email address (ending with @kaist.ac.kr) to create an account.

Text book and lecture notes

The class will mostly use the book Algorithms by Dasgupta, Papadimitriou, and Vazirani. The international edition is quite inexpensive, and there is also a Korean translation. 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.

Homework

There will be one or two programming homeworks in this course. Programming can be done in most major imperative programming languages, such as Java, C, C++, Scala, Kotlin, 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 must be submitted on paper in the homework box.