In this course you will improve your programming skills, will learn about the most important abstract data types, learn to distinguish abstract data types from data structures that implement those data types, and will learn about a number of fundamental standard data structures and algorithms.
This section of the course uses the Python programming language. It is meant to be more accessible for students with little programming background, so that you can spend more time thinking about your algorithms and less time debugging. You can actually do all the programming exercises through your web browser, you do not even need to have Python installed on your computer. And—I know some students are worried about this—you are not competing with CS students in the grading of the course :-)
The following is a list of topics that we will cover in this course:
If you prefer to learn Java or Scala in CS206, please register for CS206A (which uses Scala) or CS206B (which uses Java).
The class meets Tuesday and Thursday from 10:30 to 11:45 in room 1101 in building E3-1. Lectures are given in English.
Students must submit all programming homeworks.
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 22 from 9:00 to 11:45 in room 1501 in the old CS building (Building E3-1) (opposite from our usual classroom).
The final exam is on December 17 from 9:00 to 11:45 in room 1501 in the old CS building (Building E3-1) (opposite from our usual classroom).
Here is a rough list of what we will cover in each week of the semester. (I'm going to adapt that to this special non-CS major class.)
|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 TAs are offering an office hour every day from Monday to Thursday, as follows:
You can bring your laptop to the office hour to work on your homework projects there, while a TA is nearby 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 CS206C 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.
I will loosely follow the book:
I bought it in the on-campus book store for 35,000 Won. Unfortunately, it is now out of stock.
While I like the choice of topics and the explanations of the book for this course, the book has too many mistakes. If you buy the book, you must download the Errata and fix the mistakes in your copy.
In the explanations the mistakes are not serious, but there are really unbelievable mistakes in the code example—it seems as if the code has never really been tried. This is no problem for us—we will only use example code written by me—but if you study the book further, you should not put too much trust into the code in the book.
I will upload all the slides used in the lectures, all the example code from the lectures, and some short lecture notes about selected topics. You can find them below under Course progress. Example code may also be available at elice.io.
The material covered in the lectures so far:
|09-01||Introduction, objects, reference, and the heap||Introduction, Objects|
|09-03||User-defined classes in Python||slides||code||Appendix D|
|09-08||Abstract Data Types, Exceptions||slides||code||1.1.2, 1.2, Appendix C|
|09-10||Python Lists and arrays||slides||code||2.1.1, 2.1.2, 2.2|
|09-15||How Python Lists insert, delete, extend, and slice; two-dimensional arrays, Sets||slides||code||2.2.3, 2.2.4, 2.2.5, 2.3.2, 3.3.2|
|09-17||Sets and Maps||set slides, map slides||set code, map code||3.1.1, 3.1.3, 3.2.1|
|09-22||Recursion and recursion fairies||slides||code||10.1, 10.2|
|09-24||Recursion: Towers of Hanoi and Minesweeper, Algorithm Analysis||slides||code||10.4.2, 4.1|
|09-29||No class (Chuseok)|
|10-01||Algorithm analysis, Linear search||4.1.1, 4.1.2, 5.1.1|
|10-06||Binary search, Sorting, Selection sort||search slides, sort slides||search code, sort code||5.1.2, 10.4.1, 5.2.2,|
|10-08||Insertion sort, Bubble sort, Set implementation using sorted list||code||5.2.3, 5.4|
|10-13||Merging sorted lists, Mergesort and Quicksort||slides||code||5.3.2, 12.1, 12.2|
|10-15||Review and Question Hour|
|10-22||Midterm exam, October 22, 9:00–11:45, in room 1501 in E3-1|
|10-27||Linked lists (Singly-linked lists)||slides||code||6.1, 6.2|
|10-29||Singly-linked lists with fast append, Doubly-linked lists, sentinels, Josephus problem, Stack ADT||6.4, 9.1, 7.3.1|
|11-03||Stack implementations, runtime stack, Queue ADT||slides||code||7.1, 7.2, 8.1, 8.2.1, 8.2.3,|
|11-05||Hash tables||slides||code||11.2, 11.3, 11.2.1, 11.2.3, 11.4|
|11-12||No class (business trip)|
|11-17||Trees||slides||code||13.1, 13.2, 13.3, 13.6|
|11-19||Priority type ADT and binary heaps, Heapsort||slides||code||13.4, 13.5|
|11-26||No class (Freshmen interviews)|
|12-03||Binary search trees||slides||code||14.1|
|12-17||Final exam, December 17, 9:00–11:45, in room 1501 in E3-1|
There will be several programming projects in this course. You will have 1 to 3 weeks to complete a project. All programming projects are done through your web browser—you do not even need to install Python on your computer :-)
The deadline is at midnight on the evening of the deadline day.
All programming projects are done using elice.io.
To use elice.io, you first need to make an account using your student id on the registration page. Each application needs to be approved, so this may take a while. You can then sign in on elice.io. You should enroll in the course "Data Structures", and then you can open this course.
In Week 1, we provide a "sandbox", where you can experiment with arbitrary Python code. For instance, you can try out the code from the class.