CPSC 461 Spring 2000 final Exam Answers QUESTION 1 a. script from the movie "The Crow" b. ensures that if a copy is corrupted, the other information on the partition remains accessible c. 1 per group d. - the numbers themselves (ie the data) are important. ie the values rather than their appearance or effect - because of this, the headers have more information in them (most of which essential to the analysis of the data) and are larger. e. sample rate = 2 times the frequency f. - minimize collisions (spread out keys as uniformly as possible) - results are within the specified range - one value in must always result in the same value out g. - format ( eg. bm, pn, jpg) - size in rows and columns - pixel depth - number of colours ( how many bits are used for interpreting each colour) - row order (ie the rows may not be consecutive) h. - voice data produces a smaller frequency range than what we can actually hear. This means we can use fewer bits/sample - the quality of the sound is not as important, eg. understanding what someone is saying over the phone is fairly easy, but understanding music over the phone without vocals is harder. This means the structure of the file can be simpler, since we don't need to to store so much information, which gives us a greater compression. In general, voice data is much less complicated so it requires a smaller bit-depth. **************************************************************************************************** QUESTION 2 Number the nodes, starting at 0 with the root. Since the order is 4, each node has 3 children. Number the children from 1 - 3 starting with the leftmost child, child1 is the leftmost, child2 is the middle, and child3 is the rightmost. so the actual indexing for the array looks like, call the array LIST[someSize] root = LIST[0] level 1 child1 of root = LIST[1]; child2 of root = LIST[2]; child3 of root = LIST[3]; level 2 child1 of LIST[1]= LIST[4]; child2 of LIST[1]= LIST[5]; child3 of LIST[1]= LIST[6]; child1 of LIST[2]= LIST[7]; child2 of LIST[2]= LIST[8]; child3 of LIST[2]= LIST[9]; child1 of LIST[3]= LIST[10]; child2 of LIST[3]= LIST[11]; child3 of LIST[3]= LIST[12]; a. given that parent = LIST[j] then Child1 = LIST[(j*(order-1) + 1)] Child2 = LIST[(j*(order-1) + 2)] Child3 = LIST[(j*(order-1) + 3)] Parent = LIST[(index of child)-1 ) / N] b. allocate a new array with a size of ( 2 * the original size +1 ) preserve the same ordering of parent/children. keep using the same formulas to calculate child and parent, but if the index you get for a child is larger than the size of the original array, then use IndexInTheNewArray = SizeOfNewArray - (index *2 +1) OR dynamic allocation c. - can calculate locations, don't have to dereference pointers - no need to worry about splitting nodes, just move keys around as necessay (this is also a disadvantage, since if you move a key, then you must move all of it's descendants) - space requirements change very predictably. d. disadvantages: wastes space in a partially empty tree. involves more shuffling than when using dynamic allocation advantages: locality of nodes is built in can pad nodes as necessary to match block size makes for a faily predictable behaviour, allowing for confidence in performance predications *************************************************************************************************** QUESTION 3 key 14 51 37 18 16 25 36 17 11 27 hash(key) 3 7 4 7 5 3 3 6 0 5 i(key) 1 4 3 1 1 2 3 1 1 2 ---------------------------------------------------------------------------------------- step 1 insert 14 @ 3 no collisions index 0 1 2 3 4 5 6 7 8 9 10 key 14 ---------------------------------------------------------------------------------------- step 2 insert 51 @ 7 no collisions index 0 1 2 3 4 5 6 7 8 9 10 key 14 51 ---------------------------------------------------------------------------------------- step 3 insert 37 @ 4 no collisions index 0 1 2 3 4 5 6 7 8 9 10 key 14 37 51 ---------------------------------------------------------------------------------------- step 4 insert 18 @ 7 collision! try 18 at it's next increment location 7+1=8 8 is empty index 0 1 2 3 4 5 6 7 8 9 10 key 14 37 51 18 ---------------------------------------------------------------------------------------- step 5 insert 16 @ 5 no collision index 0 1 2 3 4 5 6 7 8 9 10 key 14 37 16 51 18 ---------------------------------------------------------------------------------------- step 6 insert 25 @ 5 collision! build tree results of tree: move 16 to 6 place 25 at 5 index 0 1 2 3 4 5 6 7 8 9 10 key 14 37 25 16 51 18 ---------------------------------------------------------------------------------------- step 7 insert 36 @ 3 collision! build tree results of tree: place 36 @ 9 index 0 1 2 3 4 5 6 7 8 9 10 key 14 37 25 16 51 18 36 ---------------------------------------------------------------------------------------- step 8 insert 17 @ 6 collision! build tree results of tree: move 51 to 0 place 17 @ 7 index 0 1 2 3 4 5 6 7 8 9 10 key 51 14 37 25 16 17 18 36 ---------------------------------------------------------------------------------------- step 9 insert 11 @ 0 collision! try 11 at it's next increment location 0+1=1 1 is empty index 0 1 2 3 4 5 6 7 8 9 10 key 51 11 14 37 25 16 17 18 36 ---------------------------------------------------------------------------------------- step 10 insert 27 @ 5 collision! build tree results of tree: move 11 to 2 move 36 to 1 place 27 @ 9 index 0 1 2 3 4 5 6 7 8 9 10 key 51 36 11 14 37 25 16 17 18 27 *************************************************************************************************** QUESTION 4 - a tournament tree is a binary tree. use an array for simplicity and speed (size of tree won't change), and also because we need to go up and down the tree, an array makes non-recursive travel easy. - each array element must hold the key value and the index of the file it came from. Don't need anything else. - for the records themselves, create an input buffer big enough to hold N records from each file, where N is 1 or more. ( when the last record from file # K is written, refill K's portion of the buffer) - watch out for EOF on individual files. Need a "tombstone" to place in the tree. value will be 1 more than the maximum key value. ( since it must never be allowed to win a tournament) - the keys from the files are leaves. need to figure out the relationship of the source file # to it's leaf: take an example: N=8 root=tree[1] / \ tree[2] tree[3] / \ / \ tree[4] tree[5] tree[6] tree[7] / \ / \ / \ / \ LEAVES: tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] tree[15] 8=N+0 9=N+1 10=N+2 11=N+3 12=N+4 13=N+5 14=N+6 15=N+7 file 0 file 1 file 2 file 3 file 4 file 5 file 6 file 7 so the index of the leaf where the value of a file belongs from is = N + file # and the size of the tree is 16, which is 2(N+1) pseudo-code //variables and structures struct TreeNode { long int key; //value from the file int source //index # of file it came from }; TreeNode tree[(2*(N+1))]; TreeNode TOMBSTONE; FileType file[N]; FileType final; //the output file pointer int depth=logToTheBase2(N); int src; main { open_All_Files(); initialize_Tree(); while ( not (eof_of_file_on_all_files) ) { write_Root(); replace_Leaf(); run_Tournament(); } } //end main //------------------------------------------------------------------------------------ initialize_Tree() { for (int i=0; i< N ; i++) { tree[N+i].key=file[i].readNext(); // readNext() will refill that file's input //buffer as necessary. tree[N+i].source=i; //assign the key the file's index it belongs to } run_First_Tournament(); } //end initialize_Tree() //------------------------------------------------------------------------------------ run_First_Tournament() { int winner; //used to keep track of index of the winner //from the bottom up, breadth first, in pairs of files for (int d=depth; d>0 ; d--) { //go level by level for (pair= 2ToThePowerOf(d); pair < (2ToThePowerOf(d+1))-1; pair+=2) { //left to right in pairs if ( tree[pair].key > tree[pair+1]) winner=pair; else winner=pair+1; tree[winner/2]=tree[winner]; //copy the TreeNode values of the winner up //to the next level } } }//end run_First_Tournament() //------------------------------------------------------------------------------------ write_Root() { final.write(tree[0]).key); } //------------------------------------------------------------------------------------ replace_Leaf() { src=tree[0].source; //the index of the file that the last winner came from tree[N+src].key=file[src].readNext(); //remember that the source value is unchanged if (file[src].eof() == true) tree[src].key = TOMBSTONE; } //------------------------------------------------------------------------------------ run_Tournament() { //start at leaf int current=N + src; //to get the index into tree int winner; // index of the winner of a tournament int sibling; //index of the sibling of current for (int i =0; i< depth; i++) { //do 1 comparaison per level, we only need to compare the key we just replaced //with it's sibling /figure out the index of it's sibling if (current mod 2 ==0) //even, it's a left sibling sibling=current+1; else sibling=current-1; //odd, it's a right sibling parent=current/2; //compare if (tree[current].key < tree[sibling].key) winner=current; else winner = sibling; tree[parent]=tree[winner]; //move the winner up the tree current = parent; //move up to the next level } } //------------------------------------------------------------------------------------