COMP S265F Design and Analysis of Algorithms Assignment 1
Due: 3 Mar 2024 (Sun) 23:59
Submit your answers in a single PDF file (Questions 1∼5) and a zip file for the Python codes and output graph (for Question 5) to OLE. Show your steps clearly.
Question 1 (24 marks). Multiple choice questions (4 marks per question). Note that there is only one correct option for each question.
(1) Which of the following is correct?
A. The original Euclid’s algorithm applies modulo operations in each iteration.
B. The smallest possible output of Euclid’s algorithm is 0.
C. Euclid’s algorithm works on negative numbers.
D. The improved Euclid’s algorithm has the time complexity of O(log max(a,b))
(2) How many modulo operations are required to find the gcd of 18 and 60 using the improved Euclid’s algorithm?
A. 1 B. 3 C. 5
(3) Which of the following has a time complexity of O(n2)?
D. 7
for i in range(n):
print("Hello World!")
print("\n")
for i in range(n):
for j in range(n):
print("Hello World!")
print("\n")
D. 2n +44n
print("Hello World!") A. print("Hello World!")
B.
D.
C.
print("\n")
i = 1
while i < n:
print("Hello World!")
i *= 2
(4) Which of the following has the highest time complexity? A. 100n3 B. n2logn+3n C. 55n+log2n
(5) What do we need to do in the divide stage of a divide-and-conquer algorithm? A. Apply arithmetic divisions.
B. Combine a series of solutions.
C. Store the solutions for subproblems.
D. Make the problem into a list of similar but simpler problems.
(6) What is the worst-case time complexity of MergeSort for n numbers? A. O(n log n) B. O(log n)
C. O(n) D. O(n2)
Question 2 (16 marks). Find the greatest common divisor of 135 and 385 using the following algorithm. Write down the two numbers in every intermediate step.
(a) (8 marks) Euclid’s algorithm with mutual subtractions (original algorithm). (b) (8 marks) Euclid’s algorithm with modulo operations (improved algorithm).
Question 3 (20 marks). Design a divide-and-conquer algorithm to find the minimum number in N = [a1,a2,...,an].
(a) (10 marks) Show your pseudo-code for this algorithm.
(b) (10 marks) The Master Theorem is for analyzing the time complexity T(n) of a divide-and-conquer algorithm on an input of size n, where T (n) is in the form:
T(n)=aT T(n) can be bounded asymptotically, as follows:
??n?? b
d
O(nd)
T(n)= O(ndlogn) ifd=logba
if d > logb a O(nlogb a) if d < logb a
Use this Master Theorem to get the T (n) for your algorithm.
Question 4 (16 marks). For a given set of numbers N = [15, 1, 10, 7, 23, 11, 17, 19, 3, 6, 9, 18, 15, 4, 2, 27, 35, 13],
we are using the Linear Time Selection algorithm to find the 11th largest number in this list.
(a) (10 marks) Determine the first pivot a by the ‘Median of the Medians’ strategy for dividing the list N into two sublists L and S. You need to keep the last group if there are less than 5 numbers in the group. You can select the upper median as the pivot in the final step. All the steps should be clearly shown.
(b) (6 marks) Determine if you need to keep L or S for the next dividing step, for recursively reaching the 11th largest number in N.
Question 5 (24 marks). Use the text document doc.txt as your program input S and complete the following tasks.
(a) (8 marks) Read the file and count the frequencies of the following letters Σ = {A, C, E, F, G}. Note letters are NOT case-sensitive. Write a function in Python to achieve this frequency-counting purpose, and also provide the frequencies in the single pdf file after you get them.
Hint. Instructions for function CompFreq(fn, chset):
• Use fl = open(fn, ’r’) to open a file named fn, and read it lines = fl.readlines();
• Define a dictionary stat = {i:0 for i in chset} to store the character-frequency pairs;
• Use the Counter function from collections package to count the frequency of each character in each line (change to upper cases), and update stat.
(b) (8 marks) Construct the Huffman code tree C for these characters with steps shown. Each step is in the format “Merge [node 1] and [node 2] to [node 3]”, where [node i] is either a character (e.g., M) or a tuple of characters that are merged to form the node (e.g. (M, N, P) means that the node is formed by merging characters M, N and P). You need to provide these steps in the single pdf file to show how to construct the Huffman code tree. In addition, you need to write a Python program for constructing and outputting the Huffman code tree (by graphviz), remember to submit the outputted tree graph (in pdf format).
(c) (8 marks) show the Huffman code for each character (e.g. A -> 0101) and compute the average character length LC(S) (rounded to 2 decimal points) of the Huffman code on these characters. You need to provide the Huffman code and LC(S) in the single pdf file, and also write a Python program for getting the code and LC(S).
+O(n )
