Algorithms & Time Complexity 2
Complete this homework assignment by Tuesday, August 2 at 7pm. You can use any resources you want, but we highly recommend not relying heavily on Google (you'll learn more this way).
Complete this homework assignment by Tuesday, August 2 at 7pm. You can use any resources you want, but we highly recommend not relying heavily on Google (you'll learn more this way).
Assume that arr is an array of integers, and #bubble_sort is a standard implementation of the bubble sort method. What is the space complexity of the following function?
def best_sort(arr)
unsorted = []
arr.each do |el|
unsorted << el
end
all_of_it = []
arr.bubble_sort.each_with_index do |el, idx|
all_of_it << [idx, el, unsorted[idx]]
end
all_of_it
end
O(n), where n is the size of the array.
O(n log n), where n is the size of the array.
O(1).
O(n2), where n is the size of the array.
Assume that arr is an array of integers, and that #merge_sort, #quick_sort, and #bubble_sort are standard implementations of their respective sorts. The methods #merge_sort and #quick_sort do not mutate the original array, but #bubble_sort does. Tail recursion is used in the implementation of #quick_sort. What is the space complexity of the following fun
def all_sorts(arr)
one_sort = arr.merge_sort
two_sort = arr.quick_sort
arr.bubble_sort.each_with_index do |el, idx|
return false unless one_sort[idx] == two_sort[idx] && el == one_sort[idx]
end
true
end
O(n) where n is the size of the array.
O(n log n) where n is the size of the array.
O(1).
O(log n) where n is the size of the array.
You have an app that 100,000 companies use. Users need to be able to see a list of all 100,000 companies, and they need to be able to sort the list by company name and company size. Here's the schema for the company table:
| id | integer |
| ceo_id | integer |
| name | string |
| num_employees | integer |
| industry | string |
| job_openings | boolean |
| logo_url | string |
You have an app that 100,000 companies use. Users need to be able to see a list of all 100,000 companies, and they need to be able to sort the list by company name and company size. Here's the schema for the company table:
| id | integer |
| ceo_id | integer |
| name | string |
| num_employees | integer |
| industry | string |
| job_openings | boolean |
| logo_url | string |
A. Based on the given information, which of the columns in the company table should be indexed?
All of them.
Only id, num_employees and name.
Everything except job_openings.
The id, ceo_id, the num_employees, and the name.
B. You initially use awesomesort in your app to sort the list of companies. Awesomesort is a comparison sort that runs as quickly as it is possible for any comparison sort to run. Assuming that your app takes 1.38 milliseconds to sort 100 companies on Captain Picard's computer, about how long will it take to sort all 100,000 companies? (Hint: use math. What's the constant factor?)
1380 milliseconds.
3.45 milliseconds.
27.6 milliseconds.
2.07 milliseconds.
C. Although Captain Picard's computer is modern and sleek, Lieutenant Uhura's is not. She complains to you that your sort is running very slowly. After some investigation, you discover that Lieutenant Uhura does not have a cache on her computer. What could be going on, and what's the best fix?
Awesomesort is an implementation of heapsort. Replace it with an in-place implementation of quicksort.
Awesomesort is an implementation of radix sort. Replace it with an implementation of quicksort.
Awesomesort is an implementation of heapsort. Replace it with either quicksort or mergesort -- they use the same amount of space.
Awesomesort is an implementation of mergesort. Replace it with an implementation of quicksort, or better yet, an implementation of radix sort.
Consider the following binary search tree:
Which tree results when 7 is inserted into the tree?0%
0
0%
0
0%
0
0%
0
Consider the following binary search tree:
Which two trees are the possible results of deleting the root node of this tree, using Hibbard deletion?
NB: Hibbard deletion is the deletion method we discussed in lecture.
0%
0
0%
0
0%
0
0%
0
In Algorithms lecture, we defined in-order traversal. Post-order traversal is defined as follows:
Beginning at the root node, do the following.
Beginning at the root node, do the following.
Step 1: perform a post-order traversal of the left subtree.
Step 2: perform a post-order traversal of the right subtree.
Step 3: print the value of the root node.
In Algorithms lecture, we defined in-order traversal. Post-order traversal is defined as follows:
Beginning at the root node, do the following.
Beginning at the root node, do the following.
Step 1: perform a post-order traversal of the left subtree.
Step 2: perform a post-order traversal of the right subtree.
Step 3: print the value of the root node.
Consider the following binary search tree.
In what order are the nodes printed when a post-order traversal is performed on this tree?
0, 4, 6, 5, 7, 1, 9, 10, 12, 11, 20, 13, 8
0, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 20
20, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 1, 0
0, 1, 7, 6, 5, 4, 11, 9, 10, 20, 12, 13, 8
Bonus: for an arbitrary binary search tree, what is the last node that will be explored in that tree? (Hint: it's very easy to describe this node.)
A. Which of the following is the min-heap that results from inserting the data set [1, 2, 3, 4, 5] from left to right?
0%
0
0%
0
0%
0
0%
0
B. Which heap results when deleteMin() is called on the heap from part (a)?
0%
0
0%
0
0%
0
0%
0
A. Which of the following is the max-heap that results from inserting the data set [1, 2, 3, 4, 5] from left to right?
0%
0
0%
0
0%
0
0%
0
B. Which heap results when deleteMax() is called on the heap from part (a)?
0%
0
0%
0
0%
0
0%
0
A. Which of the following is the min-heap that results from inserting the data set [3, 5, 2, 8, 1, 5, 2] from left to right?
0%
0
0%
0
0%
0
0%
0
Suppose deleteMin() is called on the heap from part (a). Which array represents the resulting heap?
[2, 3, 2, 8, 5, 5]
[2, 2, 3, 8, 5, 5]
[2, 2, 3, 5, 5, 8]
[2, 3, 5, 2, 8, 5]
Which table represents the time complexity of a resizing HashMap's core functionality?
| Worst Case | Amortized Time | |
| #find | O(N) | O(1) |
| #insert | O(N) | O(1) |
| #delete | O(N) | O(1) |
| Worst Case | Amortized Time | ||
| #find | O(N log N) | O(N) | |
| #insert | O(N log N) | O(N) | |
| #delete | O(N log N) | O(N) |
| Worst Case | Amortized Time | ||
| #find | O(N) | O(log N) | |
| #insert | O(N) | O(log N) | |
| #delete | O(N log N) | O(log N) |
| Worst Case | Amortized Time | ||
| #find | #find | O(N) | |
| #insert | #insert | O(N) | |
| #delete | #delete | O(N) |
Which table represents the time complexity of a fixed size HashMap's core functionality?
| Worst Case | Amortized Time | |
| #find | O(N) | O(N) |
| #insert | O(N) | O(N) |
| #delete | O(N) | O(N) |
| . | Worst Case | Amortized Time |
| #find | O(N) | O(1) |
| #insert | O(N) | O(1) |
| #delete | O(N) | O(1) |
| . | Worst Case | Amortized Time |
| #find | O(N) | O(1) |
| #insert | O(N) | O(N) |
| #delete | O(N) | O(N) |
| Worst Case | Amortized Time | |
| #find | O(log N) | O(1) |
| #insert | O(N) | O(log N) |
| #delete | O(N) | O(log N) |
{"name":"Algorithms & Time Complexity 2", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Assume that arr is an array of integers, and #bubble_sort is a standard implementation of the bubble sort method. What is the space complexity of the following function? def best_sort(arr) unsorted = [] arr.each do |el| unsorted << el end all_of_it = [] arr.bubble_sort.each_with_index do |el, idx| all_of_it << [idx, el, unsorted[idx]] end all_of_it end, Assume that arr is an array of integers, and that #merge_sort, #quick_sort, and #bubble_sort are standard implementations of their respective sorts. The methods #merge_sort and #quick_sort do not mutate the original array, but #bubble_sort does. Tail recursion is used in the implementations of #merge_sort and #quick_sort. What is the space complexity of the following function? def all_sorts(arr) one_sort = arr.merge_sort two_sort = arr.quick_sort arr.bubble_sort.each_with_index do |el, idx| return false unless one_sort[idx] == two_sort[idx] && el == one_sort[idx] end true end, You have an app that 100,000 companies use. Users need to be able to see a list of all 100,000 companies, and they need to be able to sort the list by company name and company size. Here's the schema for the company table: id integer ceo_id integer name string num_employees integer industry string job_openings boolean logo_url string","img":"https://www.quiz-maker.com/3012/images/ogquiz.png"}