[ 621 Home Page | CIS | UO | 621 Assignments ]

• No news, good news.

• Bad news: Homework #1 due Wednesday, Jan.15.

• Good news: in problem 2.31 (on HW#2), showing the correctness of the solution is for extra credit only. You do need to show that
  (i) X(t) counts binary trees with t nodes, and
  (ii) its lower bound is as indicated.

• Foot in mouth department: discussing in class the purported linear solution a·n+b to the recurrence equation T(n)=n+2T(n/2) I should have used T(n/2)=a(n/2)+b, which results in the contradictory statement a·n+b=(1+a)·n+2b.

• Class evaluation Jan. 15 (avg.+stdv.):
  • novelty: 5.8+2.4
  • difficulty: 6.2+1.6
  • speed: 5.7+1.0
  • clarity: 5.2+2.2
  • Student comments (and my reaction):
    
    • "pseudocode and some other notation are new" (make sure that you tell me when I'm using it)
    • "homework is hard!" (no pain, no gain, at least within limits)
    • "problems with reading your handwriting" (let me know in real time; I'll try to improve my BB habits)
    • "write down more on the BB -- some examples rather vague"

• Solutions to homework 1 are now available. Please send comments/problems about the solution to Roy.

• We finally got a newsgroup with a name
  uo.classes.cis.621

• Concerning HW#2:
  • in problem 2.26, "number of comparisons" means "number of comparisons of two elements of the set S."
  • in problem 2.31, X(n) counts the number of binary trees with n-1 nodes (or the number of extended binary trees -- all internal verices with two children -- with n leaves)

• Homework #1 is graded and available. Scores' statistics:
  • max: 30
  • avg.: 22.6
  • st.dev.: 5.1

• Homework #2 is graded and available. Scores' statistics:
  • max: 40
  • avg.: 24
  • st.dev.: 10

• The following policy was applied when grading HW#2:
  • Matrix Chain (total 10):
    • Any correct algorithm 5 ( this includes dynamic progremming)
    • linear lagorithm 8
    • correctness 2
  • Maxmin (total 5):
    • Exact solution gets 5
    • otherwise, 3-5 depending on the correctness of the complexity result.
  • Integer Multiplication (total 5 + 5) :
    • trivial solution 3
    • some optimization on both parts 5
  • Binary search (total 5):
    • Lower Bound for A[i]=i 5
    • No decision tree argument but correct algorithm 3
  • Catalan Numbers (total 10):
    • Tree/Parenthesization argument 6
    • Bound 4
    • Proof (generating function or otherwise) - 2 extra points.

• Comment on problem 3 from Homework #3 :
  Recall that the primary problem deals with n ordered files of given sizes that can be merged into one large ordered file by a sequence of n-1 binary merges, each merge incurring the cost of moving all the involved records. The greedy approach of merging two smalles files of the current collection does solve the primary problem in an optimal way. The challenge for the algorithm solving the secondary problem is to find these two values, delete them, and replace (in the multi-set of file sizes) by their sum. Using a priority queue, the secondary problem can be soved in O(n\log n) time even without presorting of the input data (file sizes).

• Note that (in problem 1, Homework#3) defining F(0)=F(1)=1 (rather than 0 and 1, respectively), we define the sequence F(n) shifted wrt. the usual 0,1,1,2,... You can thus make use of the shifting operator in the handout.

• Solutions to HW#3 are now available as a .ps file.

• Class evaluation Feb. 7 (avg.+stdv.):
  somewhat more difficult and less clear than before.
  • novelty: 6.0+2.2
  • difficulty: 7.5+1.6
  • speed: 5.9+1.5
  • clarity: 4.6+1.8
  • Student comments (and my reaction):
    
    • "if I had a background in combinatorial algebra I would be much better off" (if I had one I would too!)
    • "the lecture content often includes too many tangets" (to make concepts tangible)
    • "would've appreciated a full example of generating function approach" (the handout has one, and there's another one in HW#3 solution)
    • "lectures have become much less confusing" (good! what caused the change?)
    • "handwriting is better; I have glasses now" (no comment)
    • "wonderland" (?)

• A general hint about the midterm: read the problems (seriously!)

• Homework #3 is graded and available. Scores' statistics:
  • max: 30
  • avg.: 20
  • st.dev.: 5

• The following policy was applied when grading HW#3:
  • 1. Fibonacci (10 pts.):
    • generating function 4
    • fractions 3
    • asymptotic bound 4
  • 2. Order Statistics (10 pts.):
    • n=3 \Theta(nlogn) 4 pts, \omega(n) gets 2
    • n=7 gets 4pts., distributed as follows:
      I have given 1 point for the correct recurrence. For n=7, it is not enough to hand-wave and say that a constant exists that makes it linear. You have to prove that you can choose a constant (much in the lines of the proof on AHU).
  • 3. Minimum record movement (10pts.):
    • Queue 8 (see a nice solution keeping one data structure only)
    • Analysis 1
    • Correctness 1
    • Anything correct but not optimal (unoptimal greedy) gets 2-3 depending on how close you were.

• Solutions to Midterm Exam problems are now available as a .ps file.

• Midterm exam's statistics:
  • Maximum: 45
  • average: 31 (69%)
  • st.dev.: 7
  • Problem averages: 68%, 50%, 70%, 73%, 67%, 51%, 40%, 93%, 55%
    (problems 1-8, respectively)

• Homework #4 is posted and due on Wednesday, Feb.26.

• Class evaluation Feb. 24 (avg.±stdv.):
  (new, improved appearence of plusmn courtesy of José)
  • novelty: 7.1±2.2 (increased)
  • difficulty: 6.7±1.7 (decreased?)
  • speed: 5.9±1.2 (the same)
  • clarity:5.5±1.9 (better)
  • Student comments (and my reaction):
    
    • "ever since I brazenly told Andrzej that I'd never use this stuff again, I've been having dreams (nightmares) of all the ways I'm going to need algorithms for the rest of my life."
      (I could not express it better myself)
    • "it seems that majority of people in the class work in gruops on homework and don't acknowledge their `groupwork'"
      (no comment)

• Statistics for HW#4 scores: max 36, avg. 27, std. 8.4.

• A sample solution to problem 5.13 has been posted.

• Homework #5 is posted and due on Monday, Mar. 10.

• Take home Final Exam will be given on Friday, March 14 and due in my mailbox by the following Monday at 5pm.

• Problems in HW#5 carried 7pts. each, except for the last one, worth 27pts.
• Statistics for HW#5 scores: max 55, avg. 38.4, std. 8.9.

• In problem 1 on the final, the lest assignment should read "i:=i-1"