Introduction to Algorithms (CS300) in Fall 2022 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 'virtues' of Theoretical Computer Science:

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

We will learn all about important basic algorithms and their analysis, as well as the difference to heuristics or programs/code. Their practical impact is demonstrated in selected implementations.

Lecturer: Martin Ziegler

Lecture location: E11 Terman Hall / online

Schedule: Tuesdays and Thursdays, 10:30am to 12:00 KST

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

Teaching Assistants: Lwam Araya, Sookyung Han, Sujeong Lim, Abbas Mammadov, Jinyoung Oh, Mingi Shin, Biniyam Aschalew Tolera

Office hours: TBD

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

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

Philosophy/Pedagogy

Education is a Human Right, not a competition.

This course aims beyond, and takes for granted students mastering, the first level of Bloom's Hierarchy of cognitive learning.

Each chapter (see #syllabus) below deliberately starts very easy and then grows to more involved aspects and ends with cross promotion to advanced topics covered by separate lectures.

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

Academic Honesty:

Late homework submissions (until 7pm) will receive a 50% penalty.
We do not accept late submissions.
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.

Literature:

  • 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)
  • Peter Brass: Advanced Data Structures (2008)

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

Synopsis/Syllabus:

  1. Introduction (pdf,ppt)
    • Hierarchy of Abstraction
    • Virtues of Computer Science:
    • Problem specification
    • Algorithm design
    • Asymptotic analysis
    • Optimal efficiency
    • Operational primitives
    • Five algorithms for computing Fibonacci Numbers
    • Recurrences and the Master Theorem
    • Polynomial Multiplication: Long, Karatsuba, Toom, Cook
  2. Searching (pdf,ppt)
    • Linear Search
    • Binary Search
    • Uniqueness
    • Hashing
    • Median/Order Statistics
    • Approximate/Linear-Time
    • 1D Range Counting
    • 2D/3D Range Counting
    • Range Reporting
  3. Sorting (pdf,ppt)
    • Bubble Sort
    • Selection Sort
    • Insertion Sort
    • Merge Sort
    • Quicksort
    • Linear-Time Median revisited
    • Optimality of Sorting
    • Counting Sort
    • Radix Sort
    • Sorting in Parallel
  4. Data (pdf,ppt)
    • Hardware vs. Mathematical
    • Logical Structures = Abstract Data Types
    • Basic: Boolean/Bit, Integer
    • Derived: Array, Stack, Queue
    • Linked Data Structures
    • (Balanced) Search Trees
    • AVL Trees
  5. 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
  6. Strings (pdf,ppt)
    • Terminology
    • Pattern matching: Knuth-Morris-Pratt
    • Longest Common Substring
    • Edit Distance: Wagner-Fischer
    • Parsing: Cocke-Younger-Kasami
    • Huffman Compression
  7. Paradigms (pdf,ppt)
    • Divide and Conquer
    • Dynamic Programming
    • Greedy
    • Backtracking
    • Branch and Bound
  8. Randomization (pdf,ppt)
    • Un/Reliability
    • Sources of Randomness
    • Las Vegas vs. Monte Carlo
    • Primality Testing
    • Errors and Amplification
    • Blackbox Polynomial Test
    • Schwartz-Zippel Lemma

E-Learning:

  • homework assignment #0 and honor code will be uploaded on KLMS.
  • KLMS
  • ELICE
  • YouTube
  • MIT OpenCourseware
  • Due to the large number (>300) 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