Functional Problem Solving (CSC 151 2015S) : EBoards
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Taking Notes] [Rubric] - [Calendar]
Current: [Assignment] [EBoard am] [EBoard pm] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards am] [EBoards pm] [Labs] [Outlines] [Readings] - [Examples] [Handouts]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014F)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Book Office Hours] - [Issue Tracker (Course)]
Overview
I know I can't ask you a direct question about the exam, but could you answer the following?
You can ask me a direct question about the exam. I may not answer it, or a I may answer it obliquely. But you are certainly permitted to ask.
Any hints?
I've added hints to a few problems in which people asked for hints, particularly the one on speeding up code. You will also find it useful to look more deeply at the Q and A section of the exam, because the questions people ask can provide hints.
Have two people spent at least four hours on the exam or completed the exam?
Yes. That's among the reasons that there are now only seven problems.
Q (from Sam): What do you expect to get from the expression (> x (and y z))?
(I think this is intended to mean "if x is greater than both y and z".)
I find it useful to think about concrete values: What is (> 3 (and 5 1))?
A (from "volunteer"): Well, Scheme evaluates inside-out.
(and 5 1)is 1.(> 3 1)is #t.
Normal Recursion: Assume we can solve a "smaller" version of the problem (typically involving the cdr of the list). Combine that into an overall solution. "The magic recursion fairy makes it all work."
Let's do a simple example: Counting the number of dark colors in a list.
;;; Procedure:
;;; tally-dark
;;; Parameters:
;;; colors, a list of integer-encoded RGB colors
;;; Purpose:
;;; Count the number of colors in the list that are dark.
;;; Produces:
;;; number-of-dark-colors, a non-negative integer
;;; Preconditions:
;;; [No additional]
;;; Postconditions:
;;; (<= number-of-dark-colors (length colors))
;;; "The rest is hard to explain formally."
(define tally-dark
(lambda (colors)
(if (_test_for_base_case_)
_base_case_result_
(_compute_ (tally-dark (cdr colors))))))
(define tally-dark
(lambda (colors)
(cond
[(_test_for_base_case_) _base_case_result_]
[(_check?_ (car colors)) (_compute_ (tally-dark (cdr colors)))]
[else (_compute_ (tally-dark (cdr colors)))])))
If the list has no elements, there are no dark elements
(define tally-dark
(lambda (colors)
(cond
[(null? color) 0]
[(irgb-dark? (car colors)) (+ 1 (tally-dark (cdr colors)))]
[else (tally-dark (cdr colors))])))
How does Scheme process this?
(tally-dark (list black white black black))
; Not null
; The car is dark
(+ 1 (tally-dark (cdr (list black white black black))))
; Do the cdr
(+ 1 (tally-dark (list white black black)))
; Now we have to do tally-dark before we can add
; Not null
; car is not dark
(+ 1 (tally-dark (cdr (list white black black))))
; Do the cdr
(+ 1 (tally-dark (list black black)))
; Not null
; The car is dark
(+ 1 (+ 1 (tally-dark (cdr (list black black)))))
; Do the cdr
(+ 1 (+ 1 (tally-dark (list black))))
; Is it null? No
; Is the dark? Yes
(+ 1 (+ 1 (+ 1 (tally-dark (cdr (list black))))))
; Take the cdr
(+ 1 (+ 1 (+ 1 (tally-dark null))))
; Is null null? null is null. That Sam I am that Sam I am I
; do null like that sam i am.
(+ 1 (+ 1 (+ 1 0)))
; Add
(+ 1 (+ 1 1))
; Add
(+ 1 2)
; Add
3
; We are done!
The recursive solution, while correct, does not match our intuition. Most of us would keep a running total.
remaining tally
'(black white black black) 0 ; First is dark! Add 1
'(white black black) 1 ; First is light; Keep as is
'(black black) 1 ; First is dark! Add 1
'(black) 2 ; First is dark! Add 1
'() 3 ; Done!
Let's write the code
(define tally-dark-colonel
(lambda (remaining tally)
(cond
[(null? remaining) tally]
[(irgb-dark? (car remaining))
(tally-dark-colonel (cdr remaining) (+ 1 tally))]
[else
(tally-dark-colonel (cdr remaining) tally)])))
We can watch the processing
(display (list 'tally-dark-colonel remaining tally))
(newline)
Example
(define tally-odd-colonel
(lambda (remaining tally)
(display (list 'tally-odd-colonel remaining tally))
(newline)
(cond
[(null? remaining) tally]
[(odd? (car remaining))
(tally-odd-colonel (cdr remaining) (+ 1 tally))]
[else
(tally-odd-colonel (cdr remaining) tally)])))
Watch it run
(tally-odd-colonel (list 3 1 6 3 2 4 5 8 9) 0) (tally-odd-colonel (3 1 6 3 2 4 5 8 9) 0) (tally-odd-colonel (1 6 3 2 4 5 8 9) 1) (tally-odd-colonel (6 3 2 4 5 8 9) 2) (tally-odd-colonel (3 2 4 5 8 9) 2) (tally-odd-colonel (2 4 5 8 9) 3) (tally-odd-colonel (4 5 8 9) 3) (tally-odd-colonel (5 8 9) 3) (tally-odd-colonel (8 9) 4) (tally-odd-colonel (9) 4) (tally-odd-colonel () 5) 5