Introduction to Algorithms

• Lectures
  • Time: Mondays, Wednesdays and Fridays at 12:00
  • Place: 112 Lillis (the new Business School building)

• Help session: Thursdays at 08:00 in 112 Lillis
• Instructor:
    Andrzej Proskurowski, 256 Deschutes, phone 346-4428,
    email andrzej@cs.uoregon.edu

• Teaching Assistant:
    David Hofer, 254 Deschutes, phone 6-4436,
    dhofer@cs.uoregon.edu

• Office hours:
  • Andrzej: After class MW (half hour), or by appt.
  • Dave: Monday, 11am-noon, 3:30-4:30pm; Wednesday, 3:30-4:30pm; Friday, 2-3pm.

• Course URL http://www.cs.uoregon.edu/classes/04S/cis315/
• Prerequisites: Math 233, CIS 313

• Text:
    Cormen, Leiserson, Rivest, and Stein
    Introduction to Algorithms, 2nd Edition
    The MIT Press 2001.

• Supplemental Reading:
• M.T. Goodrich and R. Tamassia, Algorthm Design, John Wiley and Sons 2002.
• 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.

 

• Course Description:
    To the leitmotif of CIS 313, "Programs = Algorithms + Data Structures", we will add "Correct and Efficient." In order to (re)introduce a very useful analysis tool for those attributes, Loop Invariant, we will start by discussing the subject of spanning trees in graphs. The algorithms used to illustrate the tool also exemplify the principles of algorithm design techniques (Greedy, Dynamic Programming, Divide-and-Conquer), which will be discussed next. After the Midterm, we spend some time discussing the amortized complexity criterion and applying it to new tree-based data structures and algorithm suites: Partition into disjoint sets ("union-find") and (extended) Priority Queue. We will give further examples of algorithms on graphs (traversals and their application to connectivity) and conclude with a discussion of somewhat different models of problems (Satisfiability and Linear Programs).
• News: Keep an eye on the course news for miscellaneous announcements.

• Assignments: These will be linked through the assignments page. There will be weekly
  • Homework assignments, interspersed with
  • A programming project of longer duration (with stages);
  • While study groups and student collaboration are encouraged, the assignments are to be done individually rather than in groups. (See more below.)

• Evaluation:
  • Late policy: All assignments are due in the 315 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 posted.
  • 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 is encouraged and rewarded (see below).
  • Midterm will be held in class on the last Thursday in April. The study guide is provided (but do not expect too much from it!)
  • Final will be held on Wednesday, June 9. at 10:15 (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%

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.