Answer Happy

Background: When selecting an algorithm to use, we'll encounter the challenge of comparing two or more algorithms for their efficiency, as well as determining their correctness for an intended application. In solving this challenge, we first determine what is most important when selecting a solution to the problem being solved that is, whether the time, or space, or some other computer resource, will be efficiently used to solve the problem. In an effort to reduce biases when selecting an algorithm, we examine the order of growth for the execution time for each algorithm, and not the exact time the execution takes to solve the problem. More specifically, we describe algorithms by using the following asymptotic notations: O-notation -for giving the upper bound on a function; 2-notation -for giving the lower bound on a function; and O-notation -for giving a tight bound for a function. Scenario: A Management Information System (MIS) is needed so as to track the performance of K-13 students enrolled in tertiary institutions across the island. Due to the fact that an array data structure facilitates easy implementation for sorting and/or searching techniques, the use of arrays have been proposed for storing the record of each students' data. However, it has been noted that the implementation will not permit the capture of data for any new student once the semester has begun. Questions: 1. Explain the term 'correctness of an algorithm'. 2. Justify, with the use of ANY TWO reasons, the need for analysing algorithms. [3 marks] [6 marks] 3. a. i. Explain how the array data structure may allow the MIS to be created in O(nlgn) time. Let n represent the amount of student records to be stored. [2 marks] ii. Explain how the array data structure may permit the retrieval of any student's record in O(lgn) time. [2 marks] b. Recommend, and justify, ANY OTHER data structure that may permit the creation and retrieval of student's record in a time that is more efficient than an array data structure. [4 marks]
4. Outline, with the use of an example, the appropriate uses for EACH of the given asymptotic notations (see Background). [9 marks] 5. a. Give the pseudo-code algorithm for the quick sort, and ANY OTHER TWO sort algorithms. [6 marks] b. Using the O-notation, give the execution time for all pseudo-code algorithms in 5 part a. Show ALL working. [6 marks] c. Based on the analysis done in 5 part b, recommend a sort algorithm for implementation and use within the MIS. [1 mark] 6. Consider the following function, such that it is represent an algorithm's time for execution: f(n) = n³ + 1 Explain why the following sentence provides no meaningful information about the execution time for the algorithm: "The execution time for the algorithm is at most 7. Give the order of growth for each of the following: 100 a. 10n + Ign b. nlgn c. (Ign)" d. 2n+1 12 Ign f. Iglgn e. 8. Consider the following: Each K-13 student is allowed to transfer credits, already obtained from one tertiary institution, and continue studies in another programme either at the same or different university. (³)." [3 marks] [6 marks] Describe how a graph could be used to represent the statement. More specifically, state what a node and an edge would represent. [2 marks]