[ CIS315 | CIS | UO | Assignments ]

• (June 15) Final exam scores and course grades are now available. The statistics of final exam scores:
  • Loop invariant: 5±4(21)
  • Amortized complexity: 4±4(10)
  • MWST: 7±4(22)
  • Dijkstra: 7±6(23)
  • PQ: 6±7(24)

• (June 11) Please compare my records of homework scores with yours and alert me to any discrepancies to avoid erroneous grades.

• (June 8) At 10am...

• (June 5) Unless unforseen circumstances occur before the end of the day today, I will be available for a final Q/A session on Monday, June 8 in room 200 Deschutes. I will also attempt to post here answers to any e-mail questions on Monday, Tuesday and Wednesday mornings. Tonight, I'll post HW#7 solutions.

• (June 3) Roy's hint on the Exercise 24.2-5 of the last homework: ``What happens if edge weights take only values 1 and 2?'' (Another enigmatic hint, Roy! I'd deal with them separately?)

• (June 3) If you have not done this before, check the study guide for the final.

• (June 2) HW#6 solutions and statistics: 9.2(14)±4.6.

• (June 1) HW#5 statistics: 8.4(17)±3.3.

• (May 27) HW#7 is posted and is due on Friday, June 5.

• (May 27) Solutions to HW#5 are posted.

• (May 26) Roy's hint for the Exercise 26.1-3 of HW#6: "what can you do given this matrix and the adjacency matrix?" (I don't know, Roy; I can look at page 555?)

