Data Structures

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

• Time: Tuesdays and Thursdays at 1:30 pm.
• Place: 200 Deschutes Hall
• Course URL http://www.cs.uoregon.edu/classes/cis313/
• Course Description: Our main theme is the equation (proposed by Niklas Wirth) "Programs=Algorithms + Data Structures." First, we will briefly review loop invariants, recursion, asymptotic complexity notation and recurrence equations, as well as the basic linear data types. Then, we will discuss rooted ordered trees and their usage, especially as search structures. We will conclude with some basic sorting algorithms using the newly introduced data structures.
• Instructor:
  Andrzej Proskurowski, 256 Deschutes, phone 346-4428,
  email andrzej@cs.uoregon.edu.

• Teaching Assistants:
  Haishan Liu, ahoyleo@cs.uoregon.edu, 224 Deschutes, phone 6-3935
  Aaron Henner, ahenner@cs.uoregon.edu, 228 Deschutes, phone 6-1373

• Office hours:
  • Andrzej: After class TT at 3 (half hour) or by appt.
  • Haishan: TT 10-11, W 3-4.
  • Aaron: TBD.

• News: Keep an eye on the course news for miscellaneous announcements.
• Assignments: These will be linked through the assignments page.

• Evaluation:
  • There will be weekly homework assignments. While study groups and student collaboration are encouraged, the assignments are to be done individually rather than in groups.
  • Late policy: All assignments are due in the 313 drop box by 4:30pm of the stated due date. Late papers are subject to a 5% per day penalty, up to a maximum of 25%. Late assignments will not be accepted once the graded papers are returned or once sample solutions are handed out.
  • Grading: will be performed by an able and experienced grader. Any contested score will be first referred to that person. Be aware of the possibility of correcting grading mistakes both in your favor and disadvantage, so that the challenged score can change in either direction. Note: to allow for a larger margin of subjectivity in grading, we will use the whole score range, from 0 to 100%; you may expect the average score (corresponding to B-) to be around 50%. The final letter grade will be assigned based on the total weighted score curve.
  • Participation in class and office hours in encouraged and rewarded (see below).
  • Midterm will be held in the week of Oct. 29. In time, we will provide a study guide (html).
  • Final will be held on Thursday, December 10. at 13:00 (it's a two hour exam). Again, we will prepare a study guide for the final.

  • The approximate weights of student activities are

    Homework Assignments	30%
    Active participation	5%
    Midterm	25%
    Final Exam	40%

• Text:

Cormen, Leiserson, Rivest and Stein
Introduction to Algorithms
Second Edition, The MIT Press 2001
(from a review on Amazon.com) Warning:
• Don't bother with this book unless you have a high aptitude for math
• Don't bother with this book unless you're prepared to work at it
• It's not designed as a reference book; instead it's a study book.
• Supplemental Reading:
• Aho, Hopcroft and Ullman, Data Structures and Algorithms, Addison-Wesley 1987.
• Knuth, The Art of Computer Programming, vol.I, Addison-Wesley 1975.
• Weiss, Algorithms, Data Structures, and Problem Solving with C++, Addison-Wesley, 1995.
• Decker, Hirschfield, The Object Concept, PSW Publ., 1995.
• Ross and Wright, Discrete Mathematics, Prentice Hall 1992.
• Epp, Discrete Mathematics with Applications, PSW Publ., 1995.

Academic Dishonesty

Any assignment not categorized as group work must be done individually. You are encouraged to generally discuss problems with other groups or students, but you may never use some other group's or student's solution or code in any way. The use of sources (ideas, quotations, paraphrases) must be properly acknowledged and documented.

The student conduct code allows an instructor to impose an appropriate sanction for a student found guilty of academic dishonesty, up to and including an N or an F. The instructor also has the obligation to report any sunch incident to the university authorities.

For more information on academic honesty, please talk to me or see the following references: the Student Conduct web page, the Student Conduct Code, and the UO Dean of Students brochure on academic integrity.