Introduction to Algorithms (CS300) in Fall 2018 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, as well as the difference to heuristics or programs/code. Their practical impact is demonstrated in selected implementations.

Lecturer: Martin Ziegler

Lectures: classroom #1501 in building E3-1

Schedule: Mondays and Wednesdays, 10:30am to 11:45

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

Teaching Assistants: 임동현, 박찬수, 박세원, 박지원, 이승우, 안남조, Talipov Anuar, Nguyen Viet Dung

Office hours: Wed 14:30-17:30 @ N1 404

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

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

Written midterm exam on Wednesday October 17 at 16h30 in E11 Terman Hall.
Written final exam on Wednesday December 5 at 10h30 in E3-1 #1501.
Final ELICE assignment due Monday, Dec.18 11am. 

Final/hw#8 claiming hour on Dec.18 at 11am in E3-1 #4443

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 (#4, #5, or #6), located in front of E3-1 1501; 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, 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.

Synopsis/Syllabus:

  1. Motivation
    • 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
  2. Searching (pdf,ppt)
    • Linear Search
    • Binary Search
    • Uniqueness
    • Hashing
    • Median/Quantiles
    • 1D Range Counting
  3. Sorting (pdf,ppt)
    • Bubble Sort
    • Selection Sort
    • Insertion Sort
    • Merge Sort
    • Quicksort
    • Linear-Time Median
    • Optimality of Sorting
    • Counting Sort
    • Radix Sort
  4. 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
  5. Strings (pdf,ppt)
    • Terminology
    • Pattern matching: Knuth-Morris-Pratt
    • Longest Common Substring
    • Edit Distance: Wagner-Fischer
    • Parsing: Cocke-Younger-Kasami
    • Huffman Compression
  6. Paradigms (pdf,ppt)
    • Divide and Conquer
    • Dynamic Programming
    • Greedy
    • Backtracking
    • Branch and Bound

E-Learning:

  • homework #0 in ELICE asks you to implement three algorithms for computing Fibonacci Numbers and is due by 10am on Sep.10
  • honor code + homework #1 are due in individual English handwriting by 10:25am on Sep.17
  • homework #2 in ELICE asks you to implement Karatsuba's Algorithm and is due by 23h59 on Sep. 26 10:25am on Sep. 28
  • homework #3 is due in individual English handwriting by 10:25am on Oct.4
  • homework #4 is due in individual English handwriting by 10:25am on Oct.24
  • homework #5 is due in individual English handwriting by 10:25am on Nov.5
  • homework #6 in ELICE asks you to implement the linear-time median and is due by 10:30am on Nov.14 16 (Friday)
  • homework #7 in ELICE asks you to implement Prim's Algorithm and is due by 10:30am on Nov.23 (Friday)
  • homework #8 is due in individual English handwriting by 10:25am on Dec.3
  • KLMS
  • Due to the large number (240) 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