Andrew login ID:Full Name:CS 15-213, Fall 2001Exam 2November 13, 2001Instructions:• Make sure that your exam is not missing any sheets, then write your full name and Andrew login IDon the front.• Write your answers in the space provided below the problem. If you make a mess, clearly indicateyour 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 easypoints 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, butno 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 15The following two problems concern the performance of two procedures that generate a data structuredescribing the population statistics for a set of data values. That is, suppose we had a set of integer datavalues x1, x2, . . . xn, having minimum value xminand maximum value xmax. For each possible value of xbetween xminand 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 xmincan be an arbitrary integer, we explicitly storethe value of xminin this structure, and use an array p of size m = xmax− xmin+ 1. Population valuePxis then stored as array value p[x-xmin]. For example, for data set [−1, 1, 2, −1, −1], we would havexmin= −1, and m = 2 − −1 + 1 = 4. The array p, would represent this population as follows:Population values P−1P0P1P2Array Elements p[0] p[1] p[2] p[3]Values 3 0 1 1Here is some utility code for finding the values of xminand xmax. We have instrumented the code with acounter 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 15Here are two versions of a function to generate population statistics. The first calls functions min_val andmax_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); // MIN1result->m = (max_val(a, n) // MAX1- min_val(a, n) + 1); // MIN2result->p = (int*) malloc(result->m*sizeof(int));/*Set population entries to zero*/for (i = min_val(a,n); // MIN3i <= max_val(a,n); i++) // MAX2result->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)]++; // MIN5return 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); // MIN1int max = max_val(a,n); // MAX1result->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 15Problem 1. (13 points):The comments on the right of the code for build_pop1 indicate the places where functions min_valand 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 atthese different points in the program. Express your entries as formulas in terms of m and n. The finalentry should show the total number of calls to min_val and max_val.Call Point Times CalledMIN1MAX1MIN2MIN3MAX2MIN4MIN5TotalB. The counter comp_cnt counts the total number of comparisons made between data values. Howmany comparisons are made during a single call to min_val or max_val? Express your answer asa 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 valueof comp_cnt? Express your answer as a formula in terms of m and n.Page 4 of 15Problem 2. (6 points):Now let us compare the overall performance of build_pop1 to that of build_pop2, which avoidsrepeated 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 beformulas in big-O notation in terms of n, e.g., O(n3). Your answer will be marked incorrect if you do notsimplify 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 ofthe operations performed by the two functions, as well.Scenario build pop1 build pop2DenseMatchedSparsePage 5 of 15Problem 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 CacheIndex Tag Valid Byte 0 Byte 1 Tag Valid Byte 0 Byte 1 Tag Valid Byte 0 Byte 1 Tag Valid Byte 0 Byte 10 29 0 34 29 87 0 39 AE 7D 1 68 F2 8B 1 64 381 F3 1 0D 8F 3D 1 0C 3A 4A 1 A4 DB D9 1 A5 3C2 A7 1 E2 04 AB 1 D2 04 E3 0 3C A4 01 0 EE 053 3B 0 AC 1F E0 0 B5 70 3B 1 66 95 37 1 49 F34 80 1 60 35 2B 0 19 57 49 1 8D 0E 00 0 70 AB5 EA 1 B4 17 CC 1 67 DB 8A 0 DE AA 18 1 2C D36 1C 0 3F A4 01 0 3A C1 F0 0 20 13 7F 1 DF 057 0F 0 00 FF AF 1 B1 5F 99 0 AC 96 3A 1 22 79Part 1The box below shows the format of a physical address. Indicate (by labeling the diagram) the fields thatwould be used to
View Full Document
Unlocking...