Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithms Final > Final > Flashcards

Final Flashcards

1
Q

What’s the best evidence that computer scientists have that P does not equal NP?

A

All NP-Complete problems can be solved if you solve one of them, but not even one of them has been solved

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

(T/F) If a problem is NP it must be intractable

A

F, A problem isn’t necessarily intractable in NP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

NP

A

Set of all decision problems where you can check if a solution is correct in polynomial time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

P

A

Set of all decision problems where you can find a solution in polynomial time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

(T/F) log n = O(sqrt(n))

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

(T/F) A breadth-first search algorithm uses a stack

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

(T/F) A graph G = (V, E) is said to be dense if |E| is O(|V|^2)

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

(T/F) The worst-case asymptotic complexity of Dijkstra’s algorithm in a dense graph is O(|V|^2)

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

(T/F) If an undirected graph G = (V,E) has the same weight for every edge, then both the single-source shortest path problem and the minimal spanning tree problem for the graph can be solved in linear time.

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

(T/F) The shortest path between two vertices in a minimum spanning tree is always a shortest path between the two vertices in the full graph

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

(T/F) The greedy algorithm for the fractional knapsack problem takes a fractional amount of at most one item

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

(T/F) Like Dijkstra’s algorithm, Prim’s algorithm does not work correctly unless all edge weights are non-negative

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

(T/F) All dynamic programming algorithms have the same asymptotic complexity.

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

(T/F) If a depth-first traversal of a directed graph G yields no back edges,then the graph G is cyclic.

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

(T/F) Any problem that is in the complexity class P is also in thecomplexity class NP, even if P ≠ NP.

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

(T/F) The Boolean satisfiability problem can be solved by a deterministicpolynomial-time algorithm if and only if P = NP

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

(T/F) If a problem is NP-hard, it is also NP-complete

A

F

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

For a recurrence relation of the form T(n) = aT(n/b) + n d , the Master Theorem says that T(n) is bounded asymptotically as follows:

