Description
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
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
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 , 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 = (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.
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. 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 or
firstname_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 result
in 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…
a. Just one key – which is the answer to the main problem. This key should be the summation of any two keys. If you don’t find such a key, then write a 0 byte blank file.
b. 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.
