(D-Problems discussed on Wednesday, 20-Feb-2013)
(Q-Problems due on Friday, 22-Feb-2013)
Practice Problems: (not graded)
I have included a number of practice problems for you to try out.
These problems will help you to "ease into" the materials
covered in the course. (If you have difficulties with these
practice problems, please quickly see your classmates
or the instructor for help.)
T5-PP1:
(a) Practice Problem 1 (Ch-3.3.2), page 89 of [SG3]
(b) Practice Problem 1 (Ch-3.3.3), page 94 of [SG3]
T5-PP2: Probs 5, 11 on page 121 (Ch3) of [SG].
T5-PP3: Problem 19 of (Ch3), page 122 of [SG3].
T5-PP4: Problem 28 of Ch3, page 123 of [SG3].
Discussion Problems: -- Prepare (individually)
for tutorial discussion.
T5-D0: Compulsory Readings
T5-D1: (Running times of Find-Max(A,n), Sum(A,n), Seq-Search(N,T,n,Tel))
Consider the algorithms
Find-Max(A,n), Sum(A,n), Seq-Search(N,Tel,n,NAME)
from the lecture notes.
Analyze each of these algorithms and show that their worst-case running time
(or time complexity) is O(n).
T5-D2: (Order of Growth of Functions)
Read "The Tortoise and the Hare" on p.97 and Ch-3.3.4 of [SG3].
This story compares "running a fast O(n) algorithm on a SLOW computer"
with "running a SLOW O(n2) algorithm on a very fast computer". Now, solve the following problem:
(a) [Linear vs Quadratic] (Variant of Problem 11 (Ch3), p.121 of [SG3])
Algorithm A has time complexity of 50n
(linear in the problem size n,
with a big constant of 50).
Algorithm B has time complexity of 0.5n2
(quadratic in n,
with small constant of 0.5).
At approximately what value of n does
Algorithm A become more efficient than Algorithm B?
(b) [Quadratic vs Exponential] (Variant of Problem 27 (Ch3), p.123 of [SG3])
At approximately what value of n does
an algorithm that does 50n2 instructions become
more efficient than another that does 0.5(2n) instructions?
[Hint: We do not need the minimum or the exact value. Plot an Excel table of the two functions to see when they "cross" each other.]
T5-D3: (Analysis of Binary Search) (Variant of Problems 17, 21 p.122 of [SG3])
You are given the following 11 names to be searched
using the binary search algorithm.
(Note: Read lecture notes on Binary Search, Section 3.4.2 of [SG3], esp. Fig 3.19 on page 108.)
Amy, Barack, Carol, David, Eleanor, Fish, Gary, Hillary, Iris, John, Kerry
(a) Draw the search tree diagram that can be used to visualized
the binary search algorithm.
(b) For each name, 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?
T5-D4: (Analysis of Sequential Search) (Variant of Problems 5 p.121 of [SG3])
You are given the following 11 names to be searched
using the sequential search algorithm.
(See Section 3.3.1 (pp.84-89) of [SG3] and Problem 5 (p.121) of Ch. 3.)
Amy, Barack, Carol, David, Eleanor, Fish, Gary, Hillary, Iris, John, Kerry
(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?
Problems to be Handed in for Grading by the Deadline:
(Note: Please submit hard copy to me.
Not just soft copy via email.)
T5-Q1: (5 points) [Query Processing with Multiple Lists]
You are given information about the n students in NUS stored in
four lists -- Student-ID, Name, Major, Tel-Num, each of size n.
(You can assume that the respective data have already been read into the lists.)
(a)
Write an algorithm that will print out
the student-id, name, and telephone number of all students whose major is
"AnE".
Namely, print out
Student-ID[k], Name[k],
Faculty[k], Major[k], Tel-Num[k],
for all k where Major[k]="AnE".
(b) What is the time complexity of your algorithm
(in terms of n)?
(Note: AnE means "Anywhere and Everywhere".)
T5-Q2: (10 points) [Quiz Question from the Past -- Hamming Distance]
Quiz 1, Spring 2009, Q2 -- here (pdf)
T5-Q3: (10 points) (Analysis of Binary Search)
You are given the following 10 sorted numbers to be searched
using the binary search algorithm.
7, 13, 24, 38, 48, 55, 61, 75, 88, 93
(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?
T5-Q4: (10 points) (Analysis of Sequential Search)
You are given the following 10 sorted numbers to be searched
using the sequential search algorithm.
7, 13, 24, 38, 48, 55, 61, 75, 88, 93
(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?
T5-Q5: (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, n2, 2n,
for four different values of n (columns),
namely, n=10, 50, 100, 1,000.
Extend this table by inserting in
(a) two new rows with time complexity
functions nlgn (in between n and n2) and n3 (in between n2 and 2n) and
(b) two more columns for n=1,000,000
(or 106) and 1,000,000,000 (or 1 x 109).
Print out the extended table with rows in increasing order of growth
(namely, lg n, then n, then nlgn,
then n2, then n3, then 2n)
and the columns in increasing value of n.
Note: To illustrate these time complexities (or orders of magnitude), we note that
A5-2013: [Largest, Smallest, 2nd-smallest and tournaments]
(a)
It is straight-forward to find the Smallest and Second-Smallest in a
list A[1..n] of n numbers in (2n-3) comparisons.
However, we can do much better than that.
Give an algorithm that finds the Smallest and Second-Smallest in a
list A[1..n] of n numbers using at most (n + lg n) comparisons.
(b)
Give an algorithm that finds the Max and Min in a
list A[1..n] of n numbers using at most 1.5n comparisons.
[Hint: Think tournaments.]