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.

Try it now!

How it works?

Follow these simple steps to get your paper done

Place your order

Fill in the order form and provide all details of your assignment.

Proceed with the payment

Choose the payment system that suits you most.

Receive the final file

Once your paper is ready, we will email it to you.

Our Services

Quality Essay Help has stood as the worldβs leading custom essay writing services providers. Once you enter all the details in the order form under the place order button, the rest is up to us.

Essays

At Quality Essay Help, we prioritize on all aspects that bring about a good grade such as impeccable grammar, proper structure, zero-plagiarism and conformance to guidelines. Our experienced team of writers will help you completed your essays and other assignments.

Admissions

Admission and Business Papers

Be assured that youβll definitely get accepted to the Masterβs level program at any university once you enter all the details in the order form. We wonβt leave you here; we will also help you secure a good position in your aspired workplace by creating an outstanding resume or portfolio once you place an order.

Editing

Editing and Proofreading

Our skilled editing and writing team will help you restructure you paper, paraphrase, correct grammar and replace plagiarized sections on your paper just on time. The service is geared toward eliminating any mistakes and rather enhancing better quality.

Coursework

Technical papers

We have writers in almost all fields including the most technical fields. You donβt have to worry about the complexity of your paper. Simply enter as much details as possible in the place order section.