DOC PREVIEW
Berkeley CS 61A - Midterm Programming Review Fa13

This preview shows page 1-2-22-23 out of 23 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS10 Midterm Programming Review● Algorithmic Complexity● RecursionBig Topics● O(1) - constant time○ Say “Hello World:● O(N) - Linear time○ Say each item of a list● O(N^2)○ Compare each item of a list to each other item in a list● O(log(N))○ Binary search on a sorted list● O(2^N)○ Recursive Fibonacci algorithmAlgorithmic Complexity:A Quick RefresherA recursive algorithm is defined in terms of itself:Factorial(N) = N * Factorial(N-1)Fibonacci(N) = Fibonacci (N-1) + Fibonacci(N -2)Recursion: Recursion: Recursion: Recursion:Recursion:Recursion:Recursion:Recursion:Recursion:Recursion:...● Base Case(s): Fibonacci(1) = 1Fibonacci(0) = 0● Recursive Case:Fibonacci(N) = Fibonacci (N-1) + Fibonacci(N -2) Recursion: Recursion: Recursion: Recursion:Recursion:Recursion:Recursion:Recursion:Recursion:Recursion:...Iteration vs. RecursionLets step back for a moment...Practice ProblemsCreate a function named “Foobar Sum,” that when given a positive integer N, returns the sum of all multiples of 3 and 5 between 0 and N, inclusiveTip: Numbers which are multiples of both 3 and 5 (say, 15), should only be used once in the sum!Warm-up ProblemWarm-up ProblemImagine you are a spooky halloween witch, practicing spell incantation. To maximize the value of your time spent, you want to practice the words that appear most often in your ~scary~ spells. Write an algorithm such that given a list of words, you report how many times a given word occurs in the list?For experts: Try both a recursive and an iterative solutionSpooky Problem #1IterativeSpooky Problem #1 SolutionRecursiveSpooky Problem #1 SolutionOh no, Jack the ~evil pumpkin head~ is creating clones! And those clones are making more! But there is some hope! Jack might be an engine of terror, but his clones are not quite as spooky. Given that Jack can produce N clones, and each of his clones can only produce N-1 copies of themselves (those copies being able in turn to produce N-2, and so on), write an algorithm to calculate how many pumpkin heads we willend up with.~Spooky Problem #2~~Spooky problem #2 solution~In skeleton town (Skeletown), skeletons have a rigid social skele-archy. When a new skeleton rolls into town, their skull is measured, and they are placed in a ranking of spookiness by the size of their cranium. Larger skulls are, of course, the spookiest. Write an algorithm that takes a sorted list of cranial diameters and a new skeleton’s measurement, and returns a sorted list including the new skeleton.Spooky problem #3Spooky Problem #3 SolutionBut how did the skeletons get sorted in the first place?! When the first skele-pioneers got to Skeletown, they were all jumbled up! Using the solution from spooky problem #3, write a function called skele-sort, that takes an unsorted list of skeletal cranium measurements, and returns its sorted equivalent.Spooky Problem #4Spooky Problem #4 SolutionYou are a super scary ghost, auditioning for the part of scariest in Halloweentown. You want to know the creepiest way that you can ululate, after a given line for a maximally spooky effect. Due to your limited ghostly lung capacity, this ululation is also limited. For example, with a lung capacity of 2 (measured in O’s, as below), and the line “Boo!”, combinations would include:Boo! oo~~, Boo! oO~~, Boo! Oo~~, Boo! OO~~Write an algorithm to say every possible combination, given a line and a lung capacity, so you can find that perfectly spooky sweet spot.Spooky Problem #5Spooky Problem #5 SolutionAhhh! The zombie apocalypse is upon us! You are filling a pack with supplies, and are trying to figure out the number of ways you could do so. Given the maximum weight (in pounds) you can carry, and the following items:Bottle of water: 1lbFood rations: 2lbZombie disintegration ray (single use): 4lbZombie repellant: 9lbUseless bag of haunted bricks: 15lb(You are at a construction site and are a fan of bricks)Write an algorithm to give the possible number of combinationsSpooky Problem #6Spooky Problem #6 SolutionWhat about algorithmic complexity?~~Spooky


View Full Document

Berkeley CS 61A - Midterm Programming Review Fa13

Download Midterm Programming Review Fa13
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm Programming Review Fa13 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm Programming Review Fa13 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?