Advanced Data Structures

[ Assignments | CIS | UO | News ]

CRN 15206/15207

CIS 410/510

Fall 2003

Time: MWF 11:00 - 11:50
Place: 200 Deschutes
Text: R.E. Tarjan, Data Structures and Network Algorithms, SIAM 1983. ( RET)
Supplemental Reading:
- T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, McGraw-Hill 1989. (CLR)
- Aho, Hopcroft and Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley 1987.
- Knuth, The Art of Computer Programming, vol.I, Addisson-Wesley, 1976.
Instructor: Andrzej Proskurowski
- email: andrzej
- office: 256 Deschutes
- phone: 346-4428
Office half hours: After class
Objectives: Analysis and design of efficient algorithms based on sophisticated structuring of information.
Evaluation: Weekly homework assignments interspaced with few programming projects, take-home midterm and final exams, all weighted approximately equally. Class participation based on reading assignments and alertness will influence the final grade.

Weekly Homework Assignments 35%

Take home Midterm and Final Examinations 60%

Class Participation 5%
Description: In this course we want to study structuring of information for efficient implementation of algorithms using as a case study problems in Network Flows, an important area of combinatorial optimization. A top-down presentation of the material follows the definition of the "maximum flow" problem (in Chapter 8 of the text) and the high-level description of its solution by repetitively incrementing the flow while finding "blocking flows" (Section 8.2). The algorithm uses operations on rooted trees with cost: "makeTree", "findRoot", "findCost", "addCost", "linkTrees", and "cutTree" (Section 8.3). To realize these operations efficiently, one needs to be familiar with data structures for manipulation of trees (Chapter 5), and in particular those supporting efficient implementation of disjoint sets (Chapter 2), priority queues (Chapter 3), dictionaries (Chapter 4). The notion of "efficiency" is based on the amortized complexity and its analysis on the notion of a loop invariant. These are the main ingredients of the underlying material. Discussion of an algorithm design paradigm, Dynamic Programming, rounds out the syllabus. Depending on the students' background - preparation - inclination, we will traverse the modular structure of the material in a top-down or bottom-up manner. What follows is a possible schedule. (RET refers to the main text, CLR -- to the first on the supplemental reading list.)

Tentative Syllabus

Week of Text chptr. Description

Sept. 29 CLR1, RET1 Introduction: abstract data types, complexity analysis, loop invariants.

Oct. 6 CLR18, RET2 Amortized complexity, Disjoint sets: union/find, applications.

Oct. 13 CLR 20,21, RET 3 Priority queues.

Oct. 20 CLR 14, RET 4 Search trees: self-adjusting BST .

Oct. 27 RET 5 Linking and cutting trees.

Nov. 3 RET 1-4 Take home Midterm exam due

Nov. 10 RET 8 Network flows.

Nov. 17 Layers of ADT implementations.

Nov. 24 CLR VI, RET 6,7 Minimum spanning trees.

Dec. 1 Optimal BST

Dec. 8 comprehensive Take home Final Exam due

Weekly Homework Assignments	35%
Take home Midterm and Final Examinations	60%
Class Participation	5%

Week of	Text chptr.	Description

Sept. 29	CLR1, RET1	Introduction: abstract data types, complexity analysis, loop invariants.
Oct. 6	CLR18, RET2	Amortized complexity, Disjoint sets: union/find, applications.
Oct. 13	CLR 20,21, RET 3	Priority queues.
Oct. 20	CLR 14, RET 4	Search trees: self-adjusting BST .
Oct. 27	RET 5	Linking and cutting trees.
Nov. 3	RET 1-4	Take home Midterm exam due
Nov. 10	RET 8	Network flows.
Nov. 17		Layers of ADT implementations.
Nov. 24	CLR VI, RET 6,7	Minimum spanning trees.
Dec. 1		Optimal BST
Dec. 8	comprehensive	Take home Final Exam due