Computer Science analysis of algorithms assignment

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.

__MACOSX/hw1/._CS 5200 Homework-1.pdf