CS410: Data Structures, Summer 1998

Last updated: August 11, 12:20PM.

Course Staff

Instructor	TA	TA
Dan Grossman	Jiesang Song	Parag Tole
danieljg@cs.cornell.edu	js104@cornell.edu	parag@cs.cornell.edu
Upson 4132 (Phone 5-1179)	CSUGLAB	Upson 4162 (Phone 5-2219)
MoTuWeThFr, 2:30-4:00PM or appointment	SuMoTuWeTh, 7:00-8:30PM	TuTh, 9:30-11:30AM

Academic integrity policy for the course

Homeworks:

Prelim and Solution

Final Exam and Solution

Books on reserve in the Engineering Library.

Lecture Outlines

These are not a substitute for lecture notes. They contain no pictures and few formulas. They are much less than what was said in class. Anything in the future is subject to change.

1	29 June	Introduction, ADTs, Stacks, Asymptotic Notation
2	30 June	Asymptotic Notation, Induction, Recurrence Relations
3	1 July	Arrays, Linked Lists (single, double), Queues
4	2 July	Sentinels, Object-oriented data definitions, Exceptions
5	6 July	Polymorphism, Introduction to Trees, Binary Search Trees
6	7 July	Red-black trees
7	8 July	Red-black deletion, augmenting data structures, using splay trees
8	9 July	2-3 trees
9	10 July	B-Trees, Programming: Variations on Homework 2
10	13 July	Heaps
11	14 July	Finish Heaps, Start Hashtables
12	15 July	Hashing
13	16 July	Open Address Hashtables
	17 July	PRELIM
14	20 July	Prelim Solution, Amortization
15	21 July	Union-Find
16	22 July	Finish Union-Find, Start Sorting
17	23 July	Sorting: Selection, Insertion, Heap, Merge
18	24 July	Finish mergesort, Quicksort
19	27 July	Quicksort wrapup, lower bound on comparison sort, order statistics
20	28 July	Median, Linear Time Sorts, Radix Sort
21	29 July	Tries
22	30 July	Introduction to Graphs, Breadth-First-Search
23	31 July	BFS Correctness, Depth-First-Search
24	3 August	Topological Sort, Strongly-Connected Components
25	4 August	Minimum Spanning Trees
26	5 August	Single-source shortest path
27	6 August	Running time for MST and SSSP, Algorithms for All-pairs shortest paths
28	7 August	Course review, perspective, and evaluation

Quizzes

Programming

You should do your programming in Java, in the CSUGLAB, using Visual J++.

CSUGLAB generic information.
Getting started with Visual J++.
The Java Tutorial Lots of small well-organized lessons from the folks who wrote the language.
When learning Java, keep in mind the following topics will not be used in this class: applets, GUI, threads (and synchronization), user-defined packages, internationalization, serialization, javadoc, jar, and probably a bunch of others. (Java has a lot of features.) Focus on the core constructs, classes, inheritance, static vs. instance, exceptions (covered in lecture), etc.

Note: The old course web pages (see below) also have some introductory Java information.

Grading (subject to change):

15 Quizzes	15%
8 Homeworks	35%
1 Prelim	25%
1 Final	25%

Other Information

Automatic web update notification: If you would like to receive email every time this page gets updated, email dci1@cornell.edu with the subject cs410-notify-on. To cancel this, make the subject cs410-notify-off. Thanks to Dan Ilut (a member of the class) for volunteering this service. Notes:
- The program doesn't notice changes to other files on the course site. We'll try to remember to update this page when other pages are updated, though.
- You are ultimately responsible for checking the web page. Nobody else will take responsibility if you over-rely on this program for some reason.
Textbook: Introduction to Algorithms, Cormen, Leiserson, Rivest, 1990.
Note this text was not used the previous two semesters, but has been used many times for this course.
Lecture: 11:30-12:45, Thurston 203 (moved from Upson 211), MoTuWeThFr, June 29 - August 7, except July 3
Prelim: In class on July 17
Final Exam: August 10, 10:30-12:30
Old 410 homepages: (Keep in mind the last two semesters used a different textbook.)