Ch. 4 Computer Science 201 Data Structures & Algorithms Exam Questions with Answers.

Ch. 4 Computer Science 201: Data Structures & Algorithms Exam Questions with Answers The ingredients in an algorithm are called: - Correct Answers: Inputs Instead of a list of steps, algorithms can be written using: - Correct Answers: Flowcharts with arrows to illustrate the journey A programming algorithm is like: - Correct Answers: A recipe An algorithm always leads to a(n): - Correct Answers: Solution An algorithm is written down as: - Correct Answers: A list of steps What is one major drawback of experimental analysis? - Correct Answers: Implementation of programs What are asymptotic notations? - Correct Answers: Notations that allow us to analyze an algorithm's running time by identifying its behavior as the input size for the algorithm increases. What is NOT an asymptotic notation? - Correct Answers: β If f(n) is the function then O(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. } is true for which of the following symptotic notations ? - Correct Answers: Big Oh An experimental analysis depends on the _____ results, so an algorithm cannot be measured unless an _____ is implemented. - Correct Answers: output; equivalent program Kara's code includes a binary search operation. Which of the following functions would be optimal to test the execution time of this function? - Correct Answers: Log n An algorithm tests the air pressure on a slope at different altitudes. Given that the pressure depends on the altitude, what is the optimal algorithmic function to use? - Correct Answers: Linear In a linear function, the time taken is _____ if the size of the input is doubled. - Correct Answers: doubled Out of a random bunch of last years' holiday greeting cards, Clara wants to find the one her mother sent her. The optimal algorithm to use will be _____. - Correct Answers: N-log-N Brian has an algorithm to read through an array that contains numbers 1 through 26 and convert each number to an English alphabet. He runs the algorithm a number of times with no changes to the size of the array and no changes to the task done. The function to use is: _____ - Correct Answers: f(n) = c What is the time complexity of the following ? i=0;while(i<n){ j=i;while(j<n && j<i+5){ /* code */j++;}i=j; } - Correct Answers: O(N) If one for loop runs with size N and the other with size M and the loops follow a linear function, what is the expected time complexity? - Correct Answers: O(M+N) What is space complexity? - Correct Answers: Amount of storage an algorithm needs to work If an algorithm runs in quadratic time, what is its time complexity using Big-O ? - Correct Answers: O(N2) For a linear function, what would be its time complexity? - Correct Answers: O(N) Which method is used to prove a mathematical statement true, by assuming the negation of it to also be true? - Correct Answers: contrapositive In algorithm analysis, space complexity describes _____. - Correct Answers: the total memory space consumed In loop variants, the relationship between the variables _____. - Correct Answers: is the same before and after the loops Why is it necessary to analyze an algorithm? - Correct Answers: All of the above Contrapositive and contradiction fall under which category of algorithm analysis? - Correct Answers: Contra Attack