CS 6515 Final Review Questions and Correct Answers the Latest Update
0 keer bekeken 0 keer verkocht
Vak
CS 6515
Instelling
CS 6515
D&C Steps
1. Figure out your Black Box if needed.
○ Sorted = Binary Search (usually)
○ Unsorted = Merge sort (usually)
○ Polynomials, convolution, multiplication = FFT(usually)
2. State the Modification if needed. You may use the blackbox as is.
○ Which part of the black box you...
CS 6515 Final Review Questions and
Correct Answers the Latest Update
D&C Steps
✓ 1. Figure out your Black Box if needed.
✓ ○ Sorted = Binary Search (usually)
✓ ○ Unsorted = Merge sort (usually)
✓ ○ Polynomials, convolution, multiplication = FFT(usually)
✓ 2. State the Modification if needed. You may use the blackbox as is.
✓ ○ Which part of the black box you are changing.
✓ ○ What are your inputs and outputs to the black box.
✓ 3. State the steps of your algorithm.
✓ ○ NO PSEUDOCODE - use words
✓ ○ Must include base case(s) if needed.
✓ ○ Always return what the problem asks for.
✓ 4. Prove Correctness
✓ ○ Proof in words of why this algorithm solves the problem.
✓ ○ Prove the base case
✓ ○ The decision to select left or right in a Binary Search.
✓ ○ Prove that the problem gets smaller.
✓ 5. Analyze the runtime.
✓ ○ Can explain in words.
✓ ○ Can use black box runtime. Must include modifications' run time.
✓ ○ Can use Master Theorem.
DP Steps
✓ Steps:
✓ 1. Find the subproblem.
✓ ○ State your ranges (not required)
✓ ■ For 1 ≤ i ≤ n
✓ ○ Define the subproblem in words.
✓ ○ Define the problem on ith item.
✓ ■ T(i) or T(i, j) is ...
✓ ○ Possibly add a constraint such as include last element
✓ ■ T(i) is ... that includes x[i].
✓ ○ Might be different than what the overall question asks.
✓ ○ For example, a True/False final answer can usually be set up with Min/Max first
and then checked at the end.
✓ ■ T(i) or T(i, j) is the maximum ...
✓ 2. Find the recurrence.
✓ ○ Must include base case(s) if needed
✓ ■ T(0) = ...
✓ ○ State your ranges
✓ ■ For 1 ≤ i ≤ n
✓ ○ Define the current problem as a relationship of smaller subproblems.
✓ ■ T(i) in terms of T(i-1)
✓ ■ T(i, j) in terms T(i-1, j), T(i, j-1), and/orT(i-1, j-1)
✓ 3. Pseudocode for algorithm.
✓ ○ No real code allowed.
✓ ○ Must include base case(s) if needed.
✓ ○ Always return what the problem asks for.
✓ ○ May be a different return from the subproblem definition.
✓ 4. Analyze the runtime.
✓ ○ Can annotate code with each runtime and compute at the end.
✓ ○ Can explain in words.
✓ ○ Include all non trivial (arithmetic) lines
Master Theorem
✓ T(n) = aT(n/b) + O(n^d)
✓
✓ -T(n) is O(n^d) if d > logb(a)
Smart Grades Latest update
1
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper Examify. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €10,01. Je zit daarna nergens aan vast.
