CS575 - DAA Assignment 1 - Solved

The assignment is designed to enhance the concept of time complexity, instruction counts, mathematics computation, and to implement an efficient program to solve a simple problem. 

 

There are two parts in this assignment: (A) Theory part and (B) programming part

 

[Part A] Theory [84%]:  The hardcopy of the Part-A must be handed in to the instructor in the class meeting.

 

1.    [6%] What is the smallest value of n such that an algorithm whose running time is   runs faster than an algorithm whose running time is   on the same machine? 

 

2.       [9%] What is the count for the instruction CountMe as a function of n for the fragments below? 

a.       [3%]
      Line 1: for (i=0; i<n3; i++ ){

Line 2:    for (j=0; j<n4/5; j++){

Line 3:       CountMe

           }

        } 



b.      [3%]

Line 1: j = n

Line 2: while (j > 0) {

Line 3:    CountMe 

Line 4:    j = j-2;

        } 



c.       [3%] For simplicity you may assume that n=2k for some positive integer k. 

Line 1: j = 1

Line 2: while (j<n) {

Line 3:    CountMe

Line 4:    j = 2*j; 
        }

3.       [8%] Prefix averages

Given an array X storing n numbers, we want to compute an array A such that A[i] is the average of the elements X[0], …, X[i] for i=0, …, n-1, or  .

 

For example if X = [1, 5, 10, 100], A[0]=1, A[1] = (1+5) / 2= 3, A[2] = (1+5+10) / 3= 5.333, and A[3] = (1+5+10+100) / 4 = 116/4 =29.

 

Computing prefix averages has many applications in economics and statistics. For example given year-by-year returns of a mutual fund, an investor will typically want to see the fund's average annual returns for the last year, the last three years, the last 5 years, and the last 10 years. 

 

Design your algorithm to calculate the prefix average values A[i].  Write the pseudo-code or C-code to demonstrate the procedure. Analyze the every-case time complexity by counting the barometer operation (e.g., “+” operation). Your algorithm must be in  time complexity.

 

 

4.       [12%] Award problem to students with blind tags

 

Problem: There are 30 students attending a university award ceremony. Each student has a tag labeled by either “A”, “B”, or “C”.  The tag is stick on the back of each student, which is visible only by the others except the student self.  Students are not allowed to communicate each other. In other words, each student is aware of other students’ labels but not aware of his/her own label. Suppose there are 5 students with “A”, 10 students with “B”, and 15 students with “C”.  During the ceremony, the university president announces that the award is given to students who have the label “A”, and asks the students to come to the podium to receive the award certificate.  (1) (8%) Explain how the students with “A” can figure out their label without communicating with other students and receive the certificate?   (2) (4%) Prove your solution by induction.

 

Note: After the announcement, the president will give maximum 30 chances to all students to figure out their own labels, with 1 minute for each chance. For example, the president will give the 1st minute to students to figure out their label, whoever figures out the own label with “A” will come to receive the certificate. If no one figures it out, the president will give a second chance (with 2nd minute), or continuing the third chance (3rd minute), fourth chance (4th minute), until thirtieth chance (30th minute) at maximum or stop at any round if all the students with “A” have figured it out and received the certificates. 

 

 

 

5.    [8%] Design an algorithm: Given a list of n distinct positive integers (you may assume that n is a multiple of 2), 

(1)  partition the list into two sublists, each of size n/2, such that the difference between the sums of the integers in the two sublists is maximized; show the time complexity;

(2)  partition the list into two sublists, each of size n/2, such that the difference between the sums of the integers in the two sublists is minimized; show the time complexity;

 

6.    [9%] 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;

}

 

(1)  Show the best case; what is the best case time complexity;

(2)  Show the worst case; what is the worst case time complexity; 

(3)  Try to improve the efficiency of the algorithm; 

 

 

7.    [8%] Using the definitions of O and W , show that 

           but    

 

8.       [8%] Given a list of distinct positive numbers and the average or mean of those numbers, following pseudo-code is to determine whether there are more numbers above the average than below. 

MoreAbove( list, average, N ) 

    countAbove = 0 

    for j = 1 to N do 

if list[ j ] > average then 

     countAbove = countAbove + 1 

     if countAbove > N/2 then  return true 

 

     return false 

Let’s take the “>” as the barometer operation. What is the count for the best case, and what is the count for the worst case?  Give your explanation.

 

9. [8%]

Alternating disks: You have a row of 2n disks of two colors, n dark and n light. They alternate: dark, light, dark, light, and so on. You want to get all the dark disks to the right-hand end, and all the light disks to the left-hand end. The only moves you are allowed to make are those which

interchange the positions of two neighboring disks.

 

 

 

Design an algorithm for solving this puzzle and determine the number of moves it makes. (You algorithm should not be worse than O(n2).  Note: describe your approach without pseudo-code.

 

 

 

(10)      (8%) Suppose f + g are two functions (taking nonnegative values) such that g = O(f). Prove f + g = q(f); in other words, f is an asymptotically tight bound for the combined function f + g.

 

 

[Part B]: Programming (warm-up) (16%)

 

1.  Given an array containing n keys, design an algorithm to determine whether there exists such a key which is equal to the summation of other two keys in the array. Explain the worst-case time complexity. (no sequential search is allowed).

 

Input data (For example: Array A[ ])

 

A[ ] = 18   23   4   35   99   67   198   20   38   55   2  18   19   487   11  40 10  13  27  22      

 

 

2. Write-up:

     

(a)  Provide a readme file to explain how to run your program, and show your code and results. (9%).

 

(b)  Explain your implemented algorithm and show its worst-case time complexity (4%)

 

Extra points (5%):  Print out all the keys that are equal to the sum of the other two keys in the array, and print out the corresponding two keys.