CIS 313, Introduction to Data Structures

CIS 313 Fall 2003

Introduction to Data Structures

[ Assignments | CIS | Links | News | Grades ]

Prerequisites: Math 231-232, CIS 210-212.
CIS 313
- MWF 11:00-11:50
- room 142 Straub
- crn 11210
CIS 323
- Tuesday or Thursday, 8:30-9:50am
- room 107 Esslinger
- crn 11214 or 11215
- See the CIS323 homepage for more information.
Instructor: Chris Wilson
- 326 Deschutes, 346-3412
- office hours MW 3-4, F 1-2. Frequent availability UH 2-3:30, F 3-3:30.
- email cwilson@cs.uoregon.edu
GTF: Peter Boothe
- 254 Deschutes, 346-4436
- office hours: MU 1-2:30, H 1-2
- email peter@cs.uoregon.edu

News: Keep an eye on the course news for miscellaneous announcements.

Sample Solutions: These will be linked through the assignments page.

Evaluation:

There will be five or six written assignments.
There will be one midterm on Monday, November 10.
The final will be held on Monday, December 8, at 10:15am.
Some extra credit is available.

The approximate weighting of the work done is

Homework Assignments	45%
Midterm	17%
Final Exam	38%

Text: Michael Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, 2nd Edition, Wiley, 2001. The text has a homepage.

Supplemental Reading:

Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press/McGraw-Hill, 1990.
Weiss, Data Structures and Problem Solving using Java, Addison-Wesley, 1998.
Knuth, The Art of Computer Programming, vol.I, Addison-Wesley 1975.

Tentative Syllabus

Date	Lecture Topic	Reading	Comments

Sep 29	introduction	3.1, 3.2
Oct 1	math background	3.3, 3.4, appendix A
Oct 3	algorithm analysis	3.4, 3.5

Ocy 6	asymptotic notation	3.6, 3.7	last day to drop without W
Oct 8	stacks and queues and deques	4.1-4.4	last day to add class
Oct 10	uses of stacks

Oct 13	trees	6.1-2
Oct 15	binary trees	6.3-4
Oct 17	BSTs	9.1

Oct 20	path lengths
Oct 22	AVL trees	9.2
Oct 24	rotations	9.2

Oct 27	(2,4) trees	9.3-4
Oct 29	RB trees	9.5
Oct 31	RB insertion	9.5

Nov 3	RB deletion	9.5
Nov 5	B trees	9.6
Nov 7	priority queues and heaps	7.1-3

Nov 10	midterm
Nov 12	heap operations	7.3
Nov 14	heapsort		last day to drop with W

Nov 17	mergesort	10.1
Nov 19	recurrence relations	appendix A
Nov 21	quicksort	10.3

Nov 24	quicksort is quick	10.3
Nov 26	lower bounds	10.4
Nov 28	thanksgiving sort

Dec 1	bucket sort	10.5
Dec 3	order statistics	10.7
Dec 5	final review, course evals

Dec 8	final exam, 10:15-12:15

Late policy for 313: All assignments are due by 5:00pm of the stated due date, though it is much safer to turn them in at class time. Assignments will be accepted for up to three days past the due date with a penalty of 10% per (calendar) day.

Grading: Please note that work done correctly and meeting the specifications of the assignment will receive a base score of about 80%. Higher scores will be reserved for work that is more complete and/or especially elegant.

Academic Honesty: C'mon, do we really need to remind you?