CS 3343/3341: Recitation 6, Heaps, etc.

Introduction
to the Design and Analysis of Algorithms

Textbook.

CS 3343/3341
Analysis of Algorithms
Fall 2012
Recitation 6
Heaps, etc.
    Week 6: Oct 2-4
Due (on time): 2012-10-08  23:59:59
Due (late):        2012-10-12  23:59:59

Recitation 6 should be submitted following directions at: submissions with deadlines 2012-10-08 23:59:59 (that's Mon, 08 Oct 2012, 11:59:59 pm) for full credit. 2012-10-12 23:59:59 (that's Fri, 12 Oct 2012, 11:59:59 pm) for 75% credit.

Recitation 6 should be submitted following directions at: submissions with deadlines

2012-10-08 23:59:59 (that's Mon, 08 Oct 2012, 11:59:59 pm) for full credit.
2012-10-12 23:59:59 (that's Fri, 12 Oct 2012, 11:59:59 pm) for 75% credit.

Problems 1, 2, and 3:

Rec 6, In-Class Problems 1-3

There may seem like quite a few problems for the in-class set, but they are designed to make you familiar with heaps, heapsort, and priority queues. Most of the earlier problems have a short answer and are not hard.

Your Teaching Assistant, Ms. Mahmuda Ahmed, will be monitoring the lab sessions this week. You are not to repeatedly ask her: "Is this right?" for your short answers to questions. Instead you can utilize her to understand the questions and to get to a solution yourselves.

Memoized Calculation of C(n,k): Refer to See memoization and the specific page: Memoized Calculation of Fibonacci Numbers. As mentioned on the Memoization page, follow the pattern of the Fibonacci program to carry out a regular recursive and a memoized recursive calculation of C(n,k): the number of combinations of n things taken k at a time. The formula is:
One requires that n >= 0, k >= 0, and n >= k. As with the Fibonacci program, for sample inputs n and k, you should print the number of calls with and without memoization, and in case of memoization, the number of table inserts. Try several runs, including at least the pairs: <n,k> = <4,0>, <4,1>, <5,4>, <6,4>, <7,3>, <15,10>, <20,10>, <30,15>, <35,10>, <35,12>. [Hint: Note that you will need a 2-dimensional array for the "memos", the answers.]
(Of course there is another, completely different formula for C(n,k), one you are likely more familiar with, namely:
```
                            n!
           C(n,k) =   -------------
                       k! * (n-k)!
```
Thus C(7,3) = 7!/(3!*4!) = 7*6*5/(3*2*1) = 35.)

Revision date: 2012-09-28. (Please use ISO 8601, the International Standard.)