KHAN ACADEMY ALGORITHMS LIST 2024 WITH COMPLETE SOLUTION

KHAN ACADEMY ALGORITHMS LIST 2024 WITH COMPLETE SOLUTION A statistician developed this procedure to calculate the "variance" of a list of numbers. The variance is a statistical quantity that corresponds to the average of the sum of the squared differences of each number from the mean. As input, the procedure takes a list of numbers and its mean: PROCEDURE calculateVariance(numbers, mean) { count ← 0 sumSquaredDiffs ← 0 FOR EACH num IN numbers { diff ← (num - mean) squaredDiff ← diff * diff sumSquaredDiffs ← sumSquaredDiffs + squaredDiff count ← count + 1 variance ← sumSquaredDiffs / count } RETURN variance } The statistician verifies the procedure outputs the variance correctly, but they still want to improve the efficiency of the procedure by reducing the number of operations required. Which change will reduce the most number of operations while still outputting a correct answer? Ans- Moving the calculation of variance to be after the loop (but before the return) The following algorithm computes the maximum score for a list of final exam scores. Initialize a variable max to the first score in the list. For each score in the list, compare the score to max. If score is greater than max, store score in max Return max. Which building blocks are involved in this algorithm? ️Note that there may be multiple answers to this question. Ans- Selection Iteration Sequencing ScootALot is a scooter rental service. At the end of each day, they hire contractors to pick up scooters and distribute them optimally around the city. The distribution algorithm considers all the possible locations for the scooters, compares that to the density of customers, and comes up with the optimal location for each scooter. As the company becomes more popular, they realize their algorithm is taking an unreasonable amount of time to come up with optimal scooter locations. What is the best way to improve the run time of the algorithm? Ans- Use a heuristic-based algorithm that suggests good locations for the scooters. An algorithm will be used to calculate the difference between the smallest and largest values in a list. For the list of [10, 3, 5, 6], it should calculate a difference of 7. There are two proposals for the algorithm: Algorithm 1: Set minVal to the first value in the list and maxVal to the last value in the list. Iterate through each number in the list. If the number is greater than maxVal, store it in maxVal. If the number is less than minVal, store it in minVal. After loop, set maxDiff to the difference between maxVal and minVal. Algorithm 2: Set minVal to 1000 and maxVal to 0. Iterate through each number in the list. If the number is greater than maxVal, store it in maxVal. If the number is less than minVal, store it in minVal. After loop, set maxDiff to the difference between maxVal and minVal. Which of these statements are true about these algorithms? I. Algorithm 1 does not work on lists where the smallest valu Ans- II only The flow chart below visualizes an algorithm to generate the Fibonacci numbers, a famous mathematical sequence. If the variable max is set to 5, what would be displayed as a result of executing this algorithm? Ans- 1 2 3 5 8 Yuto implements an algorithm for finding the "greatest common divisor" of two numbers. For the numbers 54 and 24, it finds a greatest common divisor of 6. He counts the number of steps required by the algorithm for numbers of increasing digit length and comes up with this table: Number of digits Steps 2 4 3 6 4 8 5 10 6 12 Based on the table, which of the following statements describe the run time for this algorithm? ️Note that there are 2 answers to this question. Ans- The algorithm runs in polynomial time. The algorithm runs in reasonable time. An online app for playing Chess utilizes a variety of algorithms. Their software engineers would like the algorithms to run in under a second so that users have a great experience. Which algorithm's runtime is most likely to be improved by the use of a heuristic? Ans- Choosing a good move when the computer is playing against the human A restaurant delivery app uses the following algorithm to choose the restaurants it features to each user. Which pseudocode is equivalent to the algorithm in the flowchart? Ans- IF (openNow = true AND milesAway < 5 AND reviews > 3.5) { showFeatured ← true } ELSE { showFeatured ← false } The algorithm below determines whether a given year is a leap year. If year is not divisible by 4, set leap_year to false Else if year is not divisible by 100, set leap_year to true Else if year is not divisible by 400, set leap_year to false Else, set leap_year to true. Which of these tables correctly shows the results of this algorithm on the given values of year? Ans- year leap_year 1900 false 1984 true 2000 true 2002 false A 5 year old visits the Computer History Museum and gets excited about everything computers can do. They ask their mother, "Mom, can computers solve every problem?" Which response is the most accurate? Ans- There are some problems a computer can't solve, no matter how much time they have. A mathematician comes up with an algorithm for multiplying two matrices together. This table shows how many steps the algorithm requires for different matrix sizes: Matrix size Steps 1 1 2 8 3 27 4 64 5 125 Which function best describes how the number of steps changes as the matrix size (n) increases? Ans- n^3 A programmer wants to present their idea for an algorithm at a company meeting. They're debating whether to express the algorithm in flow charts, pseudocode, or a programming language. Which of these is a good argument for expressing the algorithm in a flow chart at the company meeting? Ans- Flow charts can require less technical knowledge to understand than pseudocode or programming languages. The two algorithms below are both intended to calculate the sum of squares from 1 to n, where n is any positive integer. For example, if n is 333, the algorithms should calculate a sum of 141414, from 1^2 + 2^2 + 3^21 2 +2 2 +3 2 1, start superscript, 2, end superscript, plus, 2, start superscript, 2, end superscript, plus, 3, start superscript, 2, end superscript. Algorithm 1: i ← 1 sum ← 0 REPEAT n TIMES { sum ← sum + (i * i) i ← i + 1 } Algorithm 2: i ← 1 sum ← 0 REPEAT n TIMES { sum ← sum + (i + i) i ← i + 1 } Which statements best describe the behavior of the algorithms? Ans- Algorithm 1 calculates the correct sum, but algorithm 2 does not. The two procedures below are both intended to find a target string in a list of strings. They should return true if they find the string and false if they do not. Procedure #1: PROCEDURE findString(strings, targetString) { index ← 1 foundString ← false REPEAT UNTIL (index > LENGTH(strings)) { IF (strings[index] = targetString) { foundString ← true } index ← index + 1 } RETURN foundString } Procedure #2: PROCEDURE findString(strings, targetString) { index ← 1 REPEAT UNTIL (index > LENGTH(strings)) { IF (strings[index] = targetString) { RETURN true } index ← index + 1 } RETURN false } Which of the following best describes the two procedures? Ans- Both procedures return the correct value, but procedure #1 requires more operations on average than procedure #2. Sariah is writing a research paper for literature class where she must cite many sources. She decides to make a tool to automate the citation process, and comes up with the following algorithm for citing a book: Split author name into first name and last name. Combine last name, comma, first name, and period. Combine title with period, and wrap in italics style. Combine publisher, comma, year published, and period. Combine strings from steps 2-4. After using the algorithm successfully for a single book, she decides to extend it to generate citations for all of her books at once. What structure must be added to the original algorithm so that it can operate on multiple books? Ans- Iteration Akuchi develops an algorithm that counts the number of words used in an essay. Now they've been asked to extend the algorithm to ignore common words (like "the" and "to"). What structure must be added to the algorithm so that it does not count common words? Ans- Selection A software engineer is developing a new operating system. The operating system has to make a decision when it sees an application taking a long time to finish executing an instruction. Should the operating system force quit the application, assuming it will run forever? Or can the operating system detect that the application will finish processing, if it has a bit more time? The engineer does some research and discovers that this is an undecidable problem. What are the implications of the problem being undecidable? Ans- The problem may be solvable in some cases, but there is no algorithm that will solve the problem in all cases. A programmer develops the procedure maxPairSum() to compute the sum of subsequent pairs in a list of numbers and return the maximum sum. For example, for a list of [2, 3, 4, 1], the sums of subsequent pairs are 5 (from 2 + 3), 7 (from 3 + 4), and 5 (from 4 + 1). The procedure should return the maximum sum of 7. PROCEDURE maxPairSum(numbers) { i ← 1 maxSum ← 0 REPEAT UNTIL (i = LENGTH(nums)) { sum ← nums[i] + nums[i + 1] IF (sum > maxSum) { maxSum ← sum } i ← i + 1 } RETURN sum } The programmer tests it with maxPairSum([5, 4, -4, 3, 2]) and sees a return value of 9. Can the programmer conclude that the procedure works correctly for all inputs? Ans- No, they've only verified that it works for that test case. Additional analysis and reasoning is necessary. A university library contains 30,000 books. One of the librarians is developing a program that can search through a list of those books, sorted by their title, to determine whether they have a particular title. They need to decide whether to use the linear search or binary search algorithm. Which of the following statements are true about those algorithms? I. Binary search is more efficient than linear search on sorted lists. II. Linear search is more efficient than binary search on sorted lists. III. Binary search is more efficient than linear search on both sorted and unsorted lists. IV. Linear search and binary search are equally efficient on all types of lists. Ans- Only I Hearify is an online music streaming service. They want to introduce a new feature that automatically generates 60-minute long playlists of popular music in different genres. They want each playlist to be exactly 60 minutes long and to include the most highly rated songs possible. They develop the feature but discover that it takes a long time for the computer to consider all the possible combinations of songs, and that extra time costs them money. Can the run time of the feature be improved? Ans- Yes, they can speed up the run time by using a heuristic to output a playlist that is not optimal, but close enough. The following algorithm computes the standard deviation of all the scores on the AP Computer Science Principles exam: Compute the average of all the scores. For each score, compute the square of its difference from the average. ..................