Data Structures (CS206C)

Fall Semester 2015

This section of CS206 is for non-major students only.
You cannot register for this section if your major is 전산학부, 전기전자학부, or 무학과.

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).

Course information

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

우성필, 송현지.

Lectures

The class meets Tuesday and Thursday from 10:30 to 11:45 in room 1101 in building E3-1. Lectures are given in English.

Grading policy

Students must submit all programming homeworks.

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 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).

Syllabus

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 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 TAs are offering an office hour every day from Monday to Thursday, as follows:

  • Monday, 18:30 to 20:00 in room 401 (Hyunji Song)
  • Tuesday, 18:30 to 20:00 in room 404 (Sungpil Woo)
  • Wednesday, 18:30 to 20:00 in room 401 (Hyunji Song)
  • Thursday, 18:30 to 20:00 in room 404 (Sungpil Woo)

You can bring your laptop to the office hour to work on your homework projects there, while a TA is nearby to help you.

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 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.

Textbook and lecture notes

I will loosely follow the book:

Rance D. Necaise, Data Structures and Algorithms using Python. Wiley 2011.

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.

Course progress

The material covered in the lectures so far:

Date Topic Slides Code Book
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-10 Review
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-24 Review
11-26 No class (Freshmen interviews)
12-01 Rank trees slides code
12-03 Binary search trees slides code 14.1
12-08 AVL trees slides 14.3
12-10 AVL trees
12-17 Final exam, December 17, 9:00–11:45, in room 1501 in E3-1

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 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.