Study Guides (390,000)
CA (150,000)
UW (7,000)
CS (400)
CS116 (10)
Final

# Lecture Notes + Examples Lecture notes and examples

Department
Computer Science
Course Code
CS116
Professor
Jiye Li
Study Guide
Final

This preview shows pages 1-3. to view the full 14 pages of the document.
CS 116
Introduction to Computer Science
Module 1: Review
Design Recipe- A development process that leaves behind a written explanation:
1. Contract – Describes what type of arguments the function consumes and what value it
produces
2. Purpose – Describes what the program is to compute (i.e. consumes & produces)
3. Examples – Illustrating use of the program
4. Definition – Scheme definition of the function
5. Tests – A representative set of inputs and expected outputs
ex. ;; sum-of-squares: num num -> num
;; Purpose: produces sum of squares of arg1 and arg2
;; Examples: (sum-of squares 0 2.5) => 6.25
;; (sum-of-squares 3 4) => 25
(define (sum-of-squares arg1 arg2) (+ (* arg1 arg1) (* arg2 arg2)))
;; Test sum-of-squares
(check-expect (sum-of-squares 2 3) 13)
(check-expect (sum-of-squares -1 1) 2)
* check-expect is used for exact numbers only; use check-within for a range of values
Structure- Combines a fixed number of values into a single piece of data; represents
compounds of information
1) Structure Definition:
(define-struct nameofstructure (var1 var2 … vark))
2) Data Definition:
;; comment on the constraints of each var
3) Regular design recipe
(i) Contract
instead of num, symbol, string, etc. use the name of the structure
for the use of one type of variable, use (union type1 type2 … etc)
ex. mminfo-artist: (union mp3info movieinfo) string
(mminfo-artist (make-mp3info "Beck" "Time Bomb" 183 'Rock)
=> "Beck"
(mminfo-artist (make-movieinfo "Orson Welles" "Citizen
Kane" 119 'Classic)) => "Orson Welles"
(ii) Purpose
(iii) Examples
(iv) Testing
Create structure:
(define structure1 (make-nameofstructure n1 n2 … nk))
Extract a single item from structure using selector functions:
(nameofstructure-var1 structure1) => n1
(nameofstructure-var2 structure1) => n2
...
(nameofstructure-vark structure1) => nk
1

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Ex. (define-struct date (year month day hour))
;; A date is a structure (make-date y m d h) where y is a positive
integer (>= 2009) representing the year. m, a month in a year, is an
integer in the range of 1 to 12 inclusive. d, a day in a month, is
an integer in the range of 1 to 31 inclusive. h is an integer in the
range of 0 to 23 inclusive to represent an hour in a day.
(define date1 (make-date 2001 6 2 23))
(date-year date1) => 2001
(date-month date1) => 6
(date-day date1) => 2
(date-hour date1) => 23
local contains a series of local definitions (variables, helper functions, constants, etc.) plus
an expression (evaluation) using them of the form:
(local
[(...def1...)
(...def2...)
...]
exp)
Module 2: More Functional Abstraction
filter consumes a predicate and a list and filters out all items in that list that produce true
to the predicate
;; filter: (X boolean) (listof X) (listof X)
(define (filter pred alist)
(cond
[(empty? alist) empty]
[(pred (first alist))
(cons (first alist) (filter pred (rest alist)))]
[else (filter pred (rest alist))]))
Ex. (filter even? '(1 2 3 4 5 7)) => '(2 4)
map transforms a list element-by-element into another list of the same length
;; map: (X Y) (listof X) (listof Y)
(define (map f alist)
(cond
[(empty? alist) empty]
[else (cons (f (first alist)) (map f (rest alist)))]))
Ex. (map sqr '(2 3 4)) => '(4 9 16)
foldr consumes a list of X and produces a Y by processing the list to the right
;; foldr: (X X X) X (listof X) X
(define (foldr combine base alist)
(cond
[(empty? alist) base]
[else (combine (first alist)
(foldr combine base (rest alist)))]))
Ex. (foldr + 0 '(1 2 3)) => 6
(foldr max 0 '(2 4 6 8)) => 8
2

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

member consumes X and a list of X and produces True if the list of X contains the given X
;; member: X (listof X) boolean
(define (member x lox)
(cond
[(empty? lox) false]
[(equal? x (first lox)) true]
[else (member x (rest lox))]))
Ex. (member 'a '(a b c)) => true
Polymorphic Function- has a contract that has variables for the types; arguments are
flexible
build-list consumes a natural number greater than zero and a function and produces a
list of every natural number from 0 to the inputted number with the function applied to it
;; build-list: nat (nat X) (listof X)
(define (build-list n func)
(local
[(define (count-up x i)
(cond
[(= n i) empty]
[else (cons i (count-up (add1 i)))]))]
(map func (count-up n 0)))
Ex. (build-list 6 sqr) => '(0 1 4 9 16 25)
lambda lets us build a function from scratch: (lambda (p1 p2 … pn) expr)
where (p1 p2 … pn) are the parameters and expr is the expression that evaluates the
parameter(s); can be used to build an anonymous function
(define (power-of-2 n) (define (power-of-2 n)
(local => (build-list n (lambda (x)
[(define (fn x) (expt 2 x))))
(expt 2 x))]
(build-list n fn))
arithmetic is a list of functions '( + - * /)
Module 3: Generative Recursion
Natural/Structural Recursion- Follows templates derived from a self-referential data
definition; has a template that tests a base case, etc.
Generative Recursion- More complex recursion that may make the program run faster
where structural recursion may not be the best way to solve a problem; the argument of the
recursive (function) application is “generated” by new volumes of data, not just recursion on
the rest of the list
Ex. Selection Sort
Using Structural Recursion:
(define (sort-list lon)
(cond
[(empty? lon) empty]
[else (insert (first lon) (sort-list (rest lon)))]))
(define (insert item sortedlist)
(cond
3