6.001 Tutorial 3 NotesGerald Dalley22 Feb 2005Orders of Growth ReviewThe simplest way of determining order of growth isto figure out how much extra work is necessary whenyou change the size of the problem. A few rules youcan generally use to solve by inspection (n is the sizeof the old problem, n0is the size of the new problem):• If n0= n − C, the order is Θ(n).• If n0=nC, the order is Θ(log n).• If n0= (n − C) + (n − C), the order is Θ(2n).The let Special Formlet is a piece of syntactic sugar to allow us to createtemporary local variables. We do transformations ofthe form:Rewrite(define (greatest-value x y)(max (+ x y) (- x y)))by using the let special form instead of the max pro-cedure:Pairs and ListsThe cons procedure creates a cons cell (also knowsas a pair), which has two elements, the car and cdr.The car and cdr can both have any type of value. Wedraw pairs as two boxes stuck together, where thefirst box is the car, the second is the cdr. We drawarrows out of the boxes to show what values theyhave – always drawing a down arrow out of the car,a right arrow out of the cdr.We can chain cons cells together to create lists. Alist is a set of cons cells where the cdr of one pointsto the next, and the cdr of the last cons cell points tonil, the sp ecial value that means the empty list. Forvarious (sometimes) useful reasons, our implementa-tion of Scheme defines nil to be the same as false –nil, (), and #f all mean exactly the same thing.The basic procedures that you need to understandand be familiar with are cons, car, cdr, and list.For the most part, we don’t care about dotted pairs,so cons takes something and a list (possibly empty),and sticks that something on the front of the list. cartakes a non-empty list and returns the first thing init; cdr returns everything but the first thing. listtakes any number of things and returns a list of themall.Boxes and PointersFor the following problems, give the box-and-pointerrepresentation and the printed representation.(cons 1 2)(cons 1 (cons 3 (cons 5 nil)))1(cons (cons (cons 3 2) (cons 1 0)) nil)(cons 0 (list 1 2))(list (cons 1 2) (list 4 5) 3)Write Scheme co de that would produce the follow-ing printed representations.(1 2 3)(1 2 . 3)((1 2) (3 4) (5 6))Practice Problems; ; This p ro ce du re r e t u r n s t he l e n g t h; ; ( i . e . number of e le m en ts ) in a l i s t( d e f i n e ( length l s t )Time = Θ( ), Space = Θ( ), n =; ; This p ro ce du re r e t u r n s t he nth; ; e lem ent o f a l i s t , where t h e f i r s t; ; e lem ent has in d ex 0( d e f i n e ( l i s t − r e f l s t n )Time = Θ( ), Space = Θ( ), n =; ; This p ro ce du re j o i n s two l i s t s t o g e t h e r; ; e . g . ( append ( l i s t 1 2 ) ( l i s t 3 4 ) ); ; g i v e s ( 1 2 3 4 )( d e f i n e ( append l s t 1 l s t 2 )Time = Θ( ), Space = Θ( ), n =; ; This p ro ce du re r e v e r s e s th e or de r o f; ; e l em en ts in a l i s t append may be u s e f u l( d e f i n e ( reverse l s t )Time = Θ( ), Space = Θ( ), n =; ; Swaps th e f i r s t and secon d i te ms in; ; a l i s t t h a t has a t l e a s t 2 i te ms; ; ( swap− first− and− second ( l i s t 1 2 3 ) ); ; ; Value : ( 2 1 3 )( d e f i n e ( swap− first− and− second l s t )Time = Θ( ), Space = Θ( ), n =HOPsHigher-order procedures are procedures that eitheraccept procedures as arguments or return proceduresas their values.; ; This p ro ce du re a p p l i e s f t o each; ; e lem ent o f t h e l i s t , and r e t u r n s a; ; new l i s t made from t h o s e v a l u e s( d e f i n e (map f l s t )Time = Θ( ), Space = Θ( ), n
View Full Document
Unlocking...