CSC151 2007S, Class 20: Analyzing Procedures Admin: * I anticipate returning exam 1 on Monday, so you need not do any readings over the weekend. * However, a new homework will soon by available. * And you should definitely go see Kumail Nanjiani on Saturday night. * Today's lab is brand new Overview: * Overview. * Steps. * Lab. An issue: * We care about how fast our procedures run * Experiment! Add a display to the start of the procedure (define largest-of-list (lambda (lst) (display ('largest-of-list lst)) (newline) (if (null? (cdr lst)) (car lst) (max (car lst) (largest-of-list (cdr lst)))))) Analyzing reverse-1 Length Calls to myappend 0 0 1 1 2 3 3 6 4 10 5 15 6 21 7 28 8 36 9 45 10 55 8 36 16 136 = (36*4 - 8) 32 528 = (136*4 - 16) 64 2080 = (528*4 - 32) > (analyze (reverse-1 null) myappend) Total: 0 () > (analyze (reverse-1 (list 0)) myappend) myappend: 1 Total: 1 (0) > (analyze (reverse-1 (list 0 0)) myappend) myappend: 3 Total: 3 (0 0) > (analyze (reverse-1 (list 0 0 0)) myappend) myappend: 6 Total: 6 (0 0 0) > (analyze (reverse-1 (list 0 0 0 0)) myappend) myappend: 10 Total: 10 (0 0 0 0) > (analyze (reverse-1 (list 0 0 0 0 0)) myappend) myappend: 15 Total: 15 (0 0 0 0 0) What does Sam hope you got out of this lab: * "I should see how slow my procedure is" Number of recursive calls on a list of length N is ideally about N Number of total calls is about C*N, where C is between 1 and 10 * Using (= (length lst) 1) is a bad way to test for a one element list