Data Structures (CS206A)

Fall Semester 2017

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.

Course information

Lecturer:
Otfried Cheong Office: E3-1 3434, Phone: 3542.
Teaching assistants

하대근, 이태경, 김태영, 김현섭.

Lectures

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.

Grading policy

Students must submit all programming projects.

The final grade will then be composed as follows (small changes reserved):

  • Programming projects (20%), Midterm (30%), Final (40%), Participation (10%).
Participation

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.

Exams

There will be a midterm and a final exam.

The midterm exam is on October 18 from 9:00 to 12:00 in the joint classroom (room 1501 in E3-1).

The final exam is on December 1 from 9:00 to 12:00 in the joint classroom (room 1501 in E3-1). Note that this is not during the exam week.

Syllabus

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 2 Recursion
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

TA Office hours

Our TA is offering an office hour as follows:

  • Monday evening from 18:30 to 20:00;
  • Thursday evening from 18:30 to 20:00.
The office hour takes place in room 402 in building N1.

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!

Piazza

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.

Textbook and lecture notes

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.

Course progress

The material covered in the lectures so far:

Date Topic Slides Code Notes
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-15 Stacks slides exceptions, stacks notes
09-20 No class (Business trip)
09-22 No class (POSTECH-KAIST competition)
09-27 Sets & Maps
09-29
Chuseok week
10-11
10-13
Midterm week: Exam on 10-18, 9:00–12:00 in 1501
10-25
To be continued …
11-29 No class (Student interviews)
12-01 Final exam 9:00–12:00 in 1501
12-06
12-08 Last lecture

Programming projects

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.