Report

מבוא מורחב למדעי המחשב בשפת Scheme תרגול 5 Outline • Let* • List and pairs manipulations – Insertion Sort • Abstraction Barriers – Fractals – Mobile 2 let* (let* ((<var1> <exp1>)… (<varn> <expn>)) <body>) is (almost) equivalent to (let ((<var1> <exp1>)) (let* ((<var2> <exp2>)… (<varn> <expn>)) <body>)) 3 let vs. let* (let ((x 2) (y 3)) (let ((x 7) (z (+ x y))) (* z x))) ==> 35 4 let vs. let* (let ((x 2) (y 3)) (let* ((x 7) (z (+ x y))) (* z x))) ==> 70 5 cons, car, cdr, list (cons 1 2) is a pair => (1 . 2) box and pointer diagram: 2 1 nil = () the empty list (null in Dr. Scheme) (list 1) = (cons 1 nil) => (1) 1 6 (car (list 1 2)) => 1 (cdr (list 1 2)) => (2) (cadr (list 1 2)) => 2 (cddr (list 1 2)) => () 1 2 7 (list 1 (list (list 2 3) 4) (cons 5 (list 6 7)) 8) 8 1 5 6 7 4 2 3 8 (5 4 (3 2) 1) (list 5 4 (list 3 2) 1) (cons 5 (cons 4 (cons (cons 3 (cons 2 nil)) (cons 1 null)))) 5 4 1 3 2 How to reach the 3 with cars and cdrs? (car (car (cdr (cdr x)))) 9 cdr-ing down a list cons-ing up a list (add-sort 4 (list 1 3 5 7 9)) (1 3 4 5 7 9) (add-sort 5 ‘()) (5) (add-sort 6 (list 1 2 3)) (1 2 3 6) cdr-ing down (define (add-sort n s) (cond ((null? s) (list n)) ((< n (car s)) (cons n s)) (else (cons (car s) (add-sort n (cdr s)))))) cons-ing up 10 Insertion sort • An empty list is already sorted • To sort a list with n elements: – Drop the first element – Sort remaining n-1 elements (recursively) – Insert the first element to correct place • • • • • • (7 3 5 9 1) (3 5 9 1) (5 9 1) (9 1) (1) () (1 3 5 7 9) (1 3 5 9) (1 5 9) (1 9) (1) Time () Complexity? 11 Implementation (define (insertion-sort s) (if (null? s) null (add-sort (car s) (insertion-sort (cdr s))))) 12 Fractals Definitions: • A mathematically generated pattern that is reproducible at any magnification or reduction. • A self-similar structure whose geometrical and topographical features are recapitulated in miniature on finer and finer scales. • An algorithm, or shape, characterized by self-similarity and produced by recursive 13 sub-division. Sierpinski triangle • Given the three endpoints of a triangle, draw the triangle • Compute the midpoint of each side • Connect these midpoints to each other, dividing the given triangle into four triangles • Repeat the process for the three outer triangles 14 Sierpinski triangle – Scheme version (define (sierpinski triangle) (cond ((too-small? triangle) #t) (else (draw-triangle triangle) (sierpinski [outer triangle 1] (sierpinski [outer triangle 2] (sierpinski [outer triangle 3] ) ) )))) 15 Scheme triangle Constructor: Selectors: Predicate: Draw: (define (define (define (define (make-triangle a b (a-point triangle) (b-point triangle) (c-point triangle) c) (list a b c)) (car triangle)) (cadr triangle)) (caddr triangle)) (define (too-small? triangle) (let ((a (a-point triangle)) (b (b-point triangle)) (c (c-point triangle))) (or (< (distance a b) 2) (< (distance b c) 2) (< (distance c a) 2)))) (define (draw-triangle triangle) (let ((a (a-point triangle)) (b (b-point triangle)) (c (c-point triangle))) (and ((draw-line view) a b my-color) ((draw-line view) b c my-color) ((draw-line view) c a my-color)))) 16 Points Constructor: Selectors: (define (make-posn x y) (list x y)) (define (posn-x posn) (car posn)) (define (posn-y posn) (cadr posn)) (define (mid-point a b) (make-posn (mid (posn-x a) (posn-x b)) (mid (posn-y a) (posn-y b)))) (define (mid x y) (/ (+ x y) 2)) (define (distance a b) (sqrt (+ (square (- (posn-x a) (posn-x b))) (square (- (posn-y a) (posn-y b)))))) 17 Sierpinski triangle – Scheme final version (define (sierpinski triangle) (cond ((too-small? triangle) #t) (else (let ((a (a-point triangle)) (b (b-point triangle)) (c (c-point triangle))) (let ((a-b (mid-point a b)) (b-c (mid-point b c)) (c-a (mid-point c a))) (and (draw-triangle triangle) (sierpinski (make-triangle a a-b c-a))) (sierpinski (make-triangle b a-b b-c))) (sierpinski (make-triangle c c-a b-c))))))))) 18 Abstraction barriers Programs that use Triangles Triangles in problem domain too-small? draw-triangle Triangles as lists of three points make-triangle a-point b-point c-point Points as lists of two coordinates (x,y) make-posn posn-x posn-y Points as lists cons list car cdr 19 Mobile 20 Mobile • Left and Right branches • Constructor – (make-mobile left right) • Selectors – (left-branch mobile) – (right-branch mobile) 21 Branch • Length and Structure – Length is a number – Structure is… • Another mobile • A leaf (degenerate mobile) – Weight is a number • Constructor – (make-branch length structure) • Selectors – (branch-length branch) – (branch-structure branch) 22 Building mobiles (define m (make-mobile 4 8 (make-branch 4 6) 4 (make-branch 2 6 8 1 2 (make-mobile (make-branch 4 1) (make-branch 2 2))))) 23 Mobile weight • A leaf’s weight is its value • A mobile’s weight is: – Sum of all leaves = – Sum of weights on both sides • (total-weight m) – 9 (6+1+2) 6 1 2 24 Mobile weight (define (total-weight mobile) (if (atom? mobile) mobile (+ (total-weight (branch-structure (left-branch mobile))) (total-weight (branch-structure (right-branch mobile))) ))) (define (atom? x) (and (not (pair? x)) (not (null? x)))) 25 Complexity Analysis • What does “n” represent? – Number of weights? – Number of weights, sub-mobiles and branches? – Number of pairs? – All of the above? • Analysis – (n) – Depends on mobile’s size, not structure 26 Balanced mobiles • Leaf – Always Balanced • Rod 4 8 – Equal moments – F = length x weight • Mobile 5 1 6 1 2 – All rods are balanced = – Main rod is balanced, and both sub-mobiles • (balanced? m) 27 balanced? (define (balanced? mobile) (or (atom? mobile) (let ((l (left-branch mobile)) (r (right-branch mobile))) (and (= (* (branch-length l) (total-weight (branch-structure l))) (* (branch-length r) (total-weight (branch-structure r)))) (balanced? (branch-structure l)) (balanced? (branch-structure r)))))) 28 Complexity • Worst case scenario for size n – Need to test all rods – May depend on mobile structure • Upper bound – Apply total-weight on each sub-mobile – O(n2) • Lower bound 29 Mobile structures n n-1 n-2 n-3 ... T(n) = T(n-1) + (n) T(n) = (n2) (for this family of mobiles) 30 Mobile structures n/2 n/4 n/8 n/8 n/4 n/8 n/8 T(n) = 2T(n/2) + (n) T(n) = (nlogn) n/2 n/4 n/8 n/8 n/4 n/8 n/8 (for this family of mobiles) 31 Implementation Constructors (define (make-mobile left right) (list left right)) (define (make-branch length structure) (list length structure)) Selectors (define (left-branch mobile) (car mobile)) (define (right-branch mobile) (cadr mobile)) (define (branch-length branch) (car branch)) (define (branch-structure branch) (cadr branch)) 32 Preprocessing the data • Calculate weight on creation: – (define (make-mobile left right) (list left right (+ (total-weight (branch-structure left)) (total-weight (branch-structure right))))) • New Selector: – (define (mobile-weight mobile) (caddr mobile)) • Simpler total-weight: – (define (total-weight mobile) (if (atom? mobile) mobile (mobile-weight mobile))) 33 Complexity revised • • • • Complexity of new total-weight? Complexity of new constructor? Complexity of balanced? Can we do even better? 34