16.8. ExercisesÂ¶
Youâ€™re going to write a function that takes a string as a parameter and returns a list of the five most frequent characters in the string. Eventually, you will be able to do this sort of problem without a lot of coaching. But weâ€™re going to step you through it as a series of exercises.
First, the function will count the frequencies of all the characters, as weâ€™ve done before, using a dictionary and the accumulator pattern. Then, it will sort the (key, value) pairs. Finally, it will take a slice of the sorted list to get just the top five. That slice will be returned.
Step 1. Suppose you had this list, [8, 7, 6, 6, 4, 4, 3, 1, 0], already sorted, how would you make a list of just the best 5? (Hint: take a slice).
Now suppose the list wasnâ€™t sorted yet. How would get those same five elements from this list?
Now take a list L and make a dictionary of counts for how often these numbers appear in the list.
Now sort the keys (numbers) based on their frequencies. Review Sorting a Dictionary if youâ€™re not sure how to do this. Keep just the top five keys.
Finally, generalize what youâ€™ve done. Write a function that takes a string instead of a list as a parameter and returns a list of the five most frequent characters in the string.
16.8.1. Contributed ExercisesÂ¶
You took a road trip and tracked your miles and gallons of gas consumed over three different legs of the trip. This data is stored in the dictionary road_trip
, where the key is the name of the leg and the value is a tuple in which the first value is the miles traveled and the second value is the gallons of gas consumed. Created a list called fuel_efficiencies
that contains the keys (“legA”, “legB”, etc.) sorted from most fuel efficient to least.
 Constant
 Linear
 Quadratic
 Exponential
Q1: What is the complexity of looping through a list of integers and printing each one?
Put the following runtimes in order of complexity, from least to most.

Q1: Drag each bigO expression on the left to its name on the right.
This is feedback.
 \(O(1)\)
 Constant running time
 \(O(\log n)\)
 Logarithmic running time
 \(O(n)\)
 Linear running time
 \(O(n\log n)\)
 Loglinear running time
 \(O(n^3)\)
 Polynomial running time
 \(O(2^n)\)
 Exponential running time
 5
 Five comparisons would get the second 18 in the list.
 10
 You do not need to search the entire list, only until you find the key you are looking for.
 4
 No, remember in a linear search you start at the beginning and check each key until you find what you are looking for or exhaust the list.
 2
 In this case only 2 comparisons were needed to find the key.
Q1: Suppose you are doing a linear search of the list [15, 18, 2, 19, 18, 0, 8, 14, 19, 14]. How many comparisons would you need to do in order to find the key 18?
 10
 You do not need to search the entire list, since it is ordered you can stop searching when you have compared with a value larger than the key.
 5
 Since 11 is less than the key value 13 you need to keep searching.
 7
 Since 14 is greater than the key value 13 you can stop.
 6
 Because 12 is less than the key value 13 you need to keep going.
Q1: Suppose you are doing a linear search of the ordered list [3, 5, 6, 8, 11, 12, 14, 15, 17, 18]. How many comparisons would you need to do in order to find the key 13?
 11, 5, 6, 8
 Binary search starts at the midpoint and halves the list each time.
 12, 6, 11, 8
 In our implementation, the midpoint is found by integer division, which rounds down.
 3, 5, 6, 8
 Binary search does not start at the beginning and search sequentially, its starts in the middle and halves the list after each compare.
 18, 12, 6, 8
 It appears that you are starting from the end and halving the list each time.
Q1: Suppose you have the following sorted list [3, 5, 6, 8, 11, 12, 14, 15, 17, 18] and are using the recursive binary search algorithm. Which group of numbers correctly shows the sequence of comparisons used to find the key 8.
 12, 17, 15
 Remember our implementation will round down to find the midpoint of the list.
 18, 17, 15
 Remember binary search starts in the middle and halves the list.
 14, 17, 15
 Looks like you might be off by one, be careful that you are calculating the midpoint using integer arithmetic.
 11, 15, 17
 Binary search starts at the midpoint and halves the list each time.
Q1: Suppose you have the following sorted list [3, 5, 6, 8, 11, 12, 14, 15, 17, 18] and are using the recursive binary search algorithm. Which group of numbers correctly shows the sequence of comparisons used to search for the key 16?
 O(2n)
 No, 3n^{2} dominates 2n. Try again.
 O(n)
 No, n^{2} dominates n. Try again.
 O(3n^{2})
 No, the 3 should be omitted because n^{2} dominates.
 O(n^{2})
 Right!
 More than one of the above
 No, only one of them is correct. Try again.
Q1: If the exact number of steps is \(T(n)=2n+3n^{2}1\) what is the Big O?
 the space it takes
 This can be dependent of the programming language
 the time it takes
 This can be dependent on the machine, programming language, and other factors
 the number of steps
 Yes, when quantifying the time it takes to execute an algorithm we base it on the number of steps it takes to solve the problem, not the time it takes
 the readability of the code
 No, a very efficient algorithm can be programmed efficiently in C++ without any extra spaces making it unreadable, however the solution would still be efficient.
Q1: When considering the Big O of an algorithm, what do we use to quantify our description of an algorithm.
Q1: The Big O of a particular algorithm is \(O(n^{2})\). Given that it takes 2 seconds to complete the algorithm with 1 million inputs:
How long would it take with 2 million inputs? seconds.
How long would it take with 10 million inputs? seconds.
 \(O(1)\)
 \(O(\log n)\)
 \(O(n)\)
 \(O(n\log n)\)
 \(O(n^2)\)
Q1: What is the complexity of selection sort?
 [16, 49, 39, 27, 43, 34, 46, 40]
 This is the second half of the list.
 [21,1]
 Yes, mergesort will continue to recursively move toward the beginning of the list until it hits a base case.
 [21, 1, 26, 45]
 Remember mergesort doesn't work on the right half of the list until the left half is completely sorted.
 [21]
 This is the list after 4 recursive calls
Q1: Given the following list of numbers: [21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40], which answer illustrates the list to be sorted after 3 recursive calls to merge sort?
 [21, 1] and [26, 45]
 The first two lists merged will be base case lists, we have not yet reached a base case.
 [1, 2, 9, 21, 26, 28, 29, 45] and [16, 27, 34, 39, 40, 43, 46, 49]
 These will be the last two lists merged
 [21] and [1]
 The lists [21] and [1] are the first two base cases encountered by mergesort and will therefore be the first two lists merged.
 [9] and [16]
 Although 9 and 16 are next to each other they are in different halves of the list starting with the first split.
Q1: Given the following list of numbers: [21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40], which answer illustrates the first two lists to be merged when using merge sort on this list?
 3
 5
 8
 14
 Other
Q1: Suppose you have the following sorted list:
[3, 5, 6, 8, 11, 12, 14]
You will use the recursive binary search algorithm to search for the number 4. Which number in the sorted list would be accessed first?
 3
 5
 8
 12
 Other
Q1: Suppose you have the following sorted list:
[3, 5, 6, 8, 11, 12, 14]
You will use the recursive binary search algorithm to search for the number 4. Which number in the sorted list would be accessed second?