Handout #61 CS106A Summer 2002 August 7,2002 Alex Khomenko Practice Final Note:this practice exam is the actual exam from Autumn 01.A second practice exam is available in electronic form from the class website.We have removed some of the blank space for ans wers in order to save some trees.Solutions to both practice exams will be distributed in electronic form some time next week. Exam Instructions Answer each of the five questions included in the exam.Write all of your answers directly on the examination paper,including any work that you wish to be considered for partial credit. The examination is open-book,and you may make use of the text,handouts,or course notes.You may use any functions developed in the text or the handouts and need not rewrite the code;simply cite in a comment the function name,the source,and the page number.You may not use a computer of any kind. On header files:Don't worry about putting the necessary #include statements in your solutions.Just assume the required strlib,genlib,etc.header files are visible to you. On commenting:Comments regarding implementation are not required on the exam. Uncommented code that gets the job done will be sufficient for full credit on the problem.On the other hand,comments may help you receive partial credit on a problem if they help us determine what you were trying to do,even if your code is wrong. On style:We will not require you to adhere to the strictest principles of good style for this exam, but a reasonable decomposition is expected. On time:You will have three hours to complete this exam.Budget your time and try to leave some time at the end to go over your work.If you run out of time on a problem,an English language "pseudocode"version may earn you partial credit. On function prototypes.You need not include function prototypes on any of the problems. I accept the letter and spirit of the honor code-I have not given or received aid on this exam. Name(signed) Score Grader 1.Strings (15) 2.Arrays (20) 3.Function Trace (15) 4.Useful Pointers (20) 5.Data Structures (30)
Handout #61 Summer 2002 August 7, 2002 Alex Khomenko Practice Final Note: this practice exam is the actual exam from Autumn 01. A second practice exam is available in electronic form from the class website. We have removed some of the blank space for answers in order to save some trees. Solutions to both practice exams will be distributed in electronic form some time next week. Exam Instructions Answer each of the five questions included in the exam. Write all of your answers directly on the examination paper, including any work that you wish to be considered for partial credit. The examination is open-book, and you may make use of the text, handouts, or course notes. You may use any functions developed in the text or the handouts and need not rewrite the code; simply cite in a comment the function name, the source, and the page number. You may not use a computer of any kind. On header files: Don't worry about putting the necessary #include statements in your solutions. Just assume the required strlib, genlib, etc. header files are visible to you. On commenting: Comments regarding implementation are not required on the exam. Uncommented code that gets the job done will be sufficient for full credit on the problem. On the other hand, comments may help you receive partial credit on a problem if they help us determine what you were trying to do, even if your code is wrong. On style: We will not require you to adhere to the strictest principles of good style for this exam, but a reasonable decomposition is expected. On time: You will have three hours to complete this exam. Budget your time and try to leave some time at the end to go over your work. If you run out of time on a problem, an English language "pseudocode" version may earn you partial credit. On function prototypes. You need not include function prototypes on any of the problems. I accept the letter and spirit of the honor code— I have not given or received aid on this exam. Name (signed) __________________________________________________________ Score Grader 1. Strings (15) ______ ______ 2. Arrays (20) ______ ______ 3. Function Trace (15) ______ ______ 4. Useful Pointers (20) ______ ______ 5. Data Structures (30) ______ ______ CS106A
-2- Total (100)
– 2 – Total (100) ______
-3- Problem 1:Strings(15 points) Te ANSI C library string.h exports lots of interesting functions.To create the library,someone had to implement those functions in C.In this problem,you will play the role of implementor for the following two string.h functions: /* Function:strcspn Usage:prefixLength strcspn(strl,str2); This function returns the length of the prefix of strl consisting of characters not in str2. Examples: strcspn("CS106A","0123456789")returns 2,since the first 2 ★ characters of the first argument are not in the second. strcspn("CS106A","ABCDE")returns 0,since the first character of the first argument is in the second strcspn ("CS106A","+-*/")returns 6 strcspn("CS106A","returns 6 ★ strcspn("","ABC")returns 0 strcspn("",""returns 0 It is assumed that the arguments are valid strings and in particular, that neither argument is NULL.You do not have to test for this. ★/ /贵 Function:strpbrk Usage:ptr strpbrk(strl,str2); This function returns a pointer to the first character of strl that is in str2.It returns NULL if no characters of strl are in str2. Examples: strpbrk("CS106A","0123456789") returns a pointer to the '1'in str1. strpbrk("CS106A","ABCDE")returns pointer to 'c'in WCS106A" strpbrk ("CS106A",+*/")returns NULL strpbrk("CS106A",""returns NULL strpbrk("","ABC")returns NULL strpbrk (""""returns NULL It is assumed that the arguments are valid strings and in particular, that neither argument is NULL.You do not have to test for this. */ These two functions are related in an interesting way.If you have an implementation of one function, then you can use that to help implement the other. Your job in this problem is to implement one of the functions,then use that function to implement the other one.Here are the ground rules: ?Choose either function and implement it.You may use ordinary character manipulation via array or pointer notation,and any function in string.h except strpbrk and strespn. You may not use functions from strlib.h
– 3 – Problem 1: Strings (15 points) Te ANSI C library string.h exports lots of interesting functions. To create the library, someone had to implement those functions in C. In this problem, you will play the role of implementor for the following two string.h functions: /* * Function: strcspn * Usage: prefixLength = strcspn(str1, str2); * ------------------------------------------ * This function returns the length of the prefix of str1 consisting of * characters not in str2. * Examples: * strcspn("CS106A", "0123456789") returns 2, since the first 2 * characters of the first argument are not in the second. * strcspn("CS106A", "ABCDE") returns 0, since the first character of * the first argument is in the second * strcspn("CS106A", "+-*/") returns 6 * strcspn("CS106A", "") returns 6 * strcspn("", "ABC") returns 0 * strcspn("", "") returns 0 * It is assumed that the arguments are valid strings and in particular, * that neither argument is NULL. You do not have to test for this. */ /* * Function: strpbrk * Usage: ptr = strpbrk(str1, str2); * --------------------------------- * This function returns a pointer to the first character of str1 that * is in str2. It returns NULL if no characters of str1 are in str2. * Examples: * strpbrk("CS106A", "0123456789") * returns a pointer to the '1' in str1. * strpbrk("CS106A", "ABCDE") returns pointer to ‘C’ in “CS106A” * strpbrk("CS106A", "+_*/") returns NULL * strpbrk("CS106A", "") returns NULL * strpbrk("", "ABC") returns NULL * strpbrk("", "") returns NULL * It is assumed that the arguments are valid strings and in particular, * that neither argument is NULL. You do not have to test for this. */ These two functions are related in an interesting way. If you have an implementation of one function, then you can use that to help implement the other. Your job in this problem is to implement one of the functions, then use that function to implement the other one. Here are the ground rules: ?? Choose either function and implement it. You may use ordinary character manipulation via array or pointer notation, and any function in string.h except strpbrk and strcspn. You may not use functions from strlib.h
-4- ?Next implement the other function,using the first one that you implemented,but otherwise following the same rules.Note:the difficulty is the same regardless of the one you choose to do first.You must use one to implement the other in order to get full credit. Write your first function here: Write your second function here(or on the next page)
– 4 – ?? Next implement the other function, using the first one that you implemented, but otherwise following the same rules. Note: the difficulty is the same regardless of the one you choose to do first. You must use one to implement the other in order to get full credit. Write your first function here: Write your second function here (or on the next page)
-5- Problem 2:Arrays(20 points) Note:once you understand this problem,the coding is fairly simple and not long.The best strategy is to read the whole thing for understanding,without thinking about code.Then write the code when you are ready. In this problem you will program a simple"neural net".Neural nets are programs that simulate the operation of some of the circuits in the brain,and large complicated nets can learn over time to do tasks like recognize handwriting or select stocks. We won't be able to delve into anything that complicated here on the exam.But the simple system we will show you will give you the idea,while it tests your skill with arrays. The kind of system we are concerned with is called a perceptron,and we could diagram one like this: Stimulus units Association units Response units (S-units) (A-units) (R-units) Weighted A-to-R connections The job of a perceptron is to take in a"stimulus"and classify it.For example,the stimulus might be a representation of a handwritten character,and the classification might be the identification of what letter it is.In the diagram above,the stimulus comes in at the left in the "S-units",and the classification is made at the right,in the"R-units".Here is how it works. The S-units are just an array of ints,and they will have values that are 1 or 0.For some perceptrons,the S-units form a rectangular pattern and could be thought of as simulating a retina,but we will just use a one-dimensional array
– 5 – Problem 2: Arrays (20 points) Note: once you understand this problem, the coding is fairly simple and not long. The best strategy is to read the whole thing for understanding, without thinking about code. Then write the code when you are ready. In this problem you will program a simple "neural net". Neural nets are programs that simulate the operation of some of the circuits in the brain, and large complicated nets can learn over time to do tasks like recognize handwriting or select stocks. We won’t be able to delve into anything that complicated here on the exam. But the simple system we will show you will give you the idea, while it tests your skill with arrays. The kind of system we are concerned with is called a perceptron, and we could diagram one like this: The job of a perceptron is to take in a "stimulus" and classify it. For example, the stimulus might be a representation of a handwritten character, and the classification might be the identification of what letter it is. In the diagram above, the stimulus comes in at the left in the "S-units", and the classification is made at the right, in the "R-units". Here is how it works. The S-units are just an array of ints, and they will have values that are 1 or 0. For some perceptrons, the S-units form a rectangular pattern and could be thought of as simulating a retina, but we will just use a one-dimensional array. . . . Stimulus units Association units Response units (S-units) (A-units) (R-units) Weighted A-to-R connections
-6- Each S-unit is connected to some of the A-units(the A-units are the triangles in the diagram above). Here we show A-units connecting to two R-units,but that is just a feature of the way this particular perceptron is "wired".(Not all of the connections are shown,to reduce clutter in the diagram.)As mentioned above,the stimulus is a pattern of I's and 0's in the S-units,and the S-units that have ones in them are said to "fire"into the A-units that they are connected to.That means that the I's are sent from the S-units to the A-units they connect to. The A-units are"threshold"devices.They sum their inputs,and each A-unit whose sum is greater than or equal to a threshold fires into the R-units it connects to So one stimulus might cause some A- units to fire,and another stimulus might cause other A-units to fire.The value transmitted to the connected R-units is the sum times a"weight",and each A-to-R connection has a separate weight. Now we are ready to classify the stimulus.The R-units sum their inputs,and if,say,R-unit 2 has the highest value,then we classify the input as being an example of pattern 2. That's it.To recap: ?The stimulus causes some S-units to fire into A-units. ?A-units whose input exceeds a threshold fire through weighted connections into the R-units. The threshold is the same for all A-units. ?The R-unit with the biggest sum indicates the classification of the stimulus. To program a perceptron,we just need a bunch of arrays to hold the stimulus,connections,and weights.Since this is the array question,we should be ready to go!First we will define some constants that tell us the size of the perceptron and a few other things: #define N SUNITS 16 #define N AUNITS 16 #define N RUNITS #define N S TO A 6 #define N A TO R #define THRESHOLD 4 This perceptron has 16 S-units,16 A-units,and 4 R-units.Each S-unit connects to 6 A-units,and each A-unit connects to 4 R-units.The threshold for A-unit firing is 4.(Note that all this doesn't exactly match the diagram-as mentioned,we didn't want to clutter it with too many lines.) Next we need to store the S-to-A connections.Since each of the 16 S-units connects to 6 A-units, the perfect data structure is a 16 x 6 array,which we will call sA:
– 6 – Each S-unit is connected to some of the A-units (the A-units are the triangles in the diagram above). Here we show A-units connecting to two R-units, but that is just a feature of the way this particular perceptron is "wired". (Not all of the connections are shown, to reduce clutter in the diagram.) As mentioned above, the stimulus is a pattern of 1's and 0's in the S-units, and the S-units that have ones in them are said to "fire" into the A-units that they are connected to. That means that the 1's are sent from the S-units to the A-units they connect to. The A-units are "threshold" devices. They sum their inputs, and each A-unit whose sum is greater than or equal to a threshold fires into the R-units it connects to So one stimulus might cause some Aunits to fire, and another stimulus might cause other A-units to fire. The value transmitted to the connected R-units is the sum times a "weight", and each A-to-R connection has a separate weight. Now we are ready to classify the stimulus. The R-units sum their inputs, and if, say, R-unit 2 has the highest value, then we classify the input as being an example of pattern 2. That's it. To recap: ?? The stimulus causes some S-units to fire into A-units. ?? A-units whose input exceeds a threshold fire through weighted connections into the R-units. The threshold is the same for all A-units. ?? The R-unit with the biggest sum indicates the classification of the stimulus. To program a perceptron, we just need a bunch of arrays to hold the stimulus, connections, and weights. Since this is the array question, we should be ready to go! First we will define some constants that tell us the size of the perceptron and a few other things: #define N_SUNITS 16 #define N_AUNITS 16 #define N_RUNITS 4 #define N_S_TO_A 6 #define N_A_TO_R 4 #define THRESHOLD 4 This perceptron has 16 S-units, 16 A-units, and 4 R-units. Each S-unit connects to 6 A-units, and each A-unit connects to 4 R-units. The threshold for A-unit firing is 4. (Note that all this doesn’t exactly match the diagram—as mentioned, we didn’t want to clutter it with too many lines.) Next we need to store the S-to-A connections. Since each of the 16 S-units connects to 6 A-units, the perfect data structure is a 16 x 6 array, which we will call sA: sA
-7- Let's look at the values that might be stored on one row of this table,for example,row 5: 0 y ny 3 4 5 row 5 3 个 8 11 14 The value at sa[5][2]is 8,which tells us that S-unit 5 connects to A-unit 8.Taken as a whole,this row tells us that S-unit 5 connects to A-units 3,7,8,11,14,and 15.Clearly with a table like this we can specify all of the S-to-A connections. Now we just need another table to specify the connection from the A-units to the R-units.Since these are weighted connections,we will take a slightly different approach.We will use another table, called aR that has as many columns as there are R-units(4 in our case).aR[i]]is the weight of the connection from A-unit i to R-unit j.This table will be 16 x 4 in size,and a row might look like this (the data type is double): 0 2 row 10 1.20.80.0 1.4 Suppose the sum of the inputs to A-unit 10 is x,and x>=THRESHOLD.Then A-unit 10 sends a value of 1.2 x to R-unit 0,0.8 x to R-unit 1,0.o to R-unit 2 (the weight is zero),and 1.4* x to R-unit 3.Note:the weights are allowed to be negative. The processing at the R-units is easy:we just find the one with the largest total,and resolve ties any way we want to. Here is the declaration of the tables and some arrays you will need: int sAIN SUNITS][N S TO A]; double aR[N AUNITS][N RUNITS]; int s[N SUNITS]; int a[N AUNITS]; double r[N RUNITS]; The first two lines declare the connection tables,as described above.The array s is the stimulus, and the arrays a and give you a place to accumulate the sums for the A-units and R-units.Your job is to write three functions that simulate the operation of the perceptron: void FiresToA(int s[],int sA[][N_S_TO A],int a[]); void FireAToR(int a[],double aR[][N RUNITS],double r[]); int classifyPattern(double r[]);
– 7 – Let’s look at the values that might be stored on one row of this table, for example, row 5: The value at sA[5][2] is 8, which tells us that S-unit 5 connects to A-unit 8. Taken as a whole, this row tells us that S-unit 5 connects to A-units 3, 7, 8, 11, 14, and 15. Clearly with a table like this we can specify all of the S-to-A connections. Now we just need another table to specify the connection from the A-units to the R-units. Since these are weighted connections, we will take a slightly different approach. We will use another table, called aR that has as many columns as there are R-units (4 in our case). aR[i][j] is the weight of the connection from A-unit i to R-unit j. This table will be 16 x 4 in size, and a row might look like this (the data type is double): Suppose the sum of the inputs to A-unit 10 is x, and x >= THRESHOLD. Then A-unit 10 sends a value of 1.2 * x to R-unit 0, 0.8 * x to R-unit 1, 0.0 to R-unit 2 (the weight is zero), and 1.4 * x to R-unit 3. Note: the weights are allowed to be negative. The processing at the R-units is easy: we just find the one with the largest total, and resolve ties any way we want to. Here is the declaration of the tables and some arrays you will need: int sA[N_SUNITS][N_S_TO_A]; double aR[N_AUNITS][N_RUNITS]; int s[N_SUNITS]; int a[N_AUNITS]; double r[N_RUNITS]; The first two lines declare the connection tables, as described above. The array s is the stimulus, and the arrays a and r give you a place to accumulate the sums for the A-units and R-units. Your job is to write three functions that simulate the operation of the perceptron: void FireSToA(int s[], int sA[][N_S_TO_A], int a[]); void FireAToR(int a[], double aR[][N_RUNITS], double r[]); int ClassifyPattern(double r[]); 3 7 8 11 14 15 row 5 0 1 2 3 4 5 row 10 1.2 0.8 0.0 1.4 0 1 2 3
-8- The first function uses the stimulus s and sa to produce sums in a.The second function uses a and aR to produce weighted sums in r.The third function returns the index of the element ofr with the highest value.You may assume that a and have been initialized to zero. Write your answers on the next page.(By the way,there is an algorithm for adjusting the weights in aR to train the perceptron to recognize a known set of patterns correctly.That's a story for another exam...) void FiresToA(int s[],int sA[][N_S_TO_A],int a[]) void FireAToR(int a[],double aR[][N_RUNITS],double r[]) int ClassifyPattern(double r[])
– 8 – The first function uses the stimulus s and sA to produce sums in a. The second function uses a and aR to produce weighted sums in r. The third function returns the index of the element of r with the highest value. You may assume that a and r have been initialized to zero. Write your answers on the next page. (By the way, there is an algorithm for adjusting the weights in aR to train the perceptron to recognize a known set of patterns correctly. That's a story for another exam...) void FireSToA(int s[], int sA[][N_S_TO_A], int a[]) void FireAToR(int a[], double aR[][N_RUNITS], double r[]) int ClassifyPattern(double r[])
-9-
– 9 –
-10- Problem 3:Function Trace (15 points) Draw the state of memory at the point indicated.Be sure to indicate clearly the Stack and Heap. Also,clearly label any orphaned memory,and draw an'X'through any stack frames that are no longer active.You do not have to draw the Data Segment(where string constants are stored). #include "genlib.h" #include "strlib.h" void Endive(int ***joann,int **simca,int *lydia,int *charlie,char **delia); void Chevril(char **nigella); main() string julia; int jacques; int **martin; julia Copystring("hi"); jacques 3; martin GetBlock(jacques sizeof(int *)) martin[0]GetBlock(jacques sizeof(int)); Endive(&martin,martin,*martin,&jacques,&julia); void Endive(int **joann,int **simca,int *lydia,int *charlie,char *delia) int i; for (i=0;i<*charlie;i++) if(i号3==2) *(simca i)=GetBlock(sizeof(int)); else *lydia++*charlie i; *(*joann)[2]=***joann 2; Chevril(delia); DRAW THE STATE OF MEMORY HERE void Chevril(char **nigella) *nigella Concat(*nigella,"there"); Write your answer on the next page
– 10 – Problem 3: Function Trace (15 points) Draw the state of memory at the point indicated. Be sure to indicate clearly the Stack and Heap. Also, clearly label any orphaned memory, and draw an 'X' through any stack frames that are no longer active. You do not have to draw the Data Segment (where string constants are stored). #include "genlib.h" #include "strlib.h" void Endive(int ***joann, int **simca, int *lydia, int *charlie, char **delia); void Chevril(char **nigella); main() { string julia; int jacques; int **martin; julia = CopyString("hi"); jacques = 3; martin = GetBlock(jacques * sizeof(int *)); martin[0] = GetBlock(jacques * sizeof(int)); Endive(&martin, martin, *martin, &jacques, &julia); } void Endive(int ***joann, int **simca, int *lydia, int *charlie, char **delia) { int i; for (i = 0; i < *charlie; i++) { if (i % 3 == 2) *(simca + i) = GetBlock(sizeof(int)); else *lydia++ = *charlie – i; } *(*joann)[2] = ***joann + 2; Chevril(delia); DRAW THE STATE OF MEMORY HERE } void Chevril(char **nigella) { *nigella = Concat(*nigella, "there"); } Write your answer on the next page