Advanced Data Structures

Fall 2003

[ CIS 410/510 | CIS | UO | Assignments ]

News

(Dec. 12) All raw scores (including Final Exam) are posted; please report any inconsistency (excluding Final Exam). The final grades will be posted Friday.
(Dec. 5) The last news item regarding Final Exam:
- Solutions to problems 6, 7 and 8 are expected in my mailbox by 4pm. on Tuesday.
- Problems 1-5 are elective and not subject to the 6 hour limit; solving them you will show yourselves that you mastered the material (and will receive extra credit).
- I will check my email during the weekend to see if any clarifications are necessary -- possibly Saturday afternoon.
- Thank you for your participation in the course!
(Nov. 20) Assignment 8 is posted, due Wednesday Dec. 3.
(Nov. 26) All the available raw scores (midterm scores doubled) and their statistics (avg±stdev) are posted; please check with your records and report any discrepancy.
(Nov. 20) Assignment 7 is posted, due Wednesday Nov. 26.
(Nov. 17) Statistics of homework assignment 6 (out of 4 turned in, cf. Nov. 10 below): 8.25±0.50.
(Nov. 17) Class evaluation results (difficulty and novelty have risen slightly again, the average about the lecture remained about the same):
- novelty 8.7±1.32
- difficulty 6.9±1.80
- pace 5.6±.70
- clarity 4.3±1.32
- "no comments, good comments."?
(Nov. 12) In Assignment 6, please replace the problem 1 with problem 6: Prove that the total weight of a vertex is equal to the number of its descendants in its virtual tree (page 68, line 3).
(Nov. 10) Assignment 6 is posted, due Friday Nov. 14. Also, statistics of homework assignment 5 (out of 6 turned in, cf. Nov. 4 below): 4.3±0.41 (max of 5).
(Nov. 5) Class evaluation results (difficulty and novelty have risen again, the average about the lecture remained the same, although the opinions about clarity vary):
- novelty 7.9±1.81
- difficulty 6.7±1.83
- pace 5.0±1.03
- clarity 4.6±2.26
- student comment: More easier problems (on homework).
  my answer: Happy to oblige (see below)
