ZIP

Comp 352 Data Structure and Algorithms Assignment 1 Solved

35.00 $

Category:

Description

5/5 - (4 votes)

 

Computer Science and Software Engineering

Question 1

 

  1. Given an array A of integers of any size, n ≥ 0, write an algorithm as a pseudo code (not a program!) that would find out the total number and their sum of even positive numbers as well as the total number and their sum of odd positive numbers in the array. For instance, assume that array A is as follows:

 

5 -2 4 9 -250 99 108 -62 46 13

 

The algorithm would find the number of positive even numbers is 3 and their sum is 4+108+46=158 and the number of positive odd numbers is 4 and their sum is 5+9+99+13=126. Your algorithm must handle possible special cases. Finally, the algorithm must use the smallest auxiliary /additional storage to perform what is needed.

 

  1. What is the time complexity of your algorithm, in terms of Big-O?

 

  1. What is the space complexity of your algorithm, in terms of Big-O?

 

Question 2

 

Prove or disprove the following statements, using the relationship among typical growth-rate functions discussed in class:

 

  1. 45 n2 + 28 n + 752 is Ω(n)

 

  1. 256 n + 8 n log n is Θ(log n)

 

  1. n8 + log n is O(log n)

 

  1. 2 n2 log n + n3 is Θ(log n)

 

  1. 4 n log2 n + 3 n2 log n is O(log n)

 

  1. n7 + 0.00000001n6 is Ω(n6)

 

 

Question 3

 

Consider the following algorithm:  

 

Algorithm arraySpecialSum(A, n)

    

currentMaxA[0]                               for i  1 to n − 1 do                       if A[i]  currentMax then                   currentMaxA[i]                    { increment counter i }

 

CurrentMaxOccurence = 0         for i  0 to n − 1 do                        if A[i] == currentMax then                      { increment currentMaxOccurence}

{ increment counter i }

 

specialSum = 0       for i  0 to n − 1 do                for j  1 to currentMaxOccurence do                    { specialSum = specialSum + A[i] }

{ increment counter j }

{ increment counter i }

 

return specialSum

 

 

  1. Use the analysis from the course notes to determine a time complexity function f(n) for the above algorithm. Your answer must be simple and concise.

 

  1. What is the time complexity of this algorithm, in terms of Big-O?

 

  1. What is the space complexity of this algorithm, in terms of Big-O?

 

  1. Can we improve this algorithm to achieve a better time complexity and still return the same specialSum value?
  2. If yes:
    • give a new algorithm that achieves it.
    • provide a time complexity function f(n) for the modified algorithm.
    • provide the time complexity of the modified algorithm, in terms of Big-O.
    • provide your observations regarding the two algorithms with respect to time complexity.

 

  1. If no, provide explanations as to why it cannot be improved.

 

Programming Questions

 

We received a list of people that are going to participate in a clinical test. The list includes the name and date of birth of the participants which is stored in two arrays: pName and pDOB. The two arrays are of the same size. The arrays’ size N is the number of participants. pName[0] hold the name of the first participant and pDOB[0] hold the date of birth of the first participant; pName[N-1] hold the name of the last participant and pDOB[N-1] hold the date of birth of the last participant. The participants’ information is stored in the arrays at random. We need to separate the participants in two groups: seniors and non-seniors. A person is considered senior if she/he is 65 years of age or older. You need to provide an algorithm that takes as input the two arrays and the number of participants. Your algorithm should rearrange the participants’ information in the arrays in the following manner:

  • Array position zero hold the information of the oldest person in the participants.
  • Array position N hold the information of the oldest non-senior participant.
  • Senior participants should be stored in a decreasing order based on their age.
  • Non senior participants should be stored in an increasing order based on their age.

 

A sample of two input arrays of size 10 and their contents after rearrangements by the algorithm is shown below:

 

 

Index
0
1
2
3
4
5
6
7
8
9
 

Algorithm inputs  

 

 

 

 

 

 

 

 

 

 

 

 Algorithm outputs
pName pDOB pName pDOB
Linda 1-1-2003 Sam 24-2-1940
Sam 24-2-1940 Maria 9-5-1941
Roger 11-12-1995 Melissa 25-7-1945
Alfred 31-3-1980 Roberto 29-6-1950
Roberto 29-6-1950 Thomas 20-7-2004
Melissa 25-7-1945 Linda 1-1-2003
Brian 15-7-2002 Brian 15-7-2002
Thomas 20-7-2004 Roger 11-12-1995
Leslie 27-4-1990 Leslie 27-4-1990
Maria 9-5-1941 Alfred 31-3-1980

 

 

  1. In this programming assignment, you will design an algorithm (in pseudo code), and implement (in Java), four functions as follows:
    • rearrangeParticipants: a recursive function that take as input two arrays pName and pDOB and the number of paticipants, and returns the number of senior participants in addition to arranging the arrays as specified above.
    • displaySeniorsIncreasingOrder: a recursive function that takes as input the two arrays pName and pDOB and the number of senior participants and display the name and DOB of senior participants in an increasing order based on their age.
    • displayNonSeniorsInreasingOrder: a recursive function that takes as input the two arrays pName and pDOB, the number of non-senior participants and the total number of participants and display the name and DOB of non-senior participants in an increasing order based on their age.
    • displayIncreasingOrder: this function takes as input the two arrays pName and pDOB, the number of senior participants and the total number of participants and display all participants in an increasing order based on their age.

 

All your algorithms must handle possible special cases. For each implemented function you need to compare the runtime performance and measure the corresponding run times. You can use Java built-in time function for this purpose.

You can generate a file with random data and experiment your implementation against different size of participants’ list size N in {10, 100, 1000, 10000, 100000…,1000,000}. You should redirect the output of each set of test size to an out.txt file. You should write about your observations on the timing measurements in a separate text file. You are required to submit the fully commented Java source files, the compiled files, and the text files.

 

For each implemented function:

  • Use the analysis from the course notes to determine a time complexity function f(n). Your answer must be simple and concise.
  • What is the time complexity of the function in terms of Big-O?

 

  1. For rearrangeParticipants recursive algorithm:
    • Briefly explain whether your algorithm is linear or not.
    • Does your algorithm use tail recursion? Why or why not? Explain your answer. If your answer is “No” then: can a tail-recursive version for this algorithm be designed?
      1. If yes; write the corresponding pseudo code for that tail recursion algorithm and implement it in Java and repeat the same experiments as in part (a) above.
      2. If no, explain clearly why such tail-recursive algorithm is not feasible.

 

 

  • Ass-1-x6hgib.zip

Related products