CIS 313 Introduction to Data Structures

Winter 2007

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

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

• CIS 313
  • MWF 2:00-2:50
  • room 301 Condon
  • crn 21267

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

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