Introduction to Algorithms (CS300) in Spring 2021 at KAIST's School of Computing

All Computer Science is based on the concept of an efficient algorithm: a finite sequence of primitive instructions that, when executed according to their well-specified semantics, provably provide a mechanical solution to the infinitely many instances of a complex mathematical problem within a guaranteed number of steps of least asymptotic growth. We thus call these the 'virtues' of Theoretical Computer Science:

  • full and unambiguous problem specification
  • formal semantics of operational primitives
  • algorithm design (as opposed to 'programming')
  • and analysis (correctness, asymptotic cost)
  • with proof of asymptotic optimality.

We will learn all about important basic algorithms and their analysis. Their practical impact is demonstrated in selected implementations.

Lecturer: Martin Ziegler

Lectures: online via Zoom classroom #1501 in building E3-1

Schedule: Tuedays and Thursdays, 9:00am to 10:15

Language: English only (except for students discussing in KLMS)

Teaching Assistants: 이현우 (head), 임동현, 황지만 , 김영훈, 김연수, 최재훈, 최홍규

Office hours: TBD

Quiz: On randomly selected sessions we will perform a short online quiz.

Grading: The final grade will (essentially) be composed as follows: Homework 30%, Quizzes 10%, Midterm exam 30%, Final exam 30%.

Recommended background: CS204 (Discrete Mathematics), CS206 (Data Structures)

Philosophy: Education is a Human Right, not a competition. This course aims beyond knowledge for the second and third level of Bloom's Hierarchy of cognitive learning.

Homework/Assignments:

Receptive learning and reproductive knowledge do not suffice for thorough understanding. Hence, for students' convenience, we will regularly offer homework assignments, both theoretically and practically; and encourage working on them by having a random selection of them enter into the final grade.
Submit your individual handwritten solutions to theoretical problems in due time into one of the homework submission boxes; and the programming assignments in ELICE

Late homework submissions (until 7pm) will receive a 50% penalty.
Copied solutions receive 0 points and personal interrogation during office/claiming hours.
Cheating during the exam results in failed grade F.
You are to sign and submit a pledge of integrity with your first written homework solution.

  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (3rd Edition), MIT Press (2009).
  • Donald Knuth: The Art of Computer Programming, Volume 1 Fundamental Algorithms
  • Dasgupta, Papadimitriou, Vazirani: Algorithms, McGraw-Hill (2006).
  • Kleinberg, Tardos: Algorithm Design, Pearson (2006).
  • Vöcking, Alt, Dietzfelbinger, Reischuk, Scheideler, Vollmer, Wagner: Algorithms Unplugged, Springer (2011).
  • M. Sipser: Introduction to the theory of computation, Boston (1997)

For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course.

    • Virtues of Computer Science:
    • Problem specification
    • Algorithm design
    • Asymptotic analysis
    • Optimal efficiency
    • Operational primitives
    • Recurrences and the Master Theorem
    • Polynomial Multiplication: Long, Karatsuba, Toom, Cook
  1. Searching (pdf,ppt)
    • Linear Search
    • Binary Search
    • Uniqueness
    • Hashing
    • Median/Quantiles
    • 1D Range Counting
  2. Sorting (pdf,ppt)
    • Bubble Sort
    • Selection Sort
    • Insertion Sort
    • Merge Sort
    • Quicksort
    • Linear-Time Median
    • Optimality of Sorting
    • Counting Sort
    • Radix Sort
  3. Graphs (pdf,ppt)
    • Recap on Graphs: un/directed, weighted
    • Connectedness
    • Shortest Paths: single-source, all-pairs
    • Minimum Spanning Tree: Prim, Kruskal
    • Max-Flow: Ford-Fulkerson, Edmonds-Karp
    • Max. bipartite matching
    • Min-Cut
  4. Strings (pdf,ppt)
    • Terminology
    • Pattern matching: Knuth-Morris-Pratt
    • Longest Common Substring
    • Edit Distance: Wagner-Fischer
    • Parsing: Cocke-Younger-Kasami
    • Huffman Compression
  5. Paradigms (pdf,ppt)
    • Divide and Conquer
    • Dynamic Programming
    • Greedy
    • Backtracking
    • Branch and Bound
  • homework assignment #0 and honor code will be uploaded here
  • Due to the large number (>200) of students enrolled, we unfortunately cannot answer questions by email.
    Instead please use the KLMS Bulletin Board or visit the TAs during their office hours.
  • We use KAHOOT!, so please install the app on your Android or Apple smartphone