CIS 313 Introduction to Data Structures

Fall 2006

[ Assignments | CIS | Links | News | Grades ]

• Prerequisites: Math 231-232, CIS 210-212.

• CIS 313
  • MWF 12:00-12:50
  • room 475 McKenzie
  • crn 17901

• Instructor: Chris Wilson
  • 326 Deschutes, 346-3412
  • office hours 2:00-3:30 MWF
  • email cwilson@cs.uoregon.edu

• GTF: Peter Boothe
  • 254 Deschutes, 346-4436
  • office hours: TTh 1:30-2:30, W 3:30-5:00
  • 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 seven written assignments.
  • There will be one midterm, on Friday, November 3.
  • The final will be held on Friday, December 8, 10:15-12:15.
  • Some extra credit is available.

  The approximate weighting of the work done is

  Assignments	45%
  Midterm	17%
  Final Exam	38%

• Text: Cormen, Leiserson, Rivest, & Stein, Introduction to Algorithms, 2nd Edition, MIT Press/McGraw-Hill, 2001.

• Supplemental Reading:
  • Michael Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, 3rd Edition, Wiley, 2004 (homepage).
  • 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 25	introduction	1
  Sep 27	algorithm analysis	2.1-2
  Sep 29	asymptotic notation	3.1
  Oct 2	common functions and notation	3.2	last day to drop without W
  Oct 4	recurrence relations	4	last day to add a class
  Oct 6	stacks and queues and deques	10.1-2
  Oct 9	uses of stacks & linked lists	(10.1)
  Oct 11	binary trees	appendix B.5, 10.4
  Oct 13	BSTs	12.1-3
  Oct 16	path lengths and random BSTs	12.4
  Oct 18	AVL trees
  Oct 20	rotations	(13.2)
  Oct 23	(2,4) trees	(18.1)
  Oct 25	RB trees	13.1
  Oct 27	RB insertion	13.2-3
  Oct 30	RB deletion	13.4
  Nov 1	B trees	18.1-3
  Nov 3	midterm
  Nov 6	priority queues and heaps	6.1, 6.5
  Nov 8	heap operations	6.2-3
  Nov 10	heapsort	6.4	last day to drop with W (Nov 12)
  Nov 13	binomial heaps	19.1
  Nov 15	binomial heap operations	19.2
  Nov 17	quicksort	7.1-3
  Nov 20	quicksort is quick	7.4
  Nov 22	lower bounds	8.1 (8.2-4)
  Nov 24	no class
  Nov 27	order statistics	9.1-2
  Nov 29	order statistics	9.3
  Dec 1	final review, course evals
  Dec 8	final exam, Friday, 10:15-12:15

• Late policy for 313: All assignments are due by 4:52.71828 pm of the stated due date, though it is much safer to turn them in at class time. There is a drop box, where you can put your assignments, on the first floor of Deschutes Hall. 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: Cheating ... ... bad.