Algorithms and Complexity
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):
- 3.3 ± 1.15 / 4
- 5.3 ± 1.36 / 7
- 5.0 ± 1.81 / 8
- 6.2 ± 2.92 /10
- 6.3 ± 2.71 /10
- 6.6 ± 1.31 /8
- 2.4 ± 1.51 / 5
- 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.