What is CS410 About?

Most programs manipulate data. Data structures organize data so as to allow efficient storage, access, and modification. Choosing the right data structure can often make an enormous difference in the efficiency of your program. It can also impact the reusability of your code. The purpose of this course is to introduce you to the issues involved in the choice of good data structures. You will gain experience with the use of common data structures and learn how to design your own. These skills will serve you well in your future programming tasks.

We will start with a comprehensive study of the basic data structures that have proven to be the most versatile: stacks, queues, arrays, lists, heaps, trees, hashtables, graphs. We will study the efficient implementation of these objects and their application in various contexts. We will also focus on abstract data types and their specification and implementation. This is especially important in an object-oriented programming environment. In the latter part of the course, we will take a brief look at some data structures that have been developed for various specialized applications.

Although closely related, the design and analysis of efficient algorithms is not the main focus of this course; that is more the purpose of CS482. However, good data structures and efficient algorithms often go hand in hand, so we will spend some time on the basics of asymptotic analysis.


Reaching Us

The best way to reach the course staff is by posting questions or comments to the CS410 newsgroup cornell.class.cs410. We will try to respond to questions within one working day. If you have never used newsgroups before, here are instructions.

You can also reach the course staff by sending email to cs410@cs.cornell.edu.


Who We Are


When We Meet

Lectures are Tuesday and Thursday at 2:55-4:10pm in Olin 255. There are no recitations.


Office Hours


Consulting Hours

Consultants will be on duty in the CSUGLab during evening hours prior to programming assignment due dates.  For programming assignment 4, consultants will be on duty 7-10pm on Monday 11/29 (Ben), Tuesday 11/30 (Pat), and Wednesday 12/1 (Kang-Hoe).


Textbook

All titles are on reserve in the Engineering Library, Carpenter Hall.

Required

Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press, 1990.

Recommended

Data structures

Sedgewick, Algorithms in C, 1998.
This was the course textbook in F97 and S98.
Standish, Data Structures in Java.
First four chapters are a fairly good review of some background for the course. The rest of the book is generally a more basic coverage than we will take. A good place to look if you are lost. Appendix B is a gentle but sufficiently thorough explication of O-notation.
Tarjan, Data Structures and Network Algorithms.
Concise presentation of many topics, including splay trees, which are not in CLR.
Sedgewick, Algorithms in C++, 1992.
Sedgewick, Algorithms, 1988.
Aho, Hopcroft, Ullman, Data Structures and Algorithms, 1983.

Java

Horstmann and Cornell, Core Java 1.1, vol. 1.
Good starting place, used sometimes in CS211.
Horstmann and Cornell, Core Java 1.1, vol. 2.
Advanced Java features probably beyond our needs.
Flanagan, Java in a Nutshell.
Good quick reference.
Deital and Deital, Java: How to Program.
Lots of examples, starting from the very basic--you can probably skip the first five chapters.

Additional materials will be posted periodically on the web.


Software

The course programming language is Java. For program development, we recommend MS Developer Studio/Visual J++.  It is installed on the CSUGLab machines and is available at the Campus Store.  However, if you already have another Java program development environment installed on you own machine such as Metrowerks CodeWarrior, you are welcome to use that.

There are online quick introductions to MS DevStudio/Visual J++ and the Java language.   There will be two demo sessons in the CSUGLab in the first week of classes.   They will be at 7-8pm on 31 Aug and 2 Sep.  Please attend one of these if you are unsure about how to use the CSUGLab or MS DevStudio/Visual J++.

Some handouts in .pdf format will require Adobe Acrobat Reader. This is available free of charge from Adobe. [download Acrobat Reader]


Course Requirements

Students are responsible for all material in the assigned readings, as well as material covered in lectures. There will be four written homework sets, four programming assignments, two evening preliminary exams, and a final exam. A schedule is given below. Course grades will be based on a weighted combination of the written homework and programming assignments and exam scores.

40% Homework and programming assignments
30% Prelim exams
30% Final exam

Turning in Assignments

Written assignments should be turned in on the due date, either in lecture or with Karla Consroe in 4157 Upson. Karla will accept them up until the time she goes home, usually around 4:15pm. We will generally grade them that same evening. Do not turn them in to the undergrad office or the consulting office. No late assignments will be accepted, and there will be no extensions, except in dire circumstances.

Instructions for turning in programming assignments will vary.  Sometimes we will want to see printouts only (in which case the instructions above for written assignments apply); sometimes we will want you to submit your programs online in the CSUGLab.  Specific instructions will be given in the programming assignment.


Academic Integrity

The utmost level of academic integrity is expected of every student. Please read the CS Department's Code of Academic Integrity and adhere strictly to it and to the following course policies. If you are unsure about anything, please ask.

Prelims and final. Open book, open notes.

Written homework assignments. For the written homework assignments, you must work alone. You may collaborate with others in the class to the extent of formulating a general approach, but all such interactions must be verbal only. You must write up your solutions on your own, without any material from other students. In particular, you may not work from notes taken during collaborative sessions. It is never permissible under any circumstances to read the detailed solutions of other students or to share your own solutions with others. You may look at assignments and solutions from previous versions of the course that are available on the web. If you consult any sources outside the course materials, you must cite them explicitly.

Programming assignments. You may work jointly with one other person on the programming assignments. If you work with a partner, you must submit a single joint assignment with both names on it, and you will both receive the same grade. No more than two people may work together. You may consult other students in the class besides your partner to discuss high-level design decisions or to ask basic questions about the programming language or development environment, but it must not go beyond that. It is never permissible under any circumstances to read anyone else's code or to show your code to anyone else in the class. Take care not to leave files on the local disks of the machines in the lab. If you consult any sources outside the course materials, you must cite them explicitly.

A word to the wise. Much of the learning in this course comes from doing the homework and programming assignments. They are designed to make you think. In many cases the solution will not be obvious, but will require considerable thought.   It is a good idea to get an early start.  That way, there is ample time to resolve any difficulties you might encounter. There are many resources at your disposal, but you must allow yourself enough time to take advantage of them. The best way to avoid temptation is not to leave things until the last minute.


Public Lab Facilities

All students registered in CS410 are entitled to an account in the CS Undergraduate Lab (CSUGLab), 315/317 Upson. The machines in the CSUGLab will be equipped with all the necessary course software. If you are registered for CS410, a student account will be generated for you automatically. You may pick up your userid, password, and the door combination from Karla Consroe in 5147 Upson in person during business hours. Please bring a photo ID. Sorry, we cannot distribute this information by email for security reasons.

If you prefer to use your own machine, you can obtain MS Developer Studio/Visual J++ or MetroWerks CodeWarrior from the Campus Store.


Schedule

Please mark your calendars. The homework due dates below are subject to change; the exam schedule is written in stone. If you have a conflict, please notify us as soon as possible.

Thu 9/2 Homework 1 due
Tue 9/14 Programming assignment 1 due
Thu 9/23 Homework 2 due
Tue 10/5 Programming assignment 2 due
Wed 10/6 Prelim 1 review session (optional), 7:30-9:00pm, Kimball B11
Thu 10/7 Prelim 1, 7:30-9:00pm, Olin 155 (A-L), Olin 165 (M-Z)
Tue 10/12 Fall break--no class
Thu 10/14 Prelim 1 makeup, 7:30-9:00pm, Upson 215
Thu 10/21 Homework 3 due
Thu 11/4 Programming assignment 3 due
Wed 11/10 Prelim 2 review session (optional), 7:30-9:00pm, Kimball B11
Thu 11/11 Prelim 2, 7:30-9:00pm, Olin 155 (A-L), Olin 165 (M-Z)
Tue 11/18 Homework 4 due
Thu 11/25 Thanksgiving--no class
Tue 12/7 Programming assignment 4 due
Thu 12/9 Final review session (optional), 7:30-9:00pm, Kimball B11
Fri 12/10 Final exam, 3:00-5:30pm, Olin 155

Approximate Syllabus

Subject to change.  References [ ] are to chapters of CLR.

  1. Introduction & administrivia, asymptotic notation [2,3]
  2. Recurrence relations, the Master Theorem, amortization [4]
  3. ADTs and object-oriented data definitions, exceptions
  4. Stacks, queues, arrays, linked lists, trees [11]
  5. Priority queues, heaps [7]
  6. Binomial, Fibonacci heaps [20,21]
  7. Balanced trees, binary search [13]
  8. Red-black trees [14]
  9. Red-black deletion, augmenting data structures [15]
  10. Splay trees [handout]
  11. B-trees, 2-3 trees [19]
  12. Random treaps [handout]
  13. Tries [handout]
  14. Sorting: selection, insertion, heap, merge, quick [7,8,9]
  15. Lower bounds on comparison sort, linear time sorts, radix sort [7,8,9]
  16. Hashing [12]
  17. Open-address hashing, universal hashing [12]
  18. Graphs, adjacency matrices, adjacency lists [23]
  19. BFS, DFS, connected components [23]
  20. Topological sort, strongly-connected components [23]
  21. Single-source shortest path, Dijkstra's algorithm [25]
  22. All-pairs shortest path, Floyd-Warshall algorithm [26]
  23. Huffman trees, Lempel-Ziv compression [handout]
  24. Image compression [handout]
  25. Suffix trees, DNA sequencing [handout]