• (May 22) Class evaluation statistics (19 respondents; avg.±stdv.):
  • novelty: 6.5 ±2.2
  • difficulty: 6.7 ±1.9
  • speed:6.0 ±1.3
  • clarity: 4.0 ±2.0
  • Student comments (and my reaction):
    
    • "Recent lectures have been noticeably more clear." (Hm, Roy has not been up here for some time...)
    • "I like laundry line analogy" (Then you should be able to answer the five point question: Which edges are relaxed in laundry line graph?)
    • "Solutions on the web are very helpful" (`We aim to please', well, not quite... `to help')

• (May 20) Fall 1998 ACM programming contest announcement.

• (May 19) HW#6 is posted and is due on Wednesday, May 27.

• (May 19) In HW#5, the question 22.3-4 refers to the situation where all the UNIONs (interpreted as links) are performed before any FIND-SET operation.

• (May 18) HW#4 solutions and statistics: 11.1(19)±6.2. You can pick them up now.

• (May 18) On the mid term scores, 40 was the approximate upper bound on C (as much as I would have wished it to be the lower bound). Sorry for the typo.

• (May 18) Since I just mentioned Wirth by name (as opposed to calling him by value, as many do; that was the joke I skipped in class), here is a related posting on the web.

• (May 17) Mid term raw scores can be viewed here. Check the scores with your records, please.

• (May 15) The due date for Homework#5 moved up to Wednesday, May 20.

• (May 15) Strangely enough, nobody complained about inaccessibility of the reshuffling example... It may still come handy, so look it up.

• (May 15) Solutions to HW#4 are posted.

• (May 12) HW#5 is posted (it includes 22.3-1) and is due on Monday, May 18.

• (May 11) HW#5 will be posted soon; it will include Problem 22-1 (page 458), so you may want to get cracking on that.

• (May 11) Midterm statistics: 18.1±11.7

• (May 8) HW#3 solutions and statistics: 7.4(13)±3.3.

• (May 4) Class evaluation statistics (20 respondents; avg.±stdv.):
  • novelty: 7.0 ±2.0
  • difficulty: 7.0 ±1.6
  • speed:6.2 ±1.0
  • clarity: 4.4 ±2.4
  • Student comments (and my reaction):
    
    • "Recent lectures have been noticeably more clear." (see below?)
    • "Roy is doing a great job as a lecturer." (bravo, Roy!)
    • "Please tie in the current topic with the text section(s)." (The past two weeks we have discussed amortized complexity, mergeable priority queues and set manipulation -- Chapters 18, 20, 21 and 22. The next two weeks will be devoted to graph algorithms: chapters 23-26.)
    • "Samples of problems like the ones on the midterm exam would be good to practice on." (I plan on providing those soon.)
    • "I'd like to see solutions to the homework." (I'll work on it; watch this space.)
    • "Exam did not test what we were prepared for in class or by homework." (Even though it may be difficult, forget for a moment the evaluative aspects of the test and concentrate on the learning process. Novel applications of tools being studied reinforce the new concepts better than a mere regurgitation of their use. Granted, there is anxiety involved in being tested and I may have provided more than enough of that. Let's wait and see the scores -- coming soon.)

• (May 6) Correction to HW#4: the first problem is 20.2-7.

• (May 6) (Union Find) The question of updating the ranks came up during class. An alternative to the "rank heuristics" is the "size heuristics" for Unions: keep track of the size of subtrees that are being merged. When you do a union, make the smaller subtree (smaller in terms of size) a child of the larger subtree. Observe that finds (with path compression) do not affect the size. With this modification, n Union Finds (with path compression) will take time O(nG(n)) where G(n) is the function defined in class. If you have difficulty seeing this, send email to Roy.

• (May 4) Roy's Tuesday 3:30-4:30 office hours for 5/5/98 are cancelled due to unavoidable reasons and will be rescheduled later. In the meantime, Roy will be happy to meet you any other time if you make an appointment with him.

• (May 1) CIS211 needs graders -- apply to Shelley in the main office.

• (May 1) HW#4 is assigned and due on Monday, May 11

• (April 30) Influence the next edition of your text! Answer to any question(s) on the questionnaire and send it back to me; I'll forward it to the publisher.

• (April 26) Research and teaching: here's a link to the INFORMS Montréal meeting.

• (April 22) The midterm will be held on Monday, April 27. It will be a fifty-minute open text and one page of notes exam. (You will not have much time to consult the materials, so make sure that you prepare well!) The topics to be covered by the test are listed in the study guide.

• (April 22) HW#2 statistics: 7.7(13)±3.5.

• (April 21) Just in case, here's the story of meargeable heaps with lazy deletion:

  "At the beginning thare was a tree with heap property. Then there were at least k lazy delete operations turning some legitimate nodes into dummies. Then there was your "listing" algorithm creating a list of subtrees rooted at children of the connected component of the subgraph of the original tree that is induced by dummy nodes and contains the root of the tree. Finally came a "repeated merging algorithm" that turned the remaining nodes (of the subtrees above) into one tree with heap property and everybody lived happily everafter."

• (April 17) Class evaluation statistics (23 respondents; avg.±stdv.):
  • novelty: 6.8 ±1.8
  • difficulty: 7.0 ±1.6
  • speed: 6.0 ±1.4
  • clarity: 3.2 ±1.9
  • Student comments (and my reaction):
    
    • "relate the present subject to the long term goals." (like Priority Queues and Amortized Complexity?)
    • "sometimes you hop from equation to equation and I lose track." (I'll try to provide pointers more often.)

• (April 17) A tally of lecture characteristics and a student commment (re. involving students during the lecture): "just don't ask me a question!"

• (April 17) For the stout of heart, a loop invariant excersise.

• (April 14) Last call for the programming contest participation (deadline moved up)!

• (April 14) Number the ways! Get involved in learning and teaching!

• (April 14) A clarification of Exercise 9.2-4.

• (April 14) HW#1 statistics: 8.8(12)±3.5.

• (April 14) Not forgetting the reading assignment, are we? If it's the middle of April, the chapters must be 1-10 and 18-22 (there was a typo in the syllabus, now gone: chapter 10 is in for the midterm).

• (April 14) HW#3 is assigned and due on Wednesday, April 22

• (April 13) Try again the algorithmic art; it turned out to be an unintended April Fools joke (not anymore).

• (April 13) The linear time reshuffling of an indirectly sorted array, as discussed last week.

• (April 10) Change in the office hours:
  • Andrzej: from Friday to Tuesday at 2,
  • Roy, from 3pm to 3:30 on Tuesdays.

• (April 10) The due date for Homework#2 moved up to Wednesday, April 15.

• (April 8) Execution time results from an experiment with Quick Sort.

• (April 8) Class evaluation statistics (26 respondents; avg.±stdv.):
  • novelty: 7.0 ±2.2
  • difficulty: 7.0 ±1.8
  • speed: 5.5 ±1.2
  • clarity: 3.8 ±2.3
  • Student comments (and my reaction):
    
    • "formal discussion sections would be helpful" (I am sure they would -- the informal version has already started last Friday!)
    • "CIS422 coincides with the office half-hours" (For people unwilling to make an appointment, we'll discuss an alternative time.)
    • (Not many comments -- things must be moving along smoothly, even though not quite comprehensibly; the "clarity" statistics are disquieting.)

• (April 8) HW#2 is assigned and due on Monday, April 13

• (April 8) Programming contest announcement.

• (April 3) An example of a loop invariant proof.

• (April 2; antidated for a reason) "A useful web page" (notes from a Cambridge course in formal methods). I have "unzipped" the second and the third sections of the lecture slides, some of which we saw Wednesday.

• (April 1) An "Algorithmic Art" link courtesy of Gene Luks. He recommends especially the "Universal Turing Machine Self Portrait".

• (April 1) "The future will be full of algorithms" (according to USA Today)

• (March 30) HW#1 is assigned and due on Monday, April 6