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:
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 in building E11
Schedule: Tuedays and Thursdays, 17:30am to 19:00 KST
Language: English only (except for students discussing in KLMS)
Teaching Assistants: 임동현 (head) Makenov Arnur (head)
Hyeonguk Ryu, Jaejun Lee, Jihoon Hyun, Kyounga Woo, Minjae Park, Mukhtar Kussaiynbekov, Seungjin Baek, Taeyoung Kim, Yeonghun Kim, Yoonsung Choi
Office hours: online
Quiz: On randomly selected sessions we will perform a short online quiz.
Grading: Only Pass/Fail, depending on Homework 30%, Quizzes+Attendance 10%, Midterm exam 30%, Final exam 30%.
Retakers admitted to improve grades C-,D,F; not to improve grades C0 and C+.
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.
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.
For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course.