(D-Problems discussed on Friday, 28-Oct-2016)
(NO Q-Problems)
Discussion Problems: -- Prepare (individually)
for tutorial discussion.
T11-D1: (MAR) (Modified from Practice Prob 1 & 2 of Ch-5.2.1 of [SG].)
(First read Section 5.2.1 Memory and Cache (pp. 192-198) of [SG3].)
Assume that our memory unit is organized as a 2,048 x 4,096 two dimensional
array.
(a) How big does the MAR register have to be?
(b) How many bits of the MAR is used for row decoder and column decoder?
T11-D2: (Modified from 2008 Quiz 2)
(a) If the MAR register contains the binary number [0011 1010 1011 0101 1101 1010],
what is the size of the memory unit (how many memory locations)?
(Note: The blanks are not part of the binary number, but are only there for easier readability.)
(b) If the memory is organized in a two-dimensional square,
what would its dimensions be? And how many bits for the row selector, column selector?
T11-D3: (Problem 1: Finding the Strongest Team)
Imagine that Prof. Leong wishes to select a team consisting of half
his UIT2201 class of n students, (for this semester, n=31)
to take part in an
underwater synchronized basket weaving competition in UTown.
Suppose that the underwater basket weaving "score" of the kth person
in the class can be indicated by a non-negative number S[k] and that
these scores have been stored in an array S[1..n].
Give an algorithm to help Prof. Leong select a
strongest team (team with maximum total score).
T11-D4: (Problem 2: Splitting into Two Equally Strong Teams)
Due to unexpected circumstances (secret, not to be revealed here),
the competition was cancelled.
Undaunted by this prospect, Prof. Leong decided to run his own competition using
the nice NUS Alumni Guild House swimming pool instead.
He decided to choose two teams from his own UIT2201 class.
To make the competition fair, he abandoned the strongest team idea
and instead decided to break his UIT2201 class
into two teams that are equally strong** to compete against each other.
Give an algorithm to help Prof. Leong select the two teams
(each team can have any number of students) that are most equally matched.
(** Note: If strictly equally strong teams cannot be achieved,
then at least, as equal as possible.)