- my comment: Only one complaint about the midterm?
(Nov. 4) A quick homework assignment Assignment 5 is posted, due Monday Nov. 10. Also, statistics of homework assignment 4 (out of 6 turned in, see below): 5.5±1.76
(Nov. 4) My record keeping may be deficient, but I seem not have received four HW3 solutions (Ryan, James, Kerry, Peter) and four HW4 solutions (James, Peter, Dave, Dong Ki). Please correct the record soon.
(Oct. 27) An announcement of an informational meeting about graduate schools, this Wednesday.
(Oct. 24) One more paper available from ACM portal (I have given copies to some students, you can ask me for one, if you want it): G.C. Harfst and E.M. Reingold, A potential-based amortized analysis of the union-find data structure, September 2000 ACM SIGACT News, Volume 31, Issue 3.
(Oct. 24)The original paper by D. Sleator and R. Tarjan: Self-adjusting binary trees, Annual ACM Symposium on Theory of Computing, Proceedings of the fifteenth annual ACM symposium on Theory of computing 1983, Pages: 235 - 245 (also available from ACM Digital Library, free of charge for UO faculty and students).
(Oct. 24) In class today we mentioned the article by Jean Vuillemin: A unifying look at data structures, April 1980 Communications of the ACM, Volume 23 Issue 4. It is available at ACM site. Here is the abstract:
Examples of fruitful interaction between geometrical combinatorics and the design and analysis of algorithms are presented. A demonstration is given of the way in which a simple geometrical construction yields new and efficient algorithms for various searching and list manipulation problems.
(Oct. 24) Because of my mistake the due date of Programming Assignment 1has been moved back (again) to Monday, Oct. 27 (sorry for the loss of sleep that may have been caused by my not posting this earlier; I'll try to make up to it during my lectures (:-) Here is Dave's program again, this time as three files: RandomWeightedGraphs, Edge , and graphTest.
(Oct. 24) A program to generate test graphs for the assignment (courtesy Dave).
(Oct. 23) Class evaluation results (difficulty and novelty have risen a notch, the lecture remained about average):
- novelty 6.9±1.83
- difficulty 5.9±1.45
- pace 4.9±0.78
- clarity 5.0±1.66
- student comment: Homework problems are often worded ambiguously.
- my answer: Celebrate life's ambiguity and seek clarification (for instance, by asking questions or attending office hours)
(Oct. 24) Statistics of homework assignment 3 (out of 6 turned in): 7.6±1.1
(Oct. 21) Assignment 4 is posted, due Wednesday Oct. 29. Again, you are welcome to suggest an alternative timing of the assignments (but take under consideration the comments below).
(Oct. 21) Time out for some reflection:
- Late homework is allowed, corrected homework (for partial credit) is encouraged.
- But there is a peril in loosening of the reins: you may slide so far back that it is difficult to righten yourself.
- The main goal of assignments is to give students feedback, often self-generated.
- If I do not see students during my office hours ("or by appointment") I tend to assume that they do not have problems with the material.
- So why would half of the class fail to turn in the homework on time?
(Oct. 15) We have pushed the Programming Assignment's due date back to Friday, Oct. 24.
(Oct. 15) Statistics of homework assignments 1 and 2, respectively (avg±stdev):
1. 8.2±2.35
2. 7.4±1.79
(Oct. 14) Try your hand at some loop invariant problems !
(Oct. 14) Assignment 3 is posted, due Monday Oct. 20. You are welcome to suggest an alternative timing of the assignments.
(Oct.10) Check out this suggested Programming Assignment 1 (to be finalized on Monday).
(Oct. 10) Q&A: "Which chapters of Tarjan do you expect us to have read so far?"
We are falling back on the bottom-up approach (cf. the comment below); therefore, the posted syllabus seems to apply. The exception from that strategy was the quick foray into MWST (RET 6), from which we will back-pedal into UF and PQ (RET 2, 3) to support an efficient implementation of RR. GE (good enough)?
(Oct. 9) Rogue gallery to ease socialization for learning in the class and outside it (discussion of the material). Please provide me with names you want attached to the pictures (eg., "07: Jimmy").
(Oct. 8) Class evaluation results (average±stdev, out of 10; the lower stdev, the better agreement)
- novelty 5.8±2.53
- difficulty 5.5±1.35
- pace 5.4±1.07
- clarity 4.9±1.91
- student comment: "Go slow, 313/5 were long time ago"
(Oct. 8) Q&A: "In your notes on invariants, you also sometimes use {{I}} and sometimes {I}?"
I wanted to prevent the conflict between "begin..end" and "executable assertion"; I tried to make all instances of the latter converted to {{...}}, but apparently failed.
(Oct. 7) Brand new look for your viewing comfort! For a quick review of my take on loop invariant see page 1 and page 2.
(Oct. 6) Assignment 2 is posted, due Monday Oct. 13.
(Oct. 3) Hint for the homework assignment (courtesy of Colin): To implement access in constant time, we need to design an extra data structure, say V, that provides (in constant time) a verification of the content of T[i]; the entries in T that have been set will hold -- beside the value of R -- a pointer to the right entry in V.
(Oct. 3) Exercises suggested but not required, unless you're hopelessly lost with HW#1 and would like to substitute. "Types" below (ADTs, actually) are sets of instances; Elt stands for a set of elements, Nat for the set of natural numbers, Bool for Booleans.
- Write axioms defining ADT Set(Elt,Bool) with operations
  Empty: -> Set
  ¿IsEmpty: Set -> Bool
  MakeSet: Elt -> Set
  ¿IsIn: Set x Elt -> Bool
  Union: Set x Set -> Set
- Define in a meaningful way an ADT BinCount(Nat,Bool) to convey our concept of binary counters with the content interpreted as an integer from the range 0..2^n.
(Nov.30) Assignment 1 is due Monday Oct. 6
(Nov.30) ACM International Collegiate Programming Contest
Background on the ACM contest can be found here. For UO, the first round of this competition is the Pacific Northwest Regionals, to be held this year on November 15. Send a note to Gene Luks if you would like to participate in the contest.
(Nov.30) SIAM stands for Society for Industrial and Applied Mathematics, a professional organization for computer scientists, comparable with Association for Computing Machinery (see the board outside my office for materials). Student memberships secure 30% discount on SIAM publications (our text sells to members for $26).