Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Graduate Algorithms > Exam 1 - Divide and Conquer > Flashcards

Exam 1 - Divide and Conquer Flashcards

1
Q

Is pseudocode allowed in the D&C written questions?

A

No

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

In the D&C written questions, each recurrence should be a ____ problem than before

A

Smaller

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

In the D&C written questions, each solution must be more efficient than ____

A

The brute force solution

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

In the D&C written questions, what are the three sections expected?

A

Algorithm Description
Correctness Justification
Runtime Analysis

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

In the D&C written questions, what is expected in the Algorithm Description section?

A

How to solve the problem

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

In the D&C written questions, what is expected in the Justification of Correctness section?

A

Why the algorithm solves the problem

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

In the D&C written questions, what is expected in the Runtime Analysis section?

A

The big-O runtime of the algorithm, including the big-O runtimes for all nontrivial steps of the algorithm

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

In the D&C written questions, can the master theorem be used for the runtime analysis?

A

Yes

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

What is the input for FastMultiply?

A

Two n-bit integers x and y, where n is some power of two

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

What is the output of FastMultiply?

A

x times y

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

FastMultiply starts by splitting x and y into what components?

A

X_l, Y_l, X_r, Y_r

They are the left and right n/2 bits of x and y

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

After FastMultiply splits X and Y into left and right halves, how does it calculate the three subproblems?

A

A is FastMultiply(X_l,Y_l)
B is FastMultiply(X_r,Y_r)
C is FastMultiply(X_l+X_r,Y_l+Y_r)

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

After FastMultiply calculates A, B, and C, how does it use those values to calculate the output value?

A

2^n * A +
2^(n/2) * (C - A - B)
+ B

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

What’s the input formula for the master theorem?

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

What are the input constraints of the master theorem?

A

a > 0, b > 1, d >= 0

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

What is the result of the master theorem if d > log (b, a)

A

O(n^d)

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

What is the result of the master theorem if d = log (b, a)

A

O(n^d log n)

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

What is the result of the master theorem if d < log (b, a)

A

O(n^(log(b,a)))

19
Q

What is the recurrence for the runtime of fastmultiply?

A

T(n) = 3T(n/2) + O(n)

20
Q

What does the master theorem tell us the big-O of fastmultiply is, given that its recurrence is T(n) = 3T(n/2) + O(n)

A

O(n^(log(2,3)))

21
Q

What is the input of mergesort?

A

An array of numbers a[1…n]

22
Q

What does mergesort return if the input array has size 1?

A

The input array, unmodified

23
Q

What does mergesort return if the input array has size > 1

24
Q

In mergesort, what does the merge subroutine do if either if the inputs is empty?

A

It returns the other input

25
In mergesort, the merge subroutine is given two arrays, x[1...k] and y[1...l]. What does it do if x[1] is <= y[1]?
26
In mergesort, the merge subroutine is given two arrays, x[1...k] and y[1...l]. What does it do if x[1] is NOT <= y[1]?
27
What is the recurrence of the runtime for mergesort?
T(n) = 2T(n/2) + O(n)
28
What is the runtime for mergesort, given that the recurrence is T(n) = 2T(n/2) + O(n) ?
O(n log n)
29
What is FastSelect for?
Finding the kth smallest element in an unsorted list of numbers
30
What are the inputs to FastSelect?
A, an unsorted list of numbers of size n k, an integer 1 <= k <= n
31
What is the first step of FastSelect?
Break A into n/5 groups, G1, G2, ... G(n/5)
32
After splitting A into the n/5 G groups, what does FastSelect do next?
For i from 1 to n/5, sort Gi and let m_i be the median of Gi
33
After calculating the Gi medians, what does FastSelect do?
Creates set S which includes all of the medians of the G groups S = {m_1, m_2, ..., m_(n/5)}
34
After creating set S, what does FastSelect do?
It finds the pivot value p by recursing on S p = FastSelect(S, n/10)
35
After calculating the pivot value p, what does FastSelect do?
It partitions A into Ap
36
After partitioning A based on pivot p, what does FastSelect do if k <= |A
It recurses on the A

37
After partitioning A based on pivot p, what does FastSelect do if k > |A
It recurses on the A>p set return FastSelect(A>p, k-|A
38
After partitioning A based on pivot p, what does FastSelect do if k is not <= |A |A
it returns p
39
What is the runtime of the step of FastSelect where it breaks A into n/5 groups of 5 elements each?
O(n)
40
What is the runtime of the step of FastSelect where it sorts the G groups, calculates their medians, and creates set S?
O(1) per group, which results in O(n)
41
What is the recurrence of the step of FastSelect where it calculates pivot p based on the set of medians S?
T(n/5)
42
What is the recurrence of the step of FastSelect where it recurses on one of the partitioned sections of A?
T((3/4)n)
43
Why do we know that FastSelect finds a good pivot p value?

Graduate Algorithms (6 decks)

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