Recitation notes for 11/3/97 Topics: * go over quiz (median 26, middle half: 20--32) (this is after adding the 5 pts) * another example of a recurrence * analysis of doubling the hash table * alpha-beta game tree search (we'll do balanced search trees on Wed, but there are a few words about them in these notes too) ============================================================================ Another example of a recurrence (from an old midterm): Here is a divide-and-conquer algorithm that merges two sorted arrays a and b of n elements each. Example: a = 1, 2, 3, 8, 9, 10 b = 4, 5, 6, 7, 8, 9 0. Divide the problem into smaller subproblems: Put elements a[0],a[2],...,a[n-2] into an array called a_even, and put elements a[1],a[3],...,a[n-1] into an array called a_odd. Put elements b[0],b[2],...,b[n-2] into an array called b_even, and put elements b[1],b[3],...,b[n-1] into an array called b_odd. 1. Solve the subproblems recursively: Merge arrays a_even and b_even into an array called evens. Merge arrays a_odd and b_odd into an array called odds. In the Example, evens = 1, 3, 4, 6, 8, 9 odds = 2, 5, 7, 8, 9, 10 2. Build the solution from the solution of the subproblems: Intersperse the elements of evens and odds in the following pattern: evens[0],odds[0],evens[1],odds[1],evens[2],odds[2],...,evens[n-1],odds[n-1]. Call the resulting array of n elements mixed. In the example, mixed = 1, 2, 3, 5, 4, 7, 6, 8, 8, 9, 9, 10 Compare each odd element of mixed with the following even element, and swap them if they are out of order, i.e., compare mixed[1] with mixed[2], mixed[3] with mixed[4], ... In the example, we get: 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10 The resulting array is sorted! You don't need to understand *why* this works, but let's work on the running time: Let's write a recurrence: T(n) = c*n + 2T(n/2) + c*n Solves to Theta(n log n) Here is another example (a funny way to add up n numbers that destroys the array of numbers): int sum(int *a, int length){ // destroys array a if (length == 1) return a[0]; for (int i = 0; i < length/2; ++i){ // compute sums of pairs of elements a[i] = a[2*i]+a[2*i+1]; // a[0]+a[1], a[2]+a[3], ... } // if length is odd, then a[length-1] wasn't paired up! if ((length % 2) == 1) a[length/2] = a[length-1]; return sum(a,(length+1)/2); } What's the recurrence? T(n) = T(n/2) + c_1 n T(1) = c_2 What's the solution? T(n) = Theta(n) (By the way, both of these funny algorithms are really intended as parallel algorithms --- if you have a parallel machine they work faster than the usual methods) ============================================================================ Analysis of doubling the hash table: Idea was: when you have as many elements in the table as the size of the table, then double the size an re-hash everything in it. Another way of looking at why average time is still O(1): this is the same as saying that the *total* time is linear in N (N = the final table size). We can see this by noticing that total time we've spent looks like: INIT + 2*INIT + 2*INIT + 4*INIT + 4*INIT + ... + N + N First we hash INIT # of elements, then we allocate a table of size 2*INIT and set them to NULL, then we rehash the first INIT elements plus hash INIT new ones (for a total of 2*INIT). Then we allocate a table of size 4*INIT and set them to NULL. Then we rehash the 2*INIT old ones plus hash 2*INIT new ones (for a total of 4*INIT) etc. Another way to look at this is if we let T(N) be the total time, then we can write T(N) = 2N + T(N/2) because we've done at most 2N work since the time that the N/2-sized table filled up. ============================================================================ Alpha-beta search ----------------- On last hwk, did game tree search. Win/lose/tie. You probably had a loop that tried each possible move and recursively checked to see what result was. Probably had speedup: if you find a winning move, you don't need to check the rest -- can return right then. In more complicated games like chess, you can't search all the way down. Have eval function that returns a "goodness" number. Search to some depth and then return "best" move. E.g., say function returns "goodness to player 1" - so think of 1st player as "maximizer" and 2nd player as "minimizer". o MAX / \ o o MIN / \ / \ o o o o MAX / \ / \ / \ / \ 3 5 6 2 0 4 9 20 results in max being 5, best move being the left one. Called "minimax" games. # levels of search called "# of ply" There's a method can use to speed up search, sort of like "stop when you get to a win" but a little trickier, called "alpha-beta" search. Idea: say you have a tree and have figured out the following so far. o MAX (currently we know this is worth at least 40) / \ 40 o MIN (we know this node is worth at most 30) / \ 30 ?? MAX Do we need to search the "??"? No. Because no matter what we find it won't affect the outcome. Here's another way of looking at it: maybe we originally defined "100" to be a win for MAX and "0" to be a win for MIN. But, right now we can think of "<= 40" as being a win for MIN. Why? Because if MIN ever finds a move that gets it <= 40, MAX will use its other option. Same thing can happen in other direction: o MIN / \ 40 o MAX / \ 50 ?? Idea of alpha-beta pruning: We will think of the range of the values as not being from 0 to 100, but just from alpha to beta. E.g., MIN passes its "best for MIN so far" (beta) to MAX, and if MAX ever finds that its current best is >= beta, it knows it can return immediately. Can be useful even in win/lose/tie setting. E.g., o X player / \ TIE o O player / \ TIE ?? <--don't need to evaluate. I.e., X tells O that "as far as I'm concerned, you can treat a TIE as if it were a WIN for you" NOTE: If you memoize, you need to store the alpha and beta values too. I.e., you're storing info like "on this board, if it is O's turn to move *AND* all you need is a tie, then ..." ------------------------------------------------------------------------- Balanced search trees --------------------- The idea of balanced search trees is that we want to get all the good features of a search tree *and* have all our operations take only O(log n) time. In addition to things you can do with a hash table like insert(x) and lookup(x), search trees are good for things like find_next(x) [find the next in sorted order], find_range(x,y) [find everything between x and y], etc. Some of these operations are especially useful in graphics applications, where you have an object that, say, goes from x-coordinate X_min up to X_max, and you want to find all the objects that it might be occluding. There are a number of ways of achieving Balanced Search Trees. In this course, we will be (have been) looking at two of them: 2-3 trees and AVL trees. Here is what we will expect students to know: * 2-3 trees in pretty much full detail: - what they are - how you do insertion and lookup (not worrying about deletes) - why the operations are O(log n) time each. * AVL trees at the high level: - what tree rotations are - what the AVL property is Note: the reading for this is Ch 9.8 and 9.9 in the book (the course schedule mistakenly says Ch 9.9 and 9.10). We'll do more examples in lecture on Tues and in recitation on Wed. ----------------------------------------------------------------------------