In this course you will improve your programming skills, will learn to design, use, and implement abstract data types, and learn about a number of fundamental standard data structures and algorithms.
The following is a list of topics that we will cover in this course:
This course will use the Python programming language.
하대근, 이태경, 김태영, 김현섭.
The class meets Wednesday and Friday from 10:30 to 11:45 in classroom #1 (room 1101) in building E3-1. Lectures are given in English.
Students must submit all programming projects.
The final grade will then be composed as follows (small changes reserved):
Attendance will be taken in nearly every class. If you miss at most 4 lectures, you receive 10 attendance points. For 5 missed lectures, you receive 9 attendance points, and so on. For 14 or more missed lectures you receive no attendance points.
Going to a conference, workshop, doctor, interview, is no excuse for missing the class — you can use the four free missed classes for this.
There will be a midterm and a final exam.
The midterm exam is on October 18 from 9:00 (am) to 12:00 (noon) in the joint classroom (room 1501 in E3-1).
The final exam is on December 1 from 9:00 (am) to 12:00 (noon) in the joint classroom (room 1501 in E3-1). Note that this is not during the exam week.
Here is a rough list of what we will cover in each week of the semester.
|Week 1||Introduction, Reminder on references and objects|
|Week 3||Recursive descent parsing, stacks, queues|
|Week 4||Collection classes, iterators|
|Week 5||Linked lists|
|Week 6||Algorithm analysis and Big-Oh notation|
|Week 7||Binary search, Selection Sort, Insertion Sort, Bubble Sort, Quick Sort, Merge Sort|
|Week 8||Midterm exam|
|Week 9||Trees, expression trees, rank trees|
|Week 10||Simulations, Priority Queues, Heaps|
|Week 11||Binary Search Trees, AVL-Trees|
|Week 12||234-Trees and Red-Black trees|
|Week 13||Union-Find data structure|
|Week 14||Hash tables|
|Week 15||Lower bounds, course review|
|Week 16||Final Exam|
Our TA is offering an office hour as follows:
If there is something you don't understand about class or you have difficulties while doing the project, don't be afraid to visit the office hour!
Class announcements will be made on KLMS.
For asking questions and discussion the course material, however, we will be using Piazza.
Here is our Piazza class page.
If you do not understand something, it is important that you ask questions. Piazza allows you to ask questions and get answers from the instructor, the teaching assistants, and your classmates. You can ask questions anonymously, so don't be shy and ask!
Both Korean and English are acceptable on Piazza :-). You make it easier for me if you write in English, but if the TAs can answer your question, then Korean is just fine.
To ask questions, you need to register on Piazza and enroll as a student for CS206. To do so, go to the CS206 enrollment page. Select "Join as student". You will then need to use your KAIST email address (ending with @kaist.ac.kr) to create an account.
We do not use a textbook. The available textbooks are all very long (700 pages) and I don't believe it is useful for students to read 30 pages in a textbook after each class. Textbooks also contain a lot of pages with code, and since I provide my own examples and code, you can follow my class better if you read my code (and I find it easier to read code on a computer than on paper).
Short lecture notes about some topics, course slides, and example code will be available below under Course progress.
The material covered in the lectures so far:
|08-30||Introduction, recursion||introduction, recursion||code||notes|
|09-01||Towers of Hanoi, Indirect recursion, recursive-descent parser||calculator||code||notes|
|09-06||Objects & Classes||objects, classes||notes|
|09-08||Arrays & Python lists||slides||code||notes|
|09-13||Abstract Data Types||slides||code||notes|
|09-20||No class (Business trip)|
|09-22||No class (POSTECH-KAIST competition)|
|09-27||Sets & Maps||sets, maps||sets, maps|
|09-29||Storing multi-dimensional data, Flood-fill||multi-dim, flood fill||multi-dim code, flood-fill code||notes|
|Midterm week: Exam on 10-18, 9:00 (am)–12:00 in 1501|
|10-27||Linear search, binary search||slides||code||notes|
|11-01||No class (Business trip)|
|11-03||Sorting||slides, more slides||code, more code||notes|
|11-15||ADT Priority queue, binary heaps||slides||code||notes|
|11-17||Binary search trees||slides||code||notes|
|11-29||234-trees, red-black trees||slides|
|12-01||Final exam 9:00 (am)–12:00 in 1501|
|12-06||No class (Student interviews)|
|12-08||Exam review, wrapup|
There will be several programming projects in this course. You will have 1 to 3 weeks to complete a project. All programming projects are submitted using the submission server. The deadline is at midnight on the evening of the deadline day.