Mid-Term 2 Flashcards by Adam A

Q

In general what are the two properties we need to prove that our greedy algorithm is optimal?

A

We need to prove the two following properties: 1) Greedy-choice property 2) Optimal substructure property

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

How do you prove the Greedy-choice property?

A

We are trying to prove that there exists an optimal solution for P that contains the greed choice made in the algorithm.

Proof of greedy-choice property: Assume that there is an optimal solution V that doesn’t make the same choice as our greedy choice. Prove that it makes a worse choice

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

How do you prove the optimal sub-structure property?

A

Optimal sub-structure property means that if we were to remove any choice we made from the solution, the resulting set is the optimal solution for this new subproblem.

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

In general, how is a knapsack problem defined?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Fractional Knapsack:

What is the input?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Fractional Knapsack:

What is the definition of a feasible solution?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Fractional Knapsack:

What is the required output?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Spell out the greedy choice made by densist-first algorithm for fractional knapsack.

What is the case 1?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Spell out the greedy choice made by densist-first algorithm for fractional knapsack.

What is the case 2?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Provide the proof for case 1: s_max > k

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Provide the proof for case 2: s_max<= k

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

What is the goal of proving the optimal substructure property? What is the typical proof structure?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

State case 1 of the master theorem.

What does it mean?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

State case 2 of the master theorem.

What does it mean?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

State case 3 of the master theorem.

What does it mean?

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

What is the following for mergeSort

Divide

Conquer

Combine

A

Q

Write out how mergeSort would sort the following:

A

Q

What is the mergesort code?

A

Q

What is the formula for merge sort and what is the subsequent run time?

A

Q

What is the pseudo code to implement Densest-First for the frational knapsack problem?

A

Q

How do we analyse the running time of Densist-First fractional knapsack?

What is the run time?

A

Q

What is the brute force calculation of fractional knapsack?

A

Q

What is the brute force calculation of 0-1 knapsack?

A

The number of choice would be 2ⁿ possible solutions

We can always brute force an answer but the running time is Ω(2ⁿ) which is extremely slow

As an example, see below