CS3: Introduction to Symbolic ProgrammingFall 2006 Nate [email protected] 11:Tree-recursionMidterm #2 reviewScheduleLecture: Lists, and ?Lab: Work on the projectNov 27–Dec 114Lecture: Lists, and introduce the big projectLab: Lists; start on the projectNov 20-2413Lecture: Midterm #2Lab: Start on "Lists"Nov 13-1712Tree-recursion, Review, Exam problemsLab: Tree recursions, Miniproject #3Reading: "Change Making" case study Simply Scheme, Ch. 15Nov 6-1011Announcements•Midterm 2 is coming…-Next week, 80 minutes (4:10-5:30).-Room 4 Leconte-Open book, open notes, etc.-Check for practice exams and solution on the course portal and in the reader.•Midterm 2 review session-This Sunday, Nov 12, 2-4-430 Soda (as last time)What does midterm #2 cover?•Advanced recursion (accumulating, multiple arguments, etc.). Including tree-recursion•All of higher order functions•Those "big" homeworks (bowling, compress, and occurs-in)•Elections miniproject (!)•Reading and programs:-Change making, -Difference between dates #3 (HOF), -tic-tac-toe•SS chapters 14, 15, 7, 8, 9, 10•Everything before the first Midterm (although, this won't be the focus of a question)Programming Style and Grading•During grading, we are going to start becoming “more strict” on style issues-Starting with miniproject #3-For the big project, style is important•Why?-Program maintenance: 6 months later, will you know what your code does?-Code “literacy”: sharing codeWhat issues of style matter?•Keep procedures small !•Good names for procedures and parameters•Adequate comments-Above and within procedures•Put tests cases in a comment block•Indent to aid program comprehension•Proper use of global variables•Avoid nesting conditional statements•Data abstractionTree recursionAdvanced recursion...........................151010515...146414...13313...1212...111...10...543210rows(R) columns (C)Pascal’sTriangle• How many ways can you choose C things from R choices?• Coefficients of the (x+y)^R: look in row R• etc.(define (pascal C R) (cond ((= C 0) 1) ;base case ((= C R) 1) ;base case (else ;tree recurse (+ (pascal C (- R 1)) (pascal (- C 1) (- R 1)) )))> (pascal 2 5)(+ (pascal 2 5) (pascal 2 4) (pascal 1 4) (+ (+ (pascal 2 3) (pascal 1 3) (pascal 1 3) (pascal 0 3) (+ (pascal 2 2) (pascal 1 2) (pascal 1 2) (pascal 0 2)  1(pascal 1 2) (pascal 0 2)  1 1(+ (pascal 1 1) (pascal 0 1)  1 1(+ (pascal 1 1)  1(pascal 0 1)  1 1(+ (pascal 1 1)  1(pascal 0 1)  1Chips and Drinks(snack 1 2)  3-This includes (chip, drink, drink), (drink, chip, drink), and (drink, drink, chip).(snack 2 2)  6-(c c d d), (c d c d), (c d d c)(d c c d), (d c d c), (d d c c)"I have some bags of chips and some drinks. How many different ways can I finish all of these snacks if I eat one at a time?Midterm like Problems…make-bookends (a small problem)•Write make-bookends, which is used this way:((make-bookends 'o) 'hi)  ohio((make-bookends 'to) 'ron)  toronto(define tom-proc (make-bookends 'tom))(tom-proc "")  tomtomWrite successive-concatenation(sc '(a b c d e))  (a ab abc abcd abcde)(sc '(the big red barn)) (the thebig thebigred thebigredbarn)(define (sc sent) (accumulate (lambda ?? ) sent))make-decreasing•make-decreasing -Takes a sentence of numbers-Returns a sentence of numbers, having removed elements of the input that were not larger than all numbers to the right of them.(make-decreasing '(9 6 7 4 6 2 3 1))  (9 7 6 3 1)(make-decreasing '(3))  (3)Write first as a recursion, then as a HOFCS3: Introduction to Symbolic ProgrammingFall 2006 Nate [email protected] 11:Tree-recursionMidterm #2 review2 Fall 2006 CS3: 2 ScheduleLecture: Lists, and ?Lab: Work on the projectNov 27–Dec 114Lecture: Lists, and introduce the big projectLab: Lists; start on the projectNov 20-2413Lecture: Midterm #2Lab: Start on "Lists"Nov 13-1712Tree-recursion, Review, Exam problemsLab: Tree recursions, Miniproject #3Reading: "Change Making" case study Simply Scheme, Ch. 15Nov 6-1011Fall 2006 CS3: 3 Announcements•Midterm 2 is coming…-Next week, 80 minutes (4:10-5:30).-Room 4 Leconte-Open book, open notes, etc.-Check for practice exams and solution on the course portal and in the reader.•Midterm 2 review session-This Sunday, Nov 12, 2-4-430 Soda (as last time)Fall 2006 CS3: 4 What does midterm #2 cover?•Advanced recursion (accumulating, multiple arguments, etc.). Including tree-recursion•All of higher order functions•Those "big" homeworks (bowling, compress, and occurs-in)•Elections miniproject (!)•Reading and programs:-Change making, -Difference between dates #3 (HOF), -tic-tac-toe•SS chapters 14, 15, 7, 8, 9, 10•Everything before the first Midterm (although, this won't be the focus of a question)Fall 2006 CS3: 5 Programming Style and Grading•During grading, we are going to start becoming “more strict” on style issues-Starting with miniproject #3-For the big project, style is important•Why?-Program maintenance: 6 months later, will you know what your code does?-Code “literacy”: sharing codeFall 2006 CS3: 6 What issues of style matter?•Keep procedures small !•Good names for procedures and parameters•Adequate comments-Above and within procedures•Put tests cases in a comment block•Indent to aid program comprehension•Proper use of global variables•Avoid nesting conditional statements•Data abstractionTree recursionClick to add textFall 2006 CS3: 8 Advanced recursion...........................151010515...146414...13313...1212...111...10...543210rows(R) columns (C)Pascal’sTriangle• How many ways can you choose C things from R choices?• Coefficients of the (x+y)^R: look in row R• etc.Fall 2006 CS3: 9 (define (pascal C R) (cond ((= C 0) 1) ;base case ((= C R) 1) ;base case (else ;tree recurse (+ (pascal C (- R 1)) (pascal (- C 1) (- R 1)) )))Fall 2006 CS3: 10 > (pascal 2 5)(+ (pascal 2 5) (pascal 2 4) (pascal 1 4) (+ (+ (pascal 2 3) (pascal 1 3) (pascal 1 3) (pascal 0 3) (+ (pascal 2 2) (pascal 1 2) (pascal 1 2) (pascal 0 2)  1(pascal 1 2) (pascal 0 2)  1 1(+ (pascal 1 1) (pascal 0 1)  1 1(+ (pascal 1 1)  1(pascal 0 1)  1 1(+ (pascal 1 1) 