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:
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.
조재형, 이진서.
The class meets Monday and Wednesday from 10:30 to 11:45 in room 111 in building N1. 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 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 |
Our TA is offering an office hour as follows:
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 @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:
| 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 | |||
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.
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.