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).

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(n²), 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 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

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

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 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.

In Algorithms lecture, we defined in-order traversal. Post-order traversal is defined as follows:

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.

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

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)

Algorithms & Time Complexity 2

More Quizzes