Stack of Stack Frames
What NOT to do
I get sooooo
Frustrated!
Marking the SAME
wrong answer hundreds of times!
I will give a list of mistakes
which I particularly hate marking
& for which there is no excuse.
If you do any of these things
you will get -20%
on the question.
‹#›
1
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
‹#›
2
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
‹#›
3
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
‹#›
4
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
‹#›
5
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.
‹#›
6
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).
‹#›
7
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).
‹#›
8
Typical Loop Invariant
If the input consists of an array of objects
Each iteration considers the next input item.
Loop Invariants are pictures
of current state.
Not actions
Not algorithms
‹#›
9
Typical Loop Invariant
If the input consists of an array of objects
We have considered the ith input element.
What about elements [1…i]?
‹#›
10
Typical Loop Invariant
If the input consists of an array of objects
We have considered input elements [1..i].
So?
‹#›
11
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
‹#›
12
Typical Loop Invariant
If the output consists of an array of objects
I have produced the first i objects.
‹#›
13
For all major algorithms covered. Learn pre and post conditions. Learn the Loop Invariant
Learn how to make progress
while maintaining the LI.
‹#›
14
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.
‹#›
15
I am obsessed with the Friends – Strong Induction View of Recursion.
For binary trees, make sure that your program works for
generic
generic
generic
‹#›
16
Define pre & post conditions
Don’t have inputs or outputs
that are not explained!
Typical Test Answer
‹#›
17
Typical Test Answer
Call recursively
on the correct types of input
k,num,v
‹#›
18
Typical Test Answer
Call recursively
Save the results
(or don’t bother calling)
returning the correct
types of output
‹#›
19
Typical Test Answer
Combine solutions
given by friends
to construct
your own solution.
‹#›
20
Typical Test Answer
Return things
of the correct types.
Not an
element
In every path
through code
the root?
‹#›
21
Typical Test Answer
Subinstances
need to be smaller.
“Size” is size of the tree
‹#›
22
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
‹#›
23
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.
‹#›
24
Typical Test Answer
Local variables (other than those holding and combining solutions) are not usually needed.
Value of n?
Local variables
don’t change outside
of the current stack frame.
n = 2
No global variables allowed!
‹#›
25
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!
‹#›
26
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
‹#›
27
Typical Test Answer
Don’t expect your marker
to be a compiler!
‹#›
28
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.
Hard to write a recursive program that implements an iterative algorithm.
Fine
(though asked for recursive)
‹#›
29
Greedy Algorithms Don’ts
What is the loop invariant of
any greedy algorithm?
We prove that the algorithm’s solution is …
The algorithm has made some commitments
already, but this does not yet constitute
a valid solution.
‹#›
30
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.
What is the loop invariant of
any greedy algorithm?
‹#›
31
Greedy Algorithms Don’ts
“There exists an opt solution consistent
with choices made so far.”
What is the loop invariant of
any greedy algorithm?
‹#›
32
Greedy Algorithms Don’ts
We prove it is consistent, optimal, and valid.
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?
‹#›
33
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.
Great, but what does this mean?
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?
‹#›
34
Greedy Algorithms Don’ts
The Prover is unable to see
the Fairy Godmother’s optimal solution.
The Prover compares the Fairy Godmother’s
optimal solution to what the algorithm
has done.
How do we prove optSours is consistent?
‹#›
35
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.
How do we prove optSours is consistent?
‹#›
36
Greedy Algorithms Don’ts
It is true that is important.
But it is not what we need here.
Show that the steps taken
by the algorithm are valid.
How do we prove optSours is valid?
‹#›
37
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.
How do we prove optSours is valid?
‹#›
38
Greedy Algorithms Don’ts
It is true that is important.
But it is not what we need here.
Show that the steps taken by the algorithm
are the best choice available.
How do we prove optSours is optimal?
‹#›
39
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.
How do we prove optSours is valid?
Good
‹#›
40
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
‹#›
41
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
‹#›
42
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.
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.
‹#›
43
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)
‹#›
44
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.
‹#›
45
End
‹#›
46
/docProps/thumbnail.jpeg