Algorithms and Complexity

[ Assignments | CIS | UO | CIS621 ]

CIS 621 News

Winter 2009

(March 15) FAQ about the final exam:
- Problem 2:
  - What does "m" stand for?
    The number of DeleteMin operarations ("infrequent" is supposed to suggest that m is o(n)).
  - What exactly do you want us to compare ?
    General performance of mergeable priority queue has an obvious lower bound, which can be relaxed in special cases -- as here, when DeleteMin is infrequent.
  - What is "this implementation"? Do you mean priority queue implementation using lazy heap when Delete Min is infrequent? or just general lazy heap implementation?
    Both: when DeleteMin is infrequent (occurs m times) and PQ is implemented as lazy binomial heaps.
(March 14) The final exam is posted and solutions due next Wednesday at 10:15 am.
(March 7) Finally the Midterm grades are in. Here's the statistics (average score 38.6 ± 6.36 standard deviation / 60 maximum):
1. 3.3 ± 1.15 / 4
2. 5.3 ± 1.36 / 7
3. 5.0 ± 1.81 / 8
4. 6.2 ± 2.92 /10
5. 6.3 ± 2.71 /10
6. 6.6 ± 1.31 /8
7. 2.4 ± 1.51 / 5
8. 3.5 ± 2.11 / 8
(March 4) The returns from your evaluations (avg±stdev for 12 respondents):
- Novelty: 5.6±2.47
- Difficulty: 6.2±1.70
- Pace: 5.7±1.07
- Clarity: 4.7±1.86
- Comments:
  - Quite a wide range of perception of "novelty"
  - "Did you grade our other assignments?" No, I did not.
  - "I wish the final exam were easier" Compared to what?
  - "Nobel Prize for P=NP would surely bring peace to the computer science world..." Unlikely, imho.
(March 4) Here is a citation to honor Dick Karp's achievements.
(March 4) The seventh assignment has been posted and is due next Wednesday, March 11.
(Feb. 25) We agreed to meet this Friday, Feb. 27 in room 160 at 12:00 to discuss the midterm exam's problems.
(Feb. 25) The sixth assignment has been posted and is due next Wednesday, March 4.
(Feb. 25) I forgot to tabulate the returns from Feb. 11 evaluations (avg±stdev for 9 respondents):
- Novelty: 5.9±1.69
- Difficulty: 6.3±1.49
- Pace: 4.9±1.05
- Clarity: 4.9±1.69
- Comment:
  - "I cannot see the whiteboard" Perhaps you could move your chair and write on a pad?
(Feb. 16) As soon as I figure out how to ftp the Midterm exam file, you'll be able to start working on it. The solutions will be due in class next Monday (Feb. 23).
(Feb. 9) The fifth assignment has been posted and is due next Monday, Feb. 16.
(Feb. 4) We agreed to meet this Friday, Feb. 6 in room 160 at 11:30 to discuss FFT (in the context of Divide-and-Conquer).
(Feb. 4) The returns from your evaluations (avg±stdev for 10 respondents):
- Novelty: 6.2±1.67
- Difficulty: 6.7±1.49
- Pace: 5.7±0.95
- Clarity: 4.4±2.41
- Comments:
  - "Sometimes i am not sure what problem we are solving in class" I'll try to clarify it better.
  - "No complaints" One person's opinion.
(Feb. 2) The fourth assignment has been posted and is due next Monday, Feb. 9.
(Feb. 2) Statistics of the scores for Assignment 2: maximum 15, average 9.1, standard deviation 2.57
(Jan. 28) The returns from your evaluations (avg±stdev for 9 respondents):
- Novelty: 6.6±2.18
- Difficulty: 6.4±1.33
- Pace: 5.6±1.24
- Clarity: 3.4±2.51
- Comments:
  - "Give us a week for homework (from the time it is posted)" I'll try.
  - "Give us heads up on the material to be covered next" I'll try.
  - "Sometimes you answer before the question is posed missing the point." I'll listen more carefully for the full stop.
  - "Going well" One person's opinion.
(Jan. 25) An example of a loop invariant proof (a solution to Stable Matching Problem)
(Jan. 21) As a part of homework assignment 3 (TBA), solve one of the two problems from Cormen: Problem 21.2 or Problem 21.3.
(Jan. 21) Brain-seizure correction: Adelson-Velsky and Landis
(Jan. 13) For those who looked at the second assignment: I have corrected the obvious (?) typo.
(Jan. 13) The returns from your evaluations (avg±stdev for 11 respondents):
- Novelty: 5.6±2.38
- Difficulty: 5.3±1.42
- Pace: 5.0±0.63
- Clarity: 4.5±2.11
- Comment: "At times difficult to understand a question asked" I'll try to be more explicit
(Jan. 13) The second assignment has been posted and is due next Monday, Jan. 19.
(Jan. 7) The first assignment has been posted and is due next Monday, Jan. 12.