CSC 151: Extra Session 9 (Thursday, 6 Nov. 2014) ================================================ Overview -------- * General questions on the exam * A bit of info about the quiz (topics, general forms of questions) * Your questions on recent topics * Sample quiz questions Questions on the exam --------------------- _On problem 6, can we use `map` in building the list, even if we don't use it for the repetition?_ > No. _On problem 3d, what are the input and output types of `shift-up`?_ > `shift-up` takes an integer as input and gives an integer as output. _What if the user wants a character?_ > Then he/she/ze can call `integer->char`. _For problem 4, do we have to use `map`, which appears in the topics?_ > No. But one of your goals is to make the code concise, and `map` often leads to more concise code. _Since the topic of the exam is "recursion", should we assume we'll use recursion on every problem?_ > No. The topic is "recursion and *repetition*", so you are likely to use both. And even then, not all problems require either. Two problems do not mention repetition/iteration/recursion, and probably don't require them. _On problem 8, why is multiplication "faster" than counting?_ > If we were counting down from 1000 to 1 by subtracting 1, we have 999 or so recursive calls. > What if we divide by 2 each time? 1000 -> 500 -> 250 -> 125 -> 125/2 (or 62.5) -> 125/4 (31.25) -> 125/8 -> 125/16 -> 125/32 -> 125/64 -> 125/128. > So we are doing many fewer recursive calls. _Will you take off if we use the "wrong" kind of recursion (helper, rather than direct, or vice versa)?_ > Probably not, provided your code is correct, reasonably efficient, and reasonably concise. About the Quiz -------------- _What's on the quiz?_ > Turtles > Pairs and pair structures (lists, trees, etc.) > Recursion and repetition using the previous things _What kinds of questions might you ask?_ > "Sketch the picture that results from the following set of turtle expressions." > "Sketch the pair structure that corresponds to *this expression*." > "Write the expression that corresponds to *this pair structure*." > "Given *this partially completed tree procedure*, fill in the blanks." > "Show the steps when I apply *this procedure* to *this input." > "Read *this procedure*, tell me what it does, give me the preconditions, and rewrite it so that it's clearer. (Probably only two of the three.) General Questions ----------------- _Can you talk about trees?_ > Trees are structures that are built from pairs (aka "cons cells"). > Trees are like lists except that (1) for a list, only the cdr has to be a list, while in trees, both the car and the cdr have to be trees; (2) for lists, the "simplest list" is null; for trees, the "simplest tree" is often a value of a particular type. _Can you explain the base case of tree recursion?_ > Normal recursion: Keep simplifying until you reach something "simple enough". > Tree recursion. Often recurse on both car and the cdr - likely to be more recursion. Pairs are generally not "simple enough", so our base case is when it's not a pair. And the model of trees above says that if it's not a pair, it's a single value. > We generally make trees of particular types, such as trees of numbers or trees of strings, or trees of colors, or .... So, in a tree of numbers, we know that the base case is a number. In a tree of strings, the base case is a string, .... _Can a tree contain lists?_ > Yes, but then it's hard to tell what part is the tree and what part is a list. And it makes things confusing. > One strategy: Generalize our view of trees. A tree of numbers is either a number or a pair of trees of numbers. A listree of numbers is either: a number, null, or a pair of listrees of numbers. > Hmmm ... that might be something fun for the next exam. _Why would we use trees?_ > To confuse you. (More precisely, to help you think about times in which recursion is more complex.) > As a lead in to things that are also trees, but have more information. > Trees provide one mechanism for simplifying images. _Can we talk about `for-each`?_ > Similar to `map`. > Parameters to `map`? `(map PROC LIST)`. Note that the procedure could be a predefined procedure, a lambda expression, a section (`l-s` or `r-s`) or .... In each case, it applies the procedure to each element of the list, takes the resulting values, and combines them back into a list. > We also have `(map PROC LST1 LST2 ... LSTN)`. Similar meaning: Apply procedure, combine results into a list. > Sometimes our list of values tells us other information, or its information we want to use in different ways. For example, we might represent a continuous line drawing as a list of (turn . forward) pairs. We could have a turtle use each pair to turn and movev, but we don't need values back. We would use `for-each` for this. > Model `(for-each PROC LIST)`. The `PROC` is a side-effecting procedure (so usually with a ! in its name). Sample code from the `for-each` example --------------------------------------- #lang racket (require gigls/unsafe) (define turtle-step! (lambda (turtle step) (turtle-turn! turtle (car step)) (turtle-forward! turtle (cdr step)))) (define sams-drawing (list (cons 0 10) (cons 90 20) (cons 90 12) (cons 135 24) (cons 225 10))) (define world (image-show (image-new 200 200))) (define sam (turtle-new world)) (turtle-teleport! sam 100 100) (turtle-face! sam -90) (for-each (l-s turtle-step! sam) sams-drawing)