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 wellspecified 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
Lectures: online via Zoom classroom #1501 in building E31
Schedule: Tuedays and Thursdays, 9:00am to 10:15
Language: English only (except for students discussing in KLMS)
Teaching Assistants: 이현우 (head), 임동현, 황지만 , 김영훈, 김연수, 최재훈, 최홍규, Arnur Makenov
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+Attendance 10%, Midterm exam 30%, Final exam 30%.
Midterm: April 20
Recommended background: CS204 (Discrete Mathematics), CS206 (Data Structures)
Philosophy: 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.
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.
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, McGrawHill (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.
Synopsis/Syllabus:

 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

 Linear Search
 Binary Search
 Uniqueness
 Hashing
 Median/Quantiles
 1D Range Counting
 2D Range Counting

 Bubble Sort
 Selection Sort
 Insertion Sort
 Merge Sort
 Quicksort
 LinearTime Median
 Optimality of Sorting
 Counting Sort
 Radix Sort
 Sorting in Parallel

 Hardware vs. Mathematical
 Logical Structures = Abstract Data Types
 Basic: Boolean/Bit, Integer
 Derived: Array, Stack, Queue
 Linked Data Structures
 (Balanced) Search Trees
 AVL Trees

 Recap on Graphs: un/directed, weighted
 Connectedness
 Shortest Paths: singlesource, allpairs
 Minimum Spanning Tree: Prim, Kruskal
 MaxFlow: FordFulkerson, EdmondsKarp
 Max. bipartite matching
 MinCut

 Terminology
 Pattern matching: KnuthMorrisPratt
 Longest Common Substring
 Edit Distance: WagnerFischer
 Parsing: CockeYoungerKasami
 Huffman Compression

 Divide and Conquer
 Dynamic Programming
 Greedy
 Backtracking
 Branch and Bound
ELearning:
 homework assignment #0 and honor code will be uploaded here
 Due to the large number (>150) 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.