Analysis of Algorithms ASSIGNMENT 2

Analysis of Algorithms
(Computer Science 3340b)
ASSIGNMENT 2

Please read general guidelines for answering algorithm design question on page 3.
1. In the text book 8.2-1, pp. 196.
2. In the text book 13.3-2, pp. 322.
3. In the text book 13.4-3, pp. 330.
4. Given n elements and an integer k. Design an algorithm to output a sorted sequence of
smallest k elements with time complexity O(n) when klog(n) ≤ n.
5. Design an efficient data structure using (modified) red-black trees that supports the
following operations:
Insert(x): insert the key x into the data structure if it is not already there.
Delete(x): delete the key x from the data structure if it is there.
F ind Smallest(k): find the kth smallest key in the data structure.
What are the time complexities of these operations?
6. In the text book, 21.4-2, pp. 581.
7. In the text book, 21.4-3, pp. 581. And in question 10 a), is it enough to use one byte to
store rank? Explain your answer.
8. In the text book, 16.3-5, pp. 436.
Hint: show that for an encoding T, if dT (c1) dT (c2) and f(c1) f(c2), then T is not
optimal.
9. (optional for bonus credit) In the text book, 16.3-6, pp. 436.
10. Next page.
1
10. (programming question) Finding connected components in a binary image.
a) A Disjoint-Set data structure should be implemented, with the most efficient algorithm
(union by rank and path compression), as an abstract data type (a class in C++ or java)
with the following operations.
• uandf(n): constructs an disjoint-set data type with n elements, 1, 2, . . . , n.
• make set(i): creates a new set whose only member (and thus representative) is i.
• union sets(i, j): unites the dynamic sets that contains i and j, respectively, into a new
set that is the union of these two sets.
• f ind set(i): returns the representative of the set containing i.
• f inal sets(): returns the total number of current sets and finalizes the current sets:
(i) make set() and union sets() will have no effect after this operation and (ii) resets
the representatives of the sets so that integers from 1 to f inal sets() will be used as
representatives.
b) Design and implement (write a program) an algorithm to find the connected components
in a binary image using Disjoint-Set data structure in a).
An ASCII file containing a binary image is available (see girl.img and img readme) as the
input of your program. The output of the program should be the following in this specified
order:
1. the input binary image,
2. the connected component image where each component is labelled with a unique character,
3. a list sorted by component size, where each line of the list contains the size and the
label of a component,
4. same as 2 with the connected components whose sizes are less than three deleted.
In your gaul account, you should create a directory called ”asn2” which contains your
asn2 solution.pdf for question 1 to question 9 and the description of algorithm and the
explanation of correctness and complexity of f inal set() in 10 a) and your algorithm in 10
b); your program for question 10; the input file with name infile; and the makefile. The
makefile should be written such that the command ”make clean” will remove all the ”*.o”
files and the command ”make” will generate an executable file asn2 that can be run by
typing ”asn2 < infile”. If you are using Java or Python, you may not need the makefile. In
that case, you should have a shell script file, asn2, so that by typing ”asn2 < infile” your
java or python program will run.
You should use unix script command to capture the screen of the execution of your
program. The resulting file should also be in directory ”asn2”.
Your programs have to be able to run on compute.gaul.csd.uwo.ca as our TAs will be
marking your programs with this machine.
2
• To answer a question for designing an algorithm, the following three steps are needed
1. Describe your algorithm in English (not with pseudo code);
2. Show why the algorithm is correct; and
3. Analyse the complexity of the algorithm.
3