MTH251: If an Algorithm Has Been Implemented, We can Study its Running time by Executing it on Various Test Inputs: Data Structures and Algorithms I Coursework, Singapore

Every question is 5 marks.

1.If an algorithm has been implemented, we can study its running time by executing it on various test inputs and recording the time spent during each execution. Describe an approach how to accomplish such experiments.

2.While experimental studies of running times are valuable, there are three major limitations to their use for algorithm analysis. Describe any two of them.

3.Implementation of the algorithm might be difficult, and the result might not be indicative of the running times on other inputs not included in this experiment. Besides, the same hardware and software environments must be used if need to compare two algorithms at the same time.

Write a generator in Python to return the first 50even numbers starting with

Also, write a code snippet to print the numbers from the generator.

4.Assuming that a stack S is implemented as a list L in Python, list the corresponding Python statement with the Stack ADToperation:

S.top(), S.is_empty(), S.push(), len(S), S.pop()

5.Briefly name and provide examples of any four (out of seven) most important functions used in the analysis of algorithms in this subject.

6.Sort the following functions in an order of increasing bigO: a. f(x) = 1 +x/100

f(x) = 1,000,000

f(x) = x + x² / 200

f(x) = 2^x

7.Using the definition of big-O, explain why “The function 8n + 5 isO(n).”

8.The factorial of a positive integer n, denoted n! is defined as the product of the integers from 1ton.Ifn=0,then!isdefinedas1byconvention.Write a recursive implementation of the factorial function.

9. What is the big-O complexity of “2n + n 100 log”?

10. List the preorder and inorder traversal for the following binary tree.

11. Estimatethebig-Ocomplexityofanalgorithmfromthefollowingresult

12. Using the above table of logarithm rules, simplify

a. log₂(n*n)

b. log₂(n/2)

c. log₂(n³)

d.log₂ (2ⁿ)

13. Name and describe two advantages and two disadvantages of using array-based sequences over link-list-based.

Advantage – Array will take less amount of space per item by itself compared to link-list.

Disadvantage – However, if we need to store more elements, it will lead to an increase in the size causes a long consumption of time. Sometimes will cause a waste of space.

Advantage – It is easy to use and implement using for loops as we can store similar items together, so it is a very efficient structure if we know the size.

Disadvantage – Insertion, and deletion from link-list are easier than array because for the array, we need to insert and delete in the middle of the sequences and shift the items towards left or right depends on insertion or deletion.

14. Python’s dictclass is arguably the most significant data structure in the language. Name four common dictionary operations and provided their corresponding big-Os.

15. What is a hash function? Provide two examples with brief explanations.

16.Draw the 11-entry hash table that results from using the hash function(k)

= (3k + 7) mod 11 to hash the keys 10, 20, 11, 9, 15, 2, 6, 17, and 22

a.Assuming collision resolutions are handled by linear probing.

b. Assuming collision resolutions are handled by quadratic probing (up to the point where the method fails).

17. Describe the depth-first search of a directed-graph

18. Write a recursive function in Python to find the sum of squares of all elements in a list. The list may be passed as a parameter to the function and the calculated sum should be returned.

The next 2 questions are based on the following quick-sort description

19. What is big-O of the quick-sort and why?

20. Show a sequence of steps to sort [1, 2, 5, 3, 4] using the quick-sort. Count the number of operations.