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)

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.

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

• 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.

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/Quantiles
   • 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
   • 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

• 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