Analysis of algorithms | Computer Science homework help

CS 5200 Homework -1
(Deadline: 09-17-2023 11:59pm)

Instructor: Huiyuan Yang

Q1. Complexity analysis [11%]

1) Consider the following algorithm (assume n >1)

int any-equal (int n, int A[ ][ ]) {
Index i, j, k, m;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
for (k=1; k<=n; k++)
for (m=1; m<=n; m++)
if (A[i][j] == A[k][m] && !(i==k && j==m))
return 1;
return 0;
}

§ Show the best case; what is the best-case time complexity. [3%]
§ Show the worst case; what is the worst-case time complexity. [3%]
§ Try to improve the efficiency of the algorithm. [5%]

Q2. Growth of functions [15%]

1) Using the definition of O(.) and Ω(.), show that: [5%]
10𝑛 + 8 ∈ 𝑂(𝑛!), 𝑏𝑢𝑡 10𝑛 + 8 ∉ Ω(𝑛!)

2) Using the definition of Θ(. ) To show that: [5%]
2𝑛” + 2𝑛! + Θ(𝑛) ∈ Θ(𝑛”)

3) Show by using limits that: [5%]
I. 4!#$% ∈ Θ(16#)

II. 𝑛& − 𝑛! + 2𝑛 ∈ 𝜔(𝑛)

Q3. Master theorem [9%]

Find the asymptotic bound of the recurrence equations T(n) using master theorem when
applies:

I. 𝑇(𝑛) = 9𝑇(𝑛/3) + 𝑛! + 4
II. 𝑇(𝑛) = 6𝑇(𝑛/2) + 𝑛! − 2

III. 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛” + 7

Q4. Divide-and-Conquer [25%]

1) Solve the following recurrence equation using recursion tree. [7%]
𝑇(𝑛) = T(n/2) + T(n/4) + T(n/8) + n

2) We have a problem of size n, and two solutions to solve this problem: [8%]

a. Solution-I: runs 𝑛! times to solve this problem directly (non-recursive algorithm).
b. Solution-II: is a recursive algorithm, which takes 𝑛𝑙𝑜𝑔𝑛 times to split problem into

two sub-problems with equal size of 𝑛/2, and 𝑙𝑔𝑛 times to combine the results
together.

Show whether the solution-I or solution-II is more efficient.

3) Consider the following algorithm, which return a pair with minimum and maximum in
the list of A.[10%]

Min_Max (A, lt, rt) {
if (rt – lt ≤ 1)
Return (min(A[lt], A[rt]), max(A[lt], A[rt]));

(min1, max1) = Min_Max(A, lt, ⌊(lt + rt)/2⌋);
(min2, max2) = Min_Max(A, ⌊(lt + rt)/2⌋ + 1, rt);

Return (min(min1, min2), max(max1, max2));
}

§ Write the recurrence equation for the code above. [3%]
§ Solve the recurrence equation. [2%]
§ Show by example why the algorithm works. (hint: you can show each step when

call the Min_Max() function with a list of size 6, etc). [5%]

Q5. Programming [35%]
Implement the algorithm for finding the closest pair of points in two-dimension plane using the
Divide-and-Conquer strategy.

§ Compile without errors (by calling make) [5%]
§ Use the brute-force approach to solve the problem and print out the execution time. [5%]
§ Use the Divide-and-Conquer strategy to solve the problem and print out the execution

time. [25%]

Bonus: [Extra 20%]
Design an algorithm: Given an integer array of 2𝑛 integers.

(1) Partition the list into two arrays of length 𝑛, such that the difference between the
sums of the two sub-arrays is maximized; show the time complexity. [5%]

(2) Partition the list into two arrays of length 𝑛, such that the difference between the
sums of the two sub-arrays is minimized; show the time complexity. [15%]

Submission requirements: [5%]
Put the theory part and code into a folder with the name: [YourStudentID-YourName-HW1].zip

§ Following all the submission requirements [5%]
§ Theory part:

o You solution should be clear, concise but also contain enough details.
o Only PDF format is allowed.
o Please make sure the scanned PDF file is high-resolution and easily readable if

you wrote your solution on paper.
§ Programming part:

o A sanity check to test the correctness of your algorithm.
o Your program will read an input file and write an output file.
o Your program will be called like this: prompt>./hw1 ./input.txt. ./output.txt
o Your code should be complied by calling the makefile.