CIS 313, Introduction to Data Structures

CIS 313 Winter 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 107 Gilbert
- crn 22118
CIS 323
- Tuesday 10:00-11:50
- room 110 Willamette
- crn 22123
- See the CIS323 homepage for more information.
Instructor: Chris Wilson
- 326 Deschutes, 346-3412
- office hours MWF 2-3, or by appointment
- email cwilson@cs.uoregon.edu
GTF: Peter Boothe
- 254 Deschutes, 346-4436
- office hours: UH 1:30-2:30, W 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, Feb. 17.
The final will be held on Wednesday, March 19, 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

Jan 6	introduction	3.1, 3.2
Jan 8	math background	3.3, 3.4, appendix A
Jan 10	algorithm analysis	3.4, 3.5

Jan 13	asymptotic notation	3.6, 3.7	last day to drop without W
Jan 15	stacks and queues and deques	4.1-4.4	last day to add class
Jan 17	uses of stacks

Jan 20	no class - MLK Day
Jan 22	trees	6.1-2
Jan 24	binary trees	6.3-4

Jan 27	BSTs	9.1
Jan 29	path lengths
Jan 31	AVL trees	9.2

Feb 3	rotations	9.2
Feb 5	(2,4) trees	9.3-4
Feb 7	RB trees	9.5

Feb 10	RB insertion	9.5
Feb 12	RB deletion	9.5
Feb 14	B trees	9.6

Feb 17	midterm
Feb 19	priority queues and heaps	7.1-3
Feb 21	heap operations	7.3	last day to drop with W

Feb 24	heapsort
Feb 26	mergesort	10.1
Feb 28	recurrence relations	appendix A

Mar 3	quicksort	10.3
Mar 5	quicksort is quick	10.3
Mar 7	lower bounds	10.4

Mar 10	bucket and radix sort	10.5
Mar 12	order statistics	10.7
Mar 14	final review, course evals

March 19	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?