T(n) = | O(n^(d) logn if a = b^d

| O(n^d) if a < b^d

Consider the following recurrence:

T(n) = | 16T(n/4) + 5n^2 n>k

| theta(1) n <= k

where k is a small integer. Indicate which case of the Master theorem applies(first, second, or third), and solve the recurrence

O(n^logb(a)) if a>b^d

A

second, O(n^(2) logn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

For a recurrence relation of the form T(n) = aT(n/b) + n d , the Master Theorem says that T(n) is bounded asymptotically as follows:

T(n) = | O(n^(d) logn if a = b^d

| O(n^d) if a < b^d

Suppose that we have a divide-and-conquer algorithm for solving acomputational problem that for an input of size n, divides the problem intotwo independent subproblems of input size 2n/5 each, solves the twosubproblems recursively, and combines the solutions to the subproblems.Suppose that the time for dividing and combining is O(n). Give a recurrencerelation for the running time of this algorithm and then solve the recurrence

O(n^logb(a)) if a>b^d

A

third, O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

The binary heap data structure is very useful in implementing an efficient priorityqueue. The two key operations of a priority queue are (i) insertion of a new element,and (ii) removal of the element with the minimum (or maximum) value

When a priority queue is implemented using a binary heap data structure,what is the complexity of each of these operations?

A

insertion: O(log n)

removal: O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

The binary heap data structure is very useful in implementing an efficient priorityqueue. The two key operations of a priority queue are (i) insertion of a new element,and (ii) removal of the element with the minimum (or maximum) value

When a priority queue is implemented as a simple unordered array, whatis the complexity of these same two operations?

A

insertion: O(1)

removal: O(n)

22
Q

Name three algorithms we have studied this semester that use a priority queue.

A

Heapsort, Dijkstras, Prims

23
Q

Name three decrease-and-conquer algorithms we have studied this semester.

A

Euclid, Binary search, Bisection, Square root, Interpolation search

24
Q

Name three divide-and-conquer (but not decrease-and-conquer) algorithms we have studied this semester

A

Strassen, Merge sort, Quick sort, Karatsubas

25
Q

Name three greedy algorithms we have studied this semester, all of which are guaranteed to find an optimal solution.

A

Prims, Kruskals, Huffman, Fractional knapsack

26
Q

Name three dynamic programming algorithms we have studied this semester

A

Fibonacci, LCS-Length, Edit Distance, Bellman Ford, 0-1 Knapsack

27
Q

What is a key similarity between divide-and-conquer and dynamic programming algorithms, and what is a key difference?

A

They both split problems into smaller subproblems. In divide and conquer algorithms the subproblems are independent, in dynamic they are not independent

28
Q

Christina is taking a computer science algorithms exam. She notices that the professorhas assigned points to each problem according to the professor’s opinion of thedifficulty of the problem. Unfortunately, Christina’s studying was a bit spotty so heropinion of the difficulty of each problem differs quite a bit from the professor’s.However, Christina does understand greedy algorithms so she decides to apply agreedy algorithm to her test taking. For each problem, she estimates how much time itwill take her to complete the problem. Her goal is to maximize the points she willreceive given that {p 1 ,p2 ,…,pn } are the number of points assigned by the professor toeach of the n problems, {t1 , t2 , …, tn } are Christina’s estimates of the time required todo each problem, and T is the total time available for taking the exam. If Christina hasnot finished a problem when the time for taking the exam runs out, she receivespartial credit for the work she has done on that problem.

Is there a greedy algorithm for deciding which questions to answer that Christina canuse to maximize her grade? If so, what is the greedy algorithm? What is the mostclosely-related problem we have studied this semester for which a similar greedyalgorithm could be used?

A

She can use an algorithm that solves the fractional knapsack. The most closely related problem is fractional knapsack

29
Q

Briefly, what is the relationship between the worst-case complexity of Prim’s algorithm and the worst-case complexity of Dijkstra’s algorithm

A

They are the same.

O(v^2) for array, dense

O(VlogV) for binary heap, sparse

30
Q

Find the longest common subsequence of the strings AWFUL and WAFFLE. Show the dynamic programming table that you use to find the solution. Include arrows to show how you extract the solution from the table. Recall that the optimal substructure of the longest common subsequence problem gives the recursive formula

c[i,j]=| c[i-1, j-1] + 1 if i,j > 0 and xi=yj

| max(c[i, j-1], c[i-1, j]) if i,j > 0 and xi not equal yj

What is the longest common subsequence?

0 if i=0 or j=0

A

WFL

31
Q

empty

A

empty

32
Q

Recall that the Bellman-Ford algorithm solves the single-source shortest pathproblem in a weighted graph where some edge weights may be negative.Consider the following code for the Bellman-Ford algorithm, where G = (V,E) isa graph, w is the set of edge weights, where w(u,v) denotes the weight of an edgefrom vertex u to vertex v, and s is the source vertex.

Initialize-Single-Source (G,s)

  1. for each vertex v E G
  2. do d[v] <- inf
  3. π[v] <- NIL
  4. d[s] <- 0

Relax (u,v,w)

  1. if d[v] > d[u] + w(u,v)
  2. then d[v] <- d[u] + w(u,v)
  3. π[v] <- u

Bellman-Ford (G, w, s)

  1. Initialize-Single-Source(G,w,s)
  2. for i <- 1 to |V[G]| - 1
  3. do for each edge (u, v) E E[G]
  4. do Relax(u,v,w)
  5. for each edge (u, v) E E[G]
  6. do if d[v] > d[u] + w(u, v)
  7. then return false
  8. return true

What is the asymptotic complexity of the Bellman-Ford algorithm as a function of the size of the graph G = (V,E)? Is the algorithm more efficient in a sparse graph than a dense graph?

A

O(VE), yes

33
Q

Recall that the Bellman-Ford algorithm solves the single-source shortest path problem in a weighted graph where some edge weights may be negative. Consider the following code for the Bellman-Ford algorithm, where G = (V,E) isa graph, w is the set of edge weights, where w(u,v) denotes the weight of an edge from vertex u to vertex v, and s is the source vertex.

Initialize-Single-Source (G,s)

  1. for each vertex v E G
  2. do d[v] <- inf
  3. π[v] <- NIL
  4. d[s] <- 0

Relax (u,v,w)

  1. if d[v] > d[u] + w(u,v)
  2. then d[v] <- d[u] + w(u,v)
  3. π[v] <- u

Bellman-Ford (G, w, s)

  1. Initialize-Single-Source(G,w,s)
  2. for i <- 1 to |V[G]| - 1
  3. do for each edge (u, v) E E[G]
  4. do Relax(u,v,w)
  5. for each edge (u, v) E E[G]
  6. do if d[v] > d[u] + w(u, v)
  7. then return false
  8. return true

What is the purpose of lines 5 through 7 of the algorithm?

A

Finding any negative weight cycles

34
Q

For each of the following problems, give the name of the most efficient algorithmwe’ve studied this semester for solving the problem and indicate its average-casecomplexity.

Comparison-based sorting of an array of n integers.

A

merge sort, quick sort, heap sort O(nlogn)

35
Q

Sorting a large array of 12-digit numbers.

A

Radix sort O(n)

36
Q

Sorting an array a numbers where the numbers are uniformly distributedover a range. (For this algorithm, give both its average-case and worst-case complexity.)

A

Distribution (Bucket)

37
Q

The selection problem (i.e., find the kth element in an unordered array)

A

Quick select O(n)

38
Q

Finding the strongly-connected components of a directed graph

A

Kosorajus O(V+E)

39
Q

Single-source shortest-path problem in an unweighted graph

A

BFS O(V+E)

40
Q

Single-source shortest-path problem in a sparse graph with non-negative edge weights

A

Dijkstras O(ElogV)

41
Q

Single-source shortest-path problem in a graph with negative weights but no negative-weight cycles

A

BF O(VE)

42
Q

Minimal spanning tree problem for a sparse undirected graph

A

Prims O(E log V)

43
Q

Searching for an element in a sorted array

A

Interpolation search O(log(log n))

44
Q

If you have a set of n items how many subsets are there?

A

2^n

45
Q

If you have a set of n items, how many permutations are there?

A

n!

46
Q

Decision problem

A

computational problem with output of “yes” or “no”, 1 or 0.

47
Q

Optimization problem

A

computational problem where we try to maximize or minimize some value

48
Q

What does it mean to say that a problem is in the complexity class P?

A

Find a solution in polynomial using deterministic computer

49
Q

What does it mean to say that a problem is in the complexity class NP?

A

Find a solution in polynomial using a non deterministic computer and verify solution using deterministic computer

50
Q

What does it mean to say that a problem is NP-complete? Give the names of at least five problems that are NP-complete, and describe one of these problems in detail

A

Hardest problems in class NP. If anyone of these is solved in polynomial then all of them can be solved in polynomial

0-1 knapsack. Graph coloring. Boolean satisfiability. Subset sum. Travelling salesman. Hamiltonian circuit. K click

51
Q

The most famous open problem in all of theoretical computer science is the question of whether P = NP. Why do most computer scientists believe that these classes are not the same, that is, that there are problems in the class NP that are not in the class P? What evidence do they have for this belief?

A

If one NP-Complete problem is solved then all of them would be solved. People have been trying to solve NP problems for decades and not even one has been solved

Algorithms Final (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions