CIS 315, Introduction to Algorithms

CIS 315 Winter 1997

Introduction to Algorithms

[ Assignments | CIS | UO | News ]

Prerequisites: Math 233, CIS 313.
Time and Place:
- Mondays, Wednesdays, and Fridays at 10:00 am in 30 Pacific Hall.
- Fridays at 12:00 pm in 306 Deady Hall.
Instructor: Andrzej Proskurowski, 256 Deschutes, phone 346-4428,
email andrzej@cs.uoregon.edu.
Teaching Assistant: Roy, 233 Deschutes, phone 346-1384,
email aroy@cs.uoregon.edu
Office hours:
- Andrzej: MW after class, Tusdays at 2, or by appt.
- Roy: MWF 9-10, U 3:30-4:30.
Text: Cormen, Leiserson, Rivest, Introduction to Algorithms, McGraw-Hill 1990.
Supplemental Reading:
- Aho, Hopcroft, Ullman, Data Structures and Algorithms, Addison-Wesley 1987.
- Knuth, The Art of Computer Programming, vol.I, Addison-Wesley 1975.
- Ross and Wright, Discrete Mathematics, Prentice Hall 1992.
News: Keep an eye on the course news for miscellaneous announcements.
Sample Solutions: These will be linked through the assignments page.
Evaluation: Assignments constitute a large part of the evaluative material, hence it is crucial that they reflect individual work. Any traces of plagiarism (in both assignments and examinations) will be dealt with according to the University regulations. No late assignments will be accepted, nor extra exams will be given. If you think you have a legitimate reason to argue for an exception from this rule, make sure to communicate it prior to the due date.
The approximate weight of the work graded is
- Homework Assignments: 35%
- Class Participation: 5%
- Midterm: 25%
- Final Exam: 35%

Tentative Syllabus

Week of	Chapter	Description

March 30	1, 2, 4	Introduction: iteration, recursion, loop invariant
	8	Quick Sort: strategies, average case analysis
	10	Medians and Order Statistics
April 6	9	Sorting: lower bounds
	9	Sorting in Linear Time
	18	Amortized Analysis
April 13	20	Priority Queues revisited: Binomial Heaps
	21	Fibonacci Heaps
April 20	22	Disjoint Sets (Union/Find)
	22.3	Union by rank, Find with path compression
	22.4	Amortized complexity analysis of Union/Find
April 27	1-10, 20-22	Midterm Exam
April 27	16	Dynamic Programming: Matrix Chain Product
	16.3	Longest Common Subsequence
	16.4	Polygon Triangulation
May 4	23	Graph Algorithms: Representations
	23.2-3	Breadth-first and Depth-first Traversals
	23.4-5	Topological Sort and Connected Components
May 11	24	Minimum Spanning Trees
	24.2	Algorithms of Kruskal and Prim

May 18	25	Single Source Shortest Paths
	25.2	Dijkstra's Algorithm
	26	All-Pairs Shortest Paths
May 25	34	String Matching
	34.3-4	Knuth-Morris-Pratt Algorithmno
June 1		Spillage, Review and Discussion
June 10	comprehensive	Final Exam at 15:15 Wednesday

Due date policy: All assignments are due (in my mailbox) by 5:00pm of the stated due date, though it is much safer to turn them in at class time.

Grading: 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.