__Exam 1:__

**This exam contains three problems asking **

**multiple questions**

**. Please answer each question**

__in detail with clear explanation__. 🙂__Problem 1.__

- What is the growth of the below functions?
**Explain in detail and**.__show ALL the work__ - Compare the growth of
*Test1(n)*and*Test2(n)*.**Show all the work**. - Let’s say you can finish running
*Test2(10*in^{6})*1*Could you estimate when you finish running*Test1(100)*?

** Problem 2.** A sorted array and a random number are given to you. Develop an algorithm to find the total number of the repetitions of the given number.

* Example 1*:

*: a = [0, 1, 1, 2, 2, 2, 3, 3, 6], key = 2 ➔*

__Input__*: “2 was repeated 3 times.”*

__Output__* Example 2*:

*: a = [0, 0, 2, 2, 3, 9, 10, 12, 15], key = 10 ➔*

__Input__*: “10 was repeated 1 times.”*

__Output__* Example 2*:

*: a = [0, 1, 3, 8, 12], key = 5 ➔*

__Input__*: “5 was repeated 0 times.”*

__Output__- How would you find the total number of repetitions for the given number? (
**Note**: If you have multiple answers in mind, break them apart and explain each one separately.) Explain each solution/algorithm in a few lines.

- Write the pseudocode for the best algorithm you came up with.

- Implement your answer using any programming language you want to.

- What is the time complexity of your answer?
**Explain in detail and show all the work**. (**Note**: If possible, break your code/pseudocode to different parts, calculate the runtime for each step and then try to calculate the total running time based on that.)

** **

** **

** Problem 3.** A random array of size

*n*is given to you. You know that the elements in the array are nonnegative integers less than

*n*. Develop an algorithm to

__find the mode__(the value that appears most)

__and the numbers repeated more than once__.

* *

* Example 1*:

*: a = [6, 0 ,1, 5, 1, 1, 4, 5], ➔*

__Input__*: “1 is the mode.”*

__Output1__* Output2*: “6 was repeated 2 times,

- was repeated 3 times.”

* Example 2*:

*: a = [0, 2, 4, 2, 2, 0, 0, 5, 4], ➔*

__Input__*: “0 and 2 are the mode.”*

__Output1__* Output2*: “0 was repeated 3 times,

- was repeated 3 times,

4 was repeated 2 times.””

** **

**(Hint**: Remember the algorithms we learned in the class (searchings and sortings). Could you pick a good one and use parts of it to solve this question?)

- How would you find the mode and the numbers occurring more than once? (
**Note**: If you have multiple answers in mind, break them apart and explain each one separately.) Explain each solution/algorithm in a few lines.

- Write the pseudocode for the best algorithm you came up with.

- Implement your answer using any programming language you want to.

- What is the time complexity of your answer?
**Explain in detail and show all the work**. (**Note**: If possible, break your code/pseudocode to different parts, calculate the runtime for each step and then try to calculate the total running time based on that.)

## Reviews

There are no reviews yet.