(D-Problems discussed on Friday, 16-Sep-2016)
(Q-Problems due on Tuesday, 27-Sep-2016)
Discussion Problems: -- Prepare (individually) for tutorial discussion.
T6-D0: Complete problem T5-D3 (especially the part on binary search).
T6-D1: (Analysis of Binary Search) (Variant of Problems 17, 21 p.122 of [SG3])
(Read lecture notes on Binary Search, & Sect. 3.4.2 of [SG3], esp. Fig 3.19.)
You are given the following 9 names to be searched using the binary search algorithm.
Amy, Becky, Cathy, Donald, Eve, Fish, Goldie, Howard, Leo,
The search tree below can be used to visualize
the binary search algorithm.
Note that we also draw 10 "fictitious" square-nodes
that corresponds to "unsuccessful searches".
(a)
For each name in the list, how many comparisons are
needed for its (successful) search?
(b)
Compute the average number of "name-comparisons" needed in a (successful) search,
assuming that each name is equally likely to be searched.
Now, we consider unsuccessful searches:
If we search for a name that is not in the list, we get
an unsuccessful search.
Between the 9 names in the list, there are (9+1) gaps. They are
Gap1 -- names that are smaller than Amy,
Gap2 -- those between Amy and Becky,
Gap3 -- those between Becky and Cathy,
. . . ,
Gap9 -- those between Howard and Leo, and finally
Gap10 -- those greater than Leo.
If you search for Billy (a name in Gap3 -- between Becky and Cathy),
the search will "end up" at the 3rd square-node.
(c)
For each of the 10 gaps, how many comparisons are
needed for its (unsuccessful) search?
(d)
Assuming that each gaps is equally likely to be searched,
what is the average number of "name-comparisons" used in
a (unsuccessful) search?
You are given the following 9 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, Becky, Cathy, Donald, Eve, Fish, Goldie, Howard, Leo
(a) Draw the search tree tree that can be used to visualize the sequential search algorithm. Include also the "fictitious" square node for unsuccessful searches.
(b)
For each name in the list, how many comparisons are
needed for its (successful) search?
(c)
Compute the average number of "name-comparisons" needed in
a (successful) search,
assuming that each name is equally likely to be searched.
(d)
For each of the 10 gaps, how many comparisons are
needed for its (unsuccessful) search?
(e)
Compute the average number of "name-comparisons" needed in
an (unsuccessful) search,
assuming that each gap is equally likely to be searched.
T6-PP1: Probs 6 on page 121 (Ch3) of [SG].
T6-PP2: Problem 17, 21 of (Ch3), page 122 of [SG3].
Problems to be Handed in for Grading by the Deadline:
(Note: Please submit hard copy to me.
Not just soft copy via email.)
T6-Q1: (10 points) (Analysis of Binary Search)
You are given the following 11 sorted numbers to be searched
using the binary search algorithm.
5, 8, 13, 21, 34, 47, 55, 61, 75, 89, 97
(a) Draw the search tree tree that can be used to visualize the binary search algorithm.
(b) For each name in the list, compute the number of comparisons needed for its (successful) search?
(c) Compute the average number of "name-comparisons" used in a (successful) search, assuming that each name is equally likely to be searched.
(d) For each of the 12 gaps, how many comparisons are needed for its (unsuccessful) search?
(e) Compute the average number of "name-comparisons" used in an (unsuccessful) search, assuming that each gap is equally likely to be searched.
T6-Q2: (10 points) (Analysis of Sequential Search)
Repeat T6-D2, but assuming that
you are given the following 11 sorted numbers to be searched
(also using the sequential search algorithm).
5, 8, 13, 21, 34, 47, 55, 61, 75, 89, 97
T6-Q3: (10 points) (Spring 2012 Exam Q4)
Spring 2012 Exam Q4 Parts (a)-(c).
T6-Q4: (10 points) (Coming soon -- check again for updates)
--- Cancelled!