Background: When selecting an algorithm to use, we’ll encounter the challenge of comparing two or more algorithms for th

[answerhappygod]

Background: When selecting an algorithm to use, we’ll encounterthe challenge of comparing two or more algorithms for theirefficiency, as well as determining their correctness for anintended application. In solving this challenge, we first determinewhat is most important when selecting a solution to the problembeing solved – that is, whether the time, or space, or some othercomputer resource, will be efficiently used to solve the problem.In an effort to reduce biases when selecting an algorithm, weexamine the order of growth for the execution time for eachalgorithm, and not the exact time the execution takes to solve theproblem. More specifically, we describe algorithms by using thefollowing asymptotic notations: Ο-notation –for giving the upperbound on a function; Ω-notation –for giving the lower bound on afunction; and Ө-notation –for giving a tight bound for a function.Scenario: A Management Information System (MIS) is needed so as totrack the performance of K-13 students enrolled in tertiaryinstitutions across the island. Due to the fact that an array datastructure facilitates easy implementation for sorting and/orsearching techniques, the use of arrays have been proposed forstoring the record of each students’ data. However, it has beennoted that the implementation will not permit the capture of datafor any new student once the semester has begun. Questions:
1. Explain the term ‘correctness of an algorithm’. [3 marks]
2. Justify, with the use of ANY TWO reasons, the need foranalysing algorithms. [6 marks]
3. a. i. Explain how the array data structure may allow the MISto be created in Ο(𝑛lg𝑛) time. Let n represent the amount ofstudent records to be stored. [2 marks]
ii. Explain how the array data structure may permit theretrieval of any student’s record in Ο(lg𝑛) time. [2 marks]
b. Recommend, and justify, ANY OTHER data structure that maypermit the creation and retrieval of student's record in a timethat is more efficient than an array data structure. [4 marks]
4. Outline, with the use of an example, the appropriate uses forEACH of the given asymptotic notations (see Background). [9marks]
5. a. Give the pseudo-code algorithm for the quick sort, and ANYOTHER TWO sort algorithms. [6 marks]
b. Using the Ο-notation, give the execution time for allpseudo-code algorithms in 5 part a. Show ALL working. [6 marks]
c. Based on the analysis done in 5 part b, recommend a sortalgorithm for implementation and use within the MIS. [1 mark]
6. Consider the following function, such that it is represent analgorithm’s time for execution: f (n) = n3 + 1 Explain why thefollowing sentence provides no meaningful information about theexecution time for the algorithm: “The execution time for thealgorithm is at most Ω(n3).” [3 marks]
7. Give the order of growth for each of the following: a. 10𝑛+100lg𝑛 b. 𝑛lg𝑛 c. (lg𝑛)𝑛 d. 2𝑛+1 e. 𝑛lg𝑛 f. lglg𝑛 [6 marks]
8. Consider the following: Each K-13 student is allowed totransfer credits, already obtained from one tertiary institution,and continue studies in another programme either at the same ordifferent university. Describe how a graph could be used torepresent the statement. More specifically, state what a node andan edge would represent. [2 marks]