Data Structures (CS206A)

Fall Semester 2015

This is an archived page with the materials of my Data Structures course when I taught it using Scala.

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:

Programming language

In this course we will use the Scala programming language.

In my experience, students develop a style of programming in their first programming language. They find it difficult to learn a different style later, even if they switch to a different language. This means that students should start early to use a modern language that encourages writing clean and elegant code, and supports a good object-oriented and functional style.

We will therefore use Scala in this course. Scala is already a quite successful language for server programming and is slowly replacing Java in many companies. Scala is also starting to be used for web programming (where it is compiled into Javascript), especially for web applications that work together with a server written in Scala. Knowing Scala will also make it much easier for you to learn modern languages like Swift (for iOS and MacOS development) or Kotlin (for Android development), as you will recognize many features from Scala in those languages.

While it may be useful for you later to know Scala, most students will have to learn C++ and/or Java later during their studies—but I believe that after getting programming practice in Scala, they will be able to write better code in those languages as well.

Note that CS206 is not a course in a programming language. We will spend little time to talk about Scala. You are expected to pick up the rest by yourself, for instance using my tutorials.

I have collected the Scala documentation that you will need.

Course information

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

조재형, 이진서.


The class meets Monday and Wednesday from 10:30 to 11:45 in room 111 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%).

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 21 from 9:00 to 11:45 in our normal classroom (room 111 in N1).

The final exam is on December 16 from 9:00 to 11:45 in our normal classroom (room 111 in N1).


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 and lab hour

Our TA is offering an office hour as follows:

  • Wednesday afternoon from 16:00 to 17:30
  • Thursday evening from 20:00 to 21:30.
The office hour takes place in room 403 in building N1.

If you have difficulty doing your project alone, bring your laptop to the office hour and work on your homework projects there, while TAs are around to help you.


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 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/Tutorial
08-31 Introduction, basic Scala introduction, basic scala, objects tutorial 1, tutorial 2
09-02 Classes and singleton objects, compiling compiling code tutorial 3, tutorial 4, tutorial 5, tutorial 6, tutorial 7
09-07 Growing arrays efficiently code
09-09 Abstract Data Types, Stack ADT slides code notes
09-14 Recursion: printInt, factorial, Fibonacci slides code notes, tutorial number representations
09-16 Recursion: Towers of Hanoi, recursive-descent parsing slides code tutorial 8, tutorial 9, notes
09-21 Recursive-descent parsing, Stack frames, the runtime stack slides code
09-23 Exceptions, flood fill code notes
09-28 No class (Chuseok)
09-30 Queues, ADTs and implementations, stack implementations FixedStack, GrowStack, LinkedStack, circular buffers for queues queue slides, adt slides queue code, adt code
10-05 Immutable linked lists, Scala lists slides code notes
10-07 Mutable lists: singly-linked, with fast append, doubly-linked lists, sentinels slides code
10-12 The Josephus problem, Algorithm analysis slides code notes
10-14 Asymptotic analysis, Big-Oh notation
10-21 Midterm exam, October 21, 9:00–11:45
10-26 Linear search and binary search: correctness, iterative version, loop invariants; tail recursion; pattern matching slides code notes
10-28 Recursive functions on lists, sorting problem, insertion sort, selection sort slides code notes
11-02 Bubble sort, Merge sort, Quick sort, recursion trees
11-04 Maps and Sets slides code
11-09 Hashing I slides code notes
11-11 Hashing II
11-16 No class (business trip)
11-18 Trees, expression trees slides code notes
11-23 Rank trees slides code notes
11-25 No class (KAIST closed for interviews)
11-30 Data type priority queue, binary heaps, Heapsort slides code notes
12-02 Binary search trees slides code notes
12-07 AVL trees slides code
12-09 AVL implementation, other search trees
12-16 Midterm exam, December 16, 9:00–11:45

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.

Practice problems

These are practice problems, both theoretical exercises and programming problems, that you can use to practice the material from the class. We will review some of the problems during the class.