09 dont

What NOT to do: 

What NOT to do I will give a list of mistakes which I particularly hate marking& for which there is no excuse. If you do any of these thingsyou will get -20% on the question.

Think about Algorithms Abstractly: 

Think about Algorithms Abstractly Devastated by the midterm Change your thinking now. This course requires completely changing the way you think about algorithms. Though I keep warning people, they tend not to get it until they are

Types of Questions: 

Solve new algorithmic problems Requires flashs of insight. Philosophies of algorithmic thinking. Easy algorithmic problems, testing whether you get the correct structure of iterative & recursive programs. Get the structure correct, even if you can’t get the details of the algorithm correct. Tell me that you know what you need to do and where you get stuck Types of Questions

Types of Questions: 

In high school, I hated teachers who marked answers wrong if not done their way. Now I do the same. The method of thinking abstractly is important. 99% of other types of answers are wrong. Types of Questions

Types of Questions: 

Types of Questions . Did you learn the basics of the algorithms taught in class? Can you trace them? Did you do the homework? Did you read the solution set? Math: summing, recurrence relations,  & , running time

Slide6: 

Give the exact time complexity (running time). No one gave the correct answer! Do not measure running time using the value of the input. Size = log n = s. n = 2s. Time = 2n2 + 3n + 4 = 2·22s + 3·2s + 4.

Slide7: 

T(n) = T(n/ 4) + T(n-5) + 3. Not T(n) = 3 T(n/ 4) + T(n-5) + 3. Not Eg(n) = Eg(n/ 4) + Eg(n-5) + 3. Give the exact time complexity (running time).

Slide8: 

T(n) = T(n/ 4) + T(n-5) + n + 3. Not T(n) = T(n/ 4) + T(n-5) + T(n) + 3. Give the exact time complexity (running time).

Slide9: 

Which of the steps to develop an iterative algorithm did the student fail to do correctly?

Slide10: 

Fine: Describes input and output. If I = -5, s = 1-5 j = 0

Slide11: 

Variables need to be documented.

Slide13: 

Let s' and i‘ be values of s and i when at the top of the loop. Let s'' and i'‘ be values after going around again.

Slide14: 

LI  s' = j=1i' j. Code  s'' = s'+i' i'' = i'+1. Together: s'' = (j=1i' j) + i'. i' is added in twice. i'' should be added.

Slide18: 

Test: on typical value i = 3  s=1+2+3. on special values i = 1  s=1. i = 0  s=1.

Typical Loop Invariant: 

Typical Loop Invariant If the input consists of an array of objects Each iteration considers the next input item.

Typical Loop Invariant: 

Typical Loop Invariant If the input consists of an array of objects We have considered the ith input element.

Typical Loop Invariant: 

Typical Loop Invariant If the input consists of an array of objects We have considered input elements [1..i].

Typical Loop Invariant: 

Typical Loop Invariant If the input consists of an array of objects We have a solution for the prefix consisting of elements [1..i]. plus some additional information

Typical Loop Invariant: 

Typical Loop Invariant If the output consists of an array of objects

Slide24: 

For all major algorithms covered. Learn pre and post conditions. Learn the Loop Invariant Learn how to make progress while maintaining the LI.

Slide25: 

Trust your friends to solve subinstances. The subinstance given must be smaller and must be an instance to the same problem. Combine solution given by friend to construct your own solution for your instance. Focus on one step. Do not talk of their friends friends friends. Solve small instances on your own. I am obsessed with the Friends - Strong Induction View of Recursion.

Slide26: 

I am obsessed with the Friends - Strong Induction View of Recursion. For binary trees, make sure that your program works for

Slide27: 

Define pre & post conditions Typical Test Answer

Slide28: 

Typical Test Answer Call recursively on the correct types of input

Slide29: 

Typical Test Answer Call recursively

Slide30: 

Typical Test Answer Combine solutions given by friends to construct your own solution.

Slide31: 

Typical Test Answer Return things of the correct types. In every path through code

Slide32: 

Typical Test Answer Subinstances need to be smaller. “Size” is size of the tree

Slide33: 

Typical Test Answer Subinstances need to be smaller. When the instance sufficiently small solve on your own. This does not act as base case because k is not getting smaller

