---

UIT2201: CS & the IT Revolution
Tutorial Set 4 (Spring 2008)

(D-Problems discussed on Thursday, 14-Feb-2008)
(Q-Problems due on Tuesday, 19-Feb-2008)

---

T4-PP1: Probs 12 of (Ch3) of [SG3].
T4-PP2: Probs 19 of (Ch3) of [SG3].
T4-PP3: Probs 24 of (Ch3) of [SG3].

T4-D1: [Algorithms -- Partition Problem]
(a) Give a *simple* algorithm (in pseudo-code) for solving the following problem.

Divide a group of n people into two disjoint subgroups (of equal size) such that the difference in the total ages of the members of the two subgroups is as large as possible. (Assume n is even.)

(b) Modify your algorithm slightly so that it also works when n is odd.
(c) What if we now want to make the difference as small as possible? Will your algorithm still work? Can you design an algorithm for this modified problem?

T4-D2: (Rate of Growth of Functions)
(a) (Variant of Problem 28a of [SG3]) [Linear time Algorithm]
An algorithm that is Θ(n), (namely cn for some constant c) takes 10 seconds to execute on a particular computer when n=100. How long would you expect it to take when n=200, 400, 800, 1600?
(b) (Variant of Problem 28b of [SG3]) [Quadratic time Algorithm]
An algorithm that is Θ(n²) takes 10 seconds to execute on a particular computer when n=100. How long would you expect it to take when n=200, 400, 800, 1600?
(c) (Variant of Problem 27 of [SG3]) [Linear vs Quadratic]
At about what value of n does an algorithm that does 100n instructions become more efficient than one that does 0.01n² instructions? (Use a calculator.)
(d) (Problem 27 of [SG3]) [Quadratic vs Exponential]
At about what value of n does an algorithm that does 100n² instructions become more efficient than one that does 0.01(2ⁿ) instructions? (Use a calculator.)

T4-D3: (Analysis of Binary Search) [continued from T3-D3]
You are given the following 10 names to be searched using the binary search algorithm.
(In [SG3], see Section 3.4.2, esp. Fig 3.19, and Problem 24 page of Chapter 3)

    Amy, Becky, Cathy, Donald, Eve, Fish, Goldie, Howard, Leo

(a) Draw the search tree diagram that can be used to visualized the binary search algorithm.
(b) For each name in turn, how many comparisons are needed for its successful search. Assuming that each name is equally likely to be searched, what is the average number of "name-comparisons" used in a (successful) search?
(c) Which about the average number of "name-comparisons" for an unsuccessful search?

T4-D4: (Analysis of Sequential Search)
You are given the following 10 names to be searched using the sequential search algorithm.
(See Section 3.3.1 of [SG3] and Problem 5 of Ch. 3.)

    Amy, Becky, Cathy, Donald, Eve, Fish, Goldie, Howard, Leo

(a) Draw the search tree diagram that can be used to visualized the sequential search algorithm.
(b) For each name in turn, how many comparisons are needed for its successful search. Assuming that each name is equally likely to be searched, what is the average number of "name-comparisons" used in a (successful) search?
(c) Which about the average number of "name-comparisons" for an unsuccessful search?

T4-Q1: (5 points) (Algorithm -- Hamming Distance)
The Hamming distance is often used to measure similarity between two strings (of characters). Given two strings of length n, S[1,n] and T[1,n], the Hamming distance between them is just the number of character positions in which they differ. For example, the Hamming distance between ACCGTAT and ACCGTTT is 1 since they differ only at the 6^th position. The Hamming distance between ACGT and AGGG is 2. The Hamming distance between any string and itself is always 0.
Give a *simple* algorithm for computing the Hamming distance of two strings S[1..n] and T[1..n].

T4-Q2: (10 points) (Analysis of Sequential Search)
Given the following 11 sorted numbers to be searched using the sequential search algorithm.
    3, 5, 8, 13, 15, 20, 22, 25, 29, 38, 41
(a) Draw the search tree diagram that can be used to visualized the sequential search algorithm.
(b) Assuming that each name is equally likely to be searched, what is the average number of comparisons used in a (successful) search?
(c) Which about the average number of comparisons for an unsuccessful search?

T4-Q3: (10 points) (Analysis of Binary Search)
You are given the following 11 sorted numbers to be searched using the binary search algorithm.
    3, 5, 8, 13, 15, 20, 22, 25, 29, 38, 41
(a) Draw the search tree diagram that can be used to visualized the binary search algorithm.
(b) Assuming that each name is equally likely to be searched, what is the average number of comparisons used in a (successful) search?
(c) Which about the average number of comparisons for an unsuccessful search?

T4-Q4: (15 points) [Time Complexity and How Fast They Grows]
Figure 3.27 of [SG3]] gives the comparison of four different time complexity functions (rows), namely, lg n, n, n², 2ⁿ, for four different values of n (columns), namely, n=10, 50, 100, 1,000.
Extend this table by adding in
    (a) two new rows with time complexity functions nlgn and n³, and
    (b) three more columns for n=100,000, 1,000,000 (or 10⁶), 1,000,000,000 (or 1 x 10⁹).
Print out the new (extended) table with the rows in increasing order of growth.

A4: (Faster Majority Algorithm) The solution to the majority problem explored in Tutorial 3 focussed on getting a correct algorithm based on reuse of simpler primitives. The algorithm obtained runs in quadratic (O(n²) time. There is a faster algorithm that runs in O(n lg n) time which first sorts the array and then scan in linear time. However, we can actually do even better.
Design a linear time O(n) algorithm for solving the majority problem.

A5: (Average Performance of Binary Search for large N)
(a) For the search tree for binary search on N=2^k - 1 elements, derive an exact formula for the average number of comparisons for a successful search. (You can have the answer in terms of k and N.)
(b) Now, extend your answer to all values of N.