Question: 1in a binary search tree the largest element must be...
1.In a Binary Search Tree, the largest element must
be a leaf
have no child.
be the root
have at most one child.
2.Consider the problem of finding the smallest element in an unsorted list. Select all little o bounds for the algorithm. Recall that little o means that the actual time is negligible compared to the function given.
o(n log n)
3.Algorithms which have complexity 2n are considered intractable. Which of the following problems likely have only intractable solutions?
a)Towers of Hanoi
b)Traveling Salesperson problem: Given a collection of cities on a map, a salesman must make a tour of the cities, visiting each once, and returning to the city from which he started in the shortest amount of mileage.
c)The input is a positive integer C and n objects whose sizes are positive integers s1, s2,..., sn. Among all subsets of objects with sum at most C, what is the largest subset sum?
d)Bin Packing: Suppose we have unlimited number of bins each of unit capacity and n objects with sizes s1, s2,..., sn where the sizes si(i = 1,..., n) are rational numbers in the range 0 < si <=1. Determine the smallest number of bins into which the objects can be packed and find an optimal packing.
4.In big O notation, we ignore constant factors. Why? Select all correct answers.
No one cares about improvements that are just constant factor difference.
It is difficult to account for every constant as we would have to know a lot about operator costs.
If we move to another machine, all the constants would change.
As n gets large, the constant becomes unimportant.