CIS 313 Introduction to Data Structures

Winter 2008

[ Assignments | CIS | Links | News | Grades | CIS323 ]

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

• CIS 313
  • MWF 10:00-10:50
  • room 307 Volcanology
  • crn 21385

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

• GTF: Jiawei Rong
  • 224 Deschutes, 346-3935
  • office hours: 10:00-12:00 Tuesday
  • email jrong@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 Monday, February 18.
  • The final will be held on Monday, March 17, 10:15am-12:15pm.
  • 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
  Jan 7	introduction	1
  Jan 9	algorithm analysis	2.1-2
  Jan 11	asymptotic notation	3.1
  Jan 14	common functions and notation	3.2	last day to drop without W
  Jan 16	recurrence relations	4	last day to add a class
  Jan 18	stacks and queues	10.1-2
  Jan 21	no class (MLK Day)
  Jan 23	uses of stacks & linked lists	(10.1)
  Jan 25	binary trees	appendix B.5, 10.4
  Jan 28	BSTs	12.1-3
  Jan 30	path lengths and random BSTs	12.4
  Feb 1	AVL trees
  Feb 4	rotations	(13.2)
  Feb 6	(2,4) trees	(18.1)
  Feb 8	RB trees	13.1
  Feb 11	RB insertion	13.2-3
  Feb 13	RB deletion	13.4
  Feb 15	B-trees	18.1-3
  Feb 18	midterm
  Feb 20	priority queues and heaps	6.1, 6.5
  Feb 22	heap operations	6.2-3	last day to drop with W (Feb 24)
  Feb 25	heapsort	6.4
  Feb 27	binomial heaps	19.1
  Feb 29	binomial heap operations	19.2
  Mar 3	quicksort	7.1-3
  Mar 5	quicksort is quick	7.4
  Mar 7	lower bounds	8.1 (8.2-4)
  Mar 10	order statistics	9.1-2
  Mar 12	order statistics	9.3
  Mar 14	final review, course evals
  Mar 17	final exam, Monday, 10:15-12:15

• Late policy for 313: All assignments are due by 4:55 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.