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

tba.

Lectures

The class meets Wednesday and Friday from 10:30 to 11:45 in room 201 in building N1. 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.

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

Piazza

This term we will be using Piazza for class announcements, discussion, and asking questions.

Here is our Piazza class page.

You are responsible for checking the announcements on our Piazza class page regularly (if you make a Piazza account and enroll for the course, announcements will be mailed to you automatically.)

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.

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 electronic submission server. The deadline is at midnight on the evening of the deadline day.