T11-D1: (Memory) --- SOLUTION SKETCH
2048 = 211; and 4096 = 212;
So, memory-size is (2048x4096) = 211+12 = 223;
(a) MAR has 23 bits;
(b) 11 bits row selector; 12 bits column selector;
T11-D2: (modified from 2008 Quiz 2) -- SOLUTION SKETCH
(a) MAR has 24 bits; Memory size = 224 = 24 MBytes = 16MB.
(b) Dimensions: 2^12 x 2^12 = 4096 x 4096; 12 bits row selector; 12 bits column selector;
T11-D3: (Finding the Strongest Team) --- SOLUTION SKETCH
This problem is EASy.
To get the strongest team (with highest sum-of-score),
just choose the 16 strongest students, those with the highest scores.
So, sort the array S[1..n]. Choose the 16 largest numbers.
This will take O(n2) time if we use selection sort, or O(n lg n) time if we use
mergesort.
T11-D4: (Split into Two Equally Strong Team) --- SOLUTION SKETCH
This problem is HARD.
A brute-force algorithm is to try every possible subset of players. Then compute the sum-of-score for the subset, and keep track of the best possible subset.
For each subset, computing the sum-of-score takes O(n) time. And there are (2n) subsets. So, the total time is O(n(2n)), which is exponential time. This algorithm will not be feasible for n>50. As of today, no one has a solution that is substantially faster than exhaustively search all possible subsets. But, for our problem, with n=31, this algorithm is feasible. Since it takes about (O(31(231)), which is about 62 billion operations. The running time is in the order of a few seconds.
T11-D3: (Finding the Strongest Team) --- SOLUTION SKETCH