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)
The data structure needed to store the line segments int the sweep line algorithm to find intersecting line segments is a ________
Balanced Search Tree
What is the runtime for Jarvis March?
O(n * h)
Typical dynamic programming solutions involve table storage and a recursive mathematical formula?
True
The knapsack problem we solved using dynamic programming allows the individual items to be divided into smaller pieces?
False
Longest common subsequence of abbcba and cbabca
bbca or abca
The O(n lg n) algorithm to find the closest pair of points as discussed in class uses:
all of the above (divide and conquer paradigm, sorting by both x and y coordinates)
If 0-1 knapsack problem has n items and a knapsack capacity of C, the number of entries in the table computer by the dynamic programming algorithm is:
n * C