Slide34: 

Typical Test Answer Subinstances need to be smaller. When the instance sufficiently small solve on your own. Code does not check whether the tree is empty.

Slide35: 

Typical Test Answer Local variables (other than those holding and combining solutions) are not usually needed. Value of n? No global variables allowed!

Slide36: 

Typical Test Answer No global returns. Things returned by your friends do not get returned to your boss unless you do the returning. My friend finds and returns the answer. I drop his answer. And return nothing!

Slide37: 

Typical Test Answer Loops are rarely used in recursive programs. on the same input getting the same result each time! Returns the root?? Called n times

Slide38: 

Typical Test Answer Don’t expect your marker to be a compiler!

Slide39: 

Typical Test Answer Traverse nodes in in-order. Count the nodes. Output the kth one. Reasonable Sounding Alg This is an iterative alg not a recursive alg. Fine (though asked for recursive)

Slide40: 

Greedy Algorithms Don’ts

Slide41: 

Greedy Algorithms Don’ts What the algorithm has done so far is optimal. What does this mean? The “More of the Input” loop invariant does not work.

Slide42: 

Greedy Algorithms Don’ts “There exists an opt solution consistent with choices made so far.”

Slide43: 

Greedy Algorithms Don’ts Don't say "it" without saying what "it" is. The loop invariant of any greedy algorithm is “There exists an opt solution consistent with choices made so far.” How we prove that this loop invariant is maintained?

Slide44: 

Greedy Algorithms Don’ts We tell the fairy god mother to change her solution optSLI into optSours. We must prove optSours is consistent, optimal, and valid. The loop invariant of any greedy algorithm is “There exists an opt solution consistent with choices made so far.” How we prove that this loop invariant is maintained?

Slide45: 

Greedy Algorithms Don’ts

Slide46: 

Greedy Algorithms Don’ts By the LI, optSLI is consistent with what the algorithm did in the first i steps. The Prover instructs the Fairy Godmother to change it to optSours to make it consistent with the i+1st step without missing up the earlier commitments.

Slide47: 

Greedy Algorithms Don’ts

Slide48: 

Greedy Algorithms Don’ts By the LI, optSLI is valid (ie does not contain conflicts within it.) The Prover instructs the Fairy Godmother to change it to optSours in a way that provably does not introduce conflicts.

Slide49: 

Greedy Algorithms Don’ts

Slide50: 

Greedy Algorithms Don’ts By the LI, optSLI is optimal (ie there is not a valid solution worth more.) The Prover instructs the Fairy Godmother to change it to optSours in a way that provably does not decrease its worth. Good

Optimization Problems: 

Optimization Problems Don’t mix up the following What is an instance What are the objects in an instance What is a solution What are the objects in a solution What is the cost of a solution Greedy algorithm What does the algorithm do & know What does the prover do & know What does the fairy god mother do & know Recursive Backtracking / Dynamic Programming What does the algorithm do & know What does the little bird do & know What does the friend do & know

Dynamic Programmingdon’ts : 

Dynamic Programming don’ts Yes, the code has a basic structure that you should learn. But don’t copy other code verbatim Don’t say if(ai = bj) (i.e. Longest Common Subsequence) when our problem has not bj

Dynamic Programmingdon’ts : 

Dynamic Programming don’ts When looping over the subinstances be clear what the set of subinstances are which is currently being solved, i.e. which instance is cost(i,j)? If you know that the set of subinstances are the prefixes of the input, i.e. <a1,a2, …, ai>, then don’t have a two dimensional table. Table[1..n,1..n]. Don’t loop over i and loop over j if j never gets mentioned again.

Dynamic Programmingdon’ts : 

Dynamic Programming don’ts .When trying all bird answers be clear what the set of bird answers are, which is currently being tried, & what it says about the solution being looked for. When getting help from your friend, be clear what the subinstance is that you are giving him How do you use the current instance and the birds answer to form his subinstance. Don’t simply say cost(i-1,j-1)

Dynamic Programmingdon’ts : 

Dynamic Programming don’ts .Think about what the base cases should be. Don’t make an instances a base cases if they can be solved using the general method. % is used to start a comment. Don’t put it in front of code.

End: 

End