[Solved] CS575 Assignment 1

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 : The hardcopy of the Part-A must be handed in to the instructor in the class meeting.

1. 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. What is the count for the instruction CountMe as a function of n for the fragments below?
   1. [3%]Line 1: for (i=0; i<n³; i++ ){

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

Line 3: CountMe

}

}

1. [3%]

Line 1: j = n

Line 2: while (j > 0) {

Line 3: CountMe

Line 4: j = j-2;

}

1. [3%] For simplicity you may assume that n=2^k 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 funds 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. 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 1^st 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 2^nd minute), or continuing the third chance (3^rd minute), fourth chance (4^th minute), until thirtieth chance (30^th 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),

• 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;
• 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;

}

• Show the best case; what is the best case time complexity;
• Show the worst case; what is the worst case time complexity;
• 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

Lets 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(n²). Note: describe your approach without pseudo-code.

• (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

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:

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

• 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.

3. Program demo (3%)

TA will run your program. To test your program, you are required to provide your own test sets (contained in the inputFile.txt). For example, you should identify the test sets including cases with such key, without such key, or with more than one such key.

In addition, your program will be tested by a new inputFile.txt which is designed by TA as well.

4. 4. Part B: Submission specification

4.1 For Part B, submit one zip file of your code package to the blackboard, including your code, makefile, and write-up (e.g., .doc). The title is:

firstname_lastname_programming_language_used.tar.gz orfirstname_lastname_programming_language_used.zip

4.2 All your files including a Makefile must reside in one TOP level directory named firstname_lastname_programming_language_used.

4.3 The TA will compile your code using your Makefile. That should resultin the executable files. For this assignment there would be just one executable file. It should be named submission. This will be created by running the Makefile supplied by you.

4.4 Your program MUST take command line arguments.

4.5 Your program will read an input file and write an output file.

4.6 Your program should be invoked like this

prompt>submission inputFile.txt outputFile.txt

where inputFile.txt is referring to an input file,

ouputFile.txt is referring to an output file.

4.7 Sample input & output files will be provided. Please adhere to the file formats specified by the examples (2019Fall_SampleInputOutputCode_TA.rar).

4.8 For this assignment there would be one input file, which will have one key per line. The number of lines is variable; follow the example to know how to read a variable length file.

4.9 For this assignment the output file will contain either of

1. Just one key which is the answer to the main problem. This key should be the summation of any two keys. If you dont find such a key, then write a 0 byte blank file.
2. Or if you are attempting the extra credit then you write all instances of a key matching the summation of two other keys. In which case each line will have 3 keys. The first key should be the summation of the other two keys. The other two keys should be in increasing order. Write the 3 keys with whitespaces to delimit. Please look at the example to understand. If there are no such matching keys then you output a 0 byte blank file.

4.9 To test your program, you are required to provide your own test sets (contained in the inputFile.txt). For example, you should identify the test sets including cases with such key, without such key, or with more than one such key.

Your program will be tested by the inputFile.txt which is designed by TA as well.