CSC151 2007S, Class 10: Why LISP? Admin: * Please make the effort to be in class on time! * HW 3 returned. We'll spend a bit of time discussing it. * Which of the following C-related concepts are you comfortable with: Header files, Makefiles, Macros? * Are there questions on homework 4? * Don't forget Friday's lunch with Atul Gupta. Overview: * Why lists? * Graham's differences. * Other issues. /HW3/ About 1/3 of you wrote incorrect exponentiation procedures. * Analysis would help * The efficient version used a helper, y Original X and N At each iteration, you'd change y, x, and/or n. At the end, n is 0 and we return y y * x^n = X^N Also works as a loop invariant // Invariant: y * x^n = X^N while (n > 0) { // Suppose n is odd, if ((n % 2) == 1) { // make it even n = n-1 // Whoops y*x^n has now been divided by x. Restore the invt y = y*x; } else { // n is even n = n/2; // How do we restore the invariant? // (1) Multiply y by x^(n/2) NOPE // (2) We need x_new^n_new = x_old^n_old // where n_new = n_old/2 // For what q is q^(n/2) = x^n? // q = x_new = x^2 x = x*x; } /NEW STUFF/ while (true) { if (foo) { bar; baz; bubble; } Q: What if copying and pasting makes my code ugly? A: Use an attachemnt } /Programming *well* in C/ In Quicksort, it would make sense to have at least four .c files quicksort.c Provides void quicksort(int[] a, int n) stack.c Provides stack operations quicksort_unit_test.c Provides main for unit testing qs.c Provides main for interactive testing int_array_utils.c Provides the array operations you need Why separate main from quicksort? * It's more effort to take it out later than it is to never leave it in. * You may want multiple mains Why have separate files for stack.c and array_utils.c? * Simplifies error checking * Makes it easier for other people to test * Code reuse * Code update Part of the principle of refactoring * Idea: When you write nearly identical code twice (or when you find that you're programming by copy-and-paste), make a common routine for the common code. /Given this separation, how do I build qs?/ * quicksort.c stack.c ia_utils.c qs.c * A strategy that makes Sam scream (DO NOT USE) /* qs.c - A test of quicksort */ #include "quicksort.c" #include "stack.c" #include "ia_utils.c" int main(int argc, int **argv) { ... } * Simple, but ugly, strategy cc -o qs quicksort.c stack.c ia_utils.c qs.c * Use a Makefile qs: quicksort.o stack.o ia_utils.o qs.o cc -o qs quicksort.o stack.o ia_utils.o qs.o /HW4/