Andrew login ID Full Name CS 15 213 Fall 2001 Exam 2 November 13 2001 Instructions Make sure that your exam is not missing any sheets then write your full name and Andrew login ID on the front Write your answers in the space provided below the problem If you make a mess clearly indicate your final answer The exam has a maximum score of 64 points The problems are of varying difficulty The point value of each problem is indicated Pile up the easy points quickly and then come back to the harder problems This exam is OPEN BOOK You may use any books or notes you like You may use a calculator but no laptops or other wireless devices Good luck 1 13 2 06 3 05 4 08 5 08 6 10 7 04 8 10 TOTAL 64 Page 1 of 15 The following two problems concern the performance of two procedures that generate a data structure describing the population statistics for a set of data values That is suppose we had a set of integer data values x1 x2 xn having minimum value xmin and maximum value xmax For each possible value of x between xmin and xmax we want to record Px defined to be the number of values of i such that x xi We will record this information in a data structure of type pop ele declared as follows typedef struct int m int xmin int p pop ele pop ptr Since C arrays have minimum index 0 and the value of xmin can be an arbitrary integer we explicitly store the value of xmin in this structure and use an array p of size m xmax xmin 1 Population value Px is then stored as array value p x xmin For example for data set 1 1 2 1 1 we would have xmin 1 and m 2 1 1 4 The array p would represent this population as follows Population values Array Elements Values P 1 p 0 3 P0 p 1 0 P1 p 2 1 P2 p 3 1 Here is some utility code for finding the values of xmin and xmax We have instrumented the code with a counter to determine the total number of comparisons peformed between data values comp cnt Find minimum value in array a int min val int a int n int i int result a 0 for i 1 i n i result result a i a i result comp cnt return result Find maximum value in array a int max val int a int n int i int result a 0 for i 1 i n i result result a i a i result comp cnt return result Page 2 of 15 Here are two versions of a function to generate population statistics The first calls functions min val and max val repeatedly First version of population counting routine pop ptr build pop1 int a int n int i pop ptr result pop ptr malloc sizeof pop ele result xmin min val a n MIN1 result m max val a n MAX1 min val a n 1 MIN2 result p int malloc result m sizeof int Set population entries to zero for i min val a n MIN3 i max val a n i MAX2 result p i min val a n 0 MIN4 Now update the population entries for i 0 i n i result p a i min val a n MIN5 return result The second only calls each of these functions once storing the result in a termporary pop ptr build pop2 int a int n int i pop ptr result pop ptr malloc sizeof pop ele int min min val a n MIN1 int max max val a n MAX1 result xmin min result m max min 1 result p int malloc result m sizeof int Set population entries to zero for i min i max i result p i min 0 Now update the population entries for i 0 i n i result p a i min return result Page 3 of 15 Problem 1 13 points The comments on the right of the code for build pop1 indicate the places where functions min val and max val are called Suppose that m is defined to be the number of entries in the population array That is m xmax xmin 1 As before n denotes the size of the data set A Fill in the following table to indicate the total number of calls to min val and max val made at these different points in the program Express your entries as formulas in terms of m and n The final entry should show the total number of calls to min val and max val Call Point Times Called MIN1 MAX1 MIN2 MIN3 MAX2 MIN4 MIN5 Total B The counter comp cnt counts the total number of comparisons made between data values How many comparisons are made during a single call to min val or max val Express your answer as a formula in terms of m and n C If we start with comp cnt equal to 0 and call function build pop1 what will be the final value of comp cnt Express your answer as a formula in terms of m and n Page 4 of 15 Problem 2 6 points Now let us compare the overall performance of build pop1 to that of build pop2 which avoids repeated calls to min val and max val Consider the following scenarios for the relation between m and n Dense m n i e there are many repeated values Matched m n i e the range of values is about the same as the number of values Sparse m n2 i e the range is much larger than the number of values Fill in the following table giving the asymptotic complexities of the two functions Your answers should be formulas in big O notation in terms of n e g O n3 Your answer will be marked incorrect if you do not simplify the formula For example you should write O n2 instead of O 2n2 3n 1 Your analysis should consider not just the effort expended in calling min val and max val but all of the operations performed by the two functions as well Scenario build pop1 Dense Matched Sparse Page 5 of 15 build pop2 Problem 3 5 points The following problem concerns basic cache lookups The memory is byte addressable Memory accesses are to 1 byte words not 4 byte words Physical addresses are 12 bits wide The cache is 4 way set associative with a 2 byte block size and 32 total lines In the following tables all numbers are given in hexadecimal The contents of the cache are as follows 4 way Set Associative Cache Tag Valid Byte 0 Byte 1 Tag Valid Byte 0 Byte 1 87 0 39 AE 7D 1 68 F2 3D 1 0C 3A 4A 1 A4 DB AB 1 D2 04 E3 0 3C A4 E0 0 B5 70 3B 1 66 95 2B 0 19 57 49 1 8D 0E CC 1 67 DB …
View Full Document
Unlocking...