Exam 1 Cards Flashcards
The convex hull lower bound references the_________ lower bound
sorting
If you walk around the vertices of a convex hull in a counter clockwise direction, at the vertices you make________turns
only left turns
The greedy strategy for giving back change using the minimum number of coins is to repeatedly give back the highest coin denomination that is less than or equal to the amount of change. Give back 42c, how many coins are given as change?
4
Which of these algorithms is not a good example of a divide and conquer approach?
sweep line algorithm to find if any line segments intersect
If we add 13c coin to the US coins list, waht is the smallest amount of change that can be given back where the greedy strategy fails with the 13c coin added?
15
The time to find a convex hull using the Graham Scan algorithm if the points are given in increasing order of polar angle with respect to the lowest point is________
O(n)
When solving the 0/1 knapsack problem, what do the indexes of each axis of the table represent?
The upper index in the list of items that can be considered and the capacity of the knapsack
“dog” is a subsequence of “dcoagt”
true
What is the solution to the recurrence T(n) = 4 T(n/4) + 2 T(n/2) + n?
O(n^2)
What is the solution to the recurrence T(n) = 2 T (N/4) + 2N^0.5 ?
O(N^0.5 lg N)
When the sweep line algorithm reaches a right point, what actions does it take? Assume the point is p and the line it is on is L. Select all that apply.
Remove the line from the tree and Checks to see if there exists a line above or below L, if there are, check if the intersect
Given a set of n points in counter-clockwise order, the running time to verify that the set of points form a convex polygon is______
O(n)
Cross product operations can be used to determine if two line segments intersect
True
The following recurrence fits the form for the master theorem: T(n) = 2T(n/4) + T(n/5) + O(n^2)
false
What is the solution to the following recurrence? T(n) = 4T(n/3) + n
O(n^log3 4)
