To begin, let's answer some questions:
There's so much information and rules... where do I start?
If you haven't already, you should learn the basics of environment diagrams as outlined in one of our past TA's resources and review week 1's discussion worksheet!
But Michael, why are we learning this?
Sometimes, code can get complicated. Environment diagrams will help you visualize which stack frames have which variables and give you information about the current state of the functions you're executing.
Does this come in handy in real life?
Our problems are purposefully tricky and convuluted. This is so you get really good at it. Once you get enough practice, you'll be able to mentally apply this knowledge of environment diagrams in the code base at any tech company you're working at. In my personal experience, it has come in handy in other CS courses as well as interviews (!!)
I don't wanna do thi-
wasn't a question. let's start!
Work it out with pencil and paper first, then copy and paste into pythontutor for the answer ;~)
def listenup(oski): count = 0 if not oski: return count else: count += max(len(oski[count]), len(oski)) def denero(x, y): return lambda z, h: y + h if count * 2 == len(oski + oski[-1]): return denero(len(oski), oski) return listenup(oski[::-1]) me = listenup(["I", "Love", "Lists"]) you = listenup(["You", "Also", "Love", "Lists"]) print(me(you(me(you, "None"), "2"), "denero"))
Runtime (Synonymous with 'Orders of Growth'), is the term used to describe the efficiency of various algorithms. In 61A, you'll develop an intuitive sense for how much it "costs" to run through a particular function using Big-O/Theta (for our purposes, we'll treat these as synonymous terms) notation.
If you've regularly attended discussion *cough* please go *cough*, you'll probably be familiar with the pertinent common orders of runtimes. If not, here's some review. They're listed from fastest runtime to slowest:
\(\Theta(1)\) Constant \(\Theta(log(N))\) Logarithmic \(\Theta(N)\) Linear \(\Theta(N^2), \Theta(N^3)\), etc... Polynomial time \(\Theta(2^N)\) Exponential Time
Sometimes you'll even run into some runtimes that are combinations or variations of the common orders, like \(\Theta(Nlog(N)), \Theta(N^N), \Theta(4^N)\), or even \(\Theta(N!)\). Scared yet? You probably won't need to be too concerned with some crazy variation (until 61B that is :^) ), but if it comes up on an exam, hopefully you'll have a better sense of identifying the tricky ones after you browse some of the problems listed below. Let's start by looking at a simple problem:
def printer(N): for i in range(N): print(i)
As a rule of thumb, when analyzing algorithms, you'll want to note how many times you "perform an operation". This includes things like making recursive calls and using a 'for' loop to traverse an array, In this case, you're printing each item in a list of N size. Of course you'd have to then you iterate through a list of N items, and proceed to print out each item. In this case, you'll go through N items, so you can denote that as a runtime of N.
What about this problem? It's trickier - It takes an array of integers (let's pretend that each integer value in this array represents calories of food you ate) as an input and prints out how many bites of food you took as well as how many calories you consumed.
def foodEater(FoodCalories): bites = 0 calsconsumed = 0 for x in FoodCalories: bites += 1 for y in FoodCalories: calsconsumed += y print("I took" + bites + "bites of food and consumed" + calsconsumed + "calories, yikes!")
In this code, you can see that there are two "for" loops. Take time to convince yourself that the total runtime would be \(\Theta(N+N)\), or \(\Theta(2N)\). However, the fact that we're iterating through two separate for loops doesn't affect the OVERALL runtime, so we can generalize this cost to \( \Theta(N)\). Cue cool topic transition...
Drop the constants.
\(\Theta(5N)\) will simplify to \(\Theta(N)\)
\(\Theta(999)\) simplifies to \(\Theta(1)\).
Drop the non-dominant runtimes
\(\Theta(3N^3 + N^2 + 9)\) is upper bounded by \(\Theta(N^3)\).
\(\Theta(N + N + N)\) is \(\Theta(3N)\), so it'll simplify to \(\Theta(N)\).
CORRELATIONS WARNING: do NOT always rely on this to hold true, but it's a good way to guess if you really can't figure out what the runtime is.
"for" loop: If iterating through the entire range of a number or an array of N-size, it will be \(\Theta(N)\)
Double-nested "for" loop: \(\Theta(N^2)\)
Triple-nested "for" loop: \(\Theta(N^3)\), etc..
Trees with N leaves can usually be generalized as \(\Theta(N^d)\) where d is the depth of the tree.
Binary Trees are usually \(\Theta(2^N)\), since they have two leaves for each tree.
Binary Search, or instances where you find a recursive call on half of the elements at a time: \(\Theta(log(N))\)
This code takes in an integer N, and outputs a number.
def splitter(N): if N <= 0: return 2 return splitter(N-1) + splitter(N-1)
This code takes in a balanced binary search tree, and returns the summation of all the nodes in the tree.
def treeSum(tree): if tree == null: return 0 else: return treeSum(tree.left) + tree.value + treeSum(tree.right)
This code computes the power of \(A^B\). Assumes \(B \ge 0\).
def powers(A, B): if B == 0: return 1 else: return A * powers(A, B-1)
This code computes the remainder of \(A \over B\) (aka A % B). Assumes \(B \gt 0 \).
def remainder(A , B): div = A // B return A - div * B
The following code computes the integer square root of a number. If the number is not a perfect square, then it returns -1. It does this by a process called successive guessing. What is its runtime?
def sqrooter(N): return sqrt_helper(N, 1, N) def sqrt_helper(N, min, max): if max < min: return -1 guess = (min + max) // 2 if (guess * guess) == N: return guess // found it! elif (guess * guess) < N: return sqrt_helper(N, guess + 1, max) // Try a higher guess else: return sqrt_helper(N, 1, guess - 1) // Try a lower guess
This code functions similarly to the one above, it's just written differently. What is it's runtime?
def sqrooter(N): guess = 1 while (guess * guess) <= N: if (guess * guess) == N: return guess guess += 1 return -1
This code takes in an integer and returns the summation of the digits.
def digitizer(N): sum = 0 if N < 0: N *= -1 while N > 0: sum += N % 10 N = N // 10 return sum