CS61A: Recursion

  • Base case: what is the smallest case?
  • Recursive case: reduce your input size by one and then trust your program works
  • Example1:

counting_partitions

*direction takes one argument called guess and compares the guess to the secret number.

Screen Shot 2017-09-29 at 12.51.35 AM.png

Screen Shot 2017-09-29 at 9.41.46 AM

Screen Shot 2017-09-29 at 1.00.00 AM.png

Screen Shot 2017-09-29 at 1.01.36 AM.png

Advertisements

CS61A: Tree Structure (Part 1)

{Using list to represent trees}

  • Components: constructor, selectors, check is_leaf.
  • Problems: I think the discussion worksheet is pretty comprehensive! Make sure you understand everything on the discussion worksheet.
  • (You wouldn’t be tested too much on this tree representation during the exams; however, understanding this representation is crucial to understand Part 2 of tree structure, which you will be tested on!)

Screen Shot 2017-09-29 at 12.44.54 AM.png

CS61A: List

List mutation summary:

  • .append (+=): pass in an element and mutate the original list
  • .extend: pass in a list and mutate the original list
  • direct assignment: create a copy of the original list without mutating it

Practice problems: (from CSM worksheet and fall 15 midterm)

  • [warm-up] Draw the environment diagram:

Screen Shot 2017-09-27 at 2.28.11 AM.png

solution

  • [warm-up] Write square_list:

Screen Shot 2017-09-27 at 2.31.38 AM

solution

  • Complete the environment diagram:

Screen Shot 2017-09-27 at 2.37.38 AM.png

 

solution

  • More environment diagrams:

Screen Shot 2017-09-27 at 2.42.06 AM.png

solution

  • [challenging] FYI, I didn’t solve this problem when I first tried this problem : (

Screen Shot 2017-09-27 at 2.44.48 AM.png

solution

*I have no idea why I couldn’t rotate the page in some of the solution. If you don’t want to download the pdf and rotate the page manually yourself, go to the original pdf (yes I only took a screenshot).

Solving coding problems: A strategy and an example

CS61A coding problems are tricky. Most of the times, they require you to build some sort of “intuition”. I believe the “intuition” can be trained by following a reasonable procedure when you approach those problems. The strategies vary person by person, problem by problem. However, I’ll still use one example to illustrate how I build my intuition on the coding problems, and I hope the example will help you to find the best way to build your own intuition!

Here’s one challenging problem a student asked me:

Screen Shot 2017-09-22 at 9.15.46 PM.png

Screen Shot 2017-09-22 at 9.16.21 PM.pngI have to admit that this is a very challenging problem. But before you give up or freak out, let’s see whether we can make some progress by answering the following questions:

  1. What is make_check_my_fave_consecutive_sequence? What is add_to_checker? What is update_start? (When answering the “what is [function]” questions, ask yourself 1. what are the arguments? 2. what does the function return?)
  2. What is the relationship between the three functions? (i.e. which function should make_check_my_fave_consecutive_sequence’s return statement calls directly?)
  3. What is the smallest/simplest case? How does that help you to implement helper function/return statement for make_check_my_fave_consecutive_sequence?
  4. What if we pass in a “slightly larger” input? How do you want to modify your code?
  5. Pass in a reasonably large input and confirm your solution. (Don’t need to run the program all the way to the end; correctly use leap of faith in recursion and the idea of abstraction when you do this step). Make small modification if needed.

(A side note: in my opinion, solving those problems is kind of like making educated guess – don’t be afraid to make mistake at first, remember that you can always modify your code!)

After answering the above question, take a look at the solution.

Hope those questions inspire you on how to develop intuition on coding problems! Nevertheless, enjoy solving them (and admire people who came up with those questions :P)!

CS61A Cheatsheet

Environment diagrams:

  • Treat functions are data: they’re just function objects with variable names
  • Lookup the value of a variable: find it in current frame; if couldn’t find it, go up to that frame’s parent frame; keep doing this until you find it. Otherwise, there’s an error.
  • Assignment =
  1. Evaluate RHS
  2. Evaluate LHS
  3. Bind RHS to LHS
  • Call expression ( )
  1. Open a new frame for function call! (don’t need to create a new frame for built in functions)
  2. Evaluate the operator
  3. Evaluate the operand
  4. Execute the body of the function

Check your understanding of (tree) recursion: 

Screen Shot 2017-09-12 at 9.10.37 AM.png