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.
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.
Lectures are Tuesday and Thursday at 2:55-4:10pm in Olin 255. There are no recitations.
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).
All titles are on reserve in the Engineering Library, Carpenter Hall.
Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press, 1990.
Data structures
Java
Additional materials will be posted periodically on the web.
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]
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 |
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.
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.
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.
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 |
Subject to change. References [ ] are to chapters of CLR.