Handout #36 CS106A 2002 Dec.30,2002 Alex Khomenko Practice Final Note:this practice exam is the actual exam from Autumn 00 at Stanford.Solutions to it will be distributed in electronic form as handout #37. 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 (15) 3.Function Trace (20) 4.Useful Pointers (20) 5.Data Structures (30) Total (100)
Handout #36 2002 Dec.30, 2002 Alex Khomenko Practice Final Note: this practice exam is the actual exam from Autumn 00 at Stanford. Solutions to it will be distributed in electronic form as handout #37. 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 (15) ______ ______ 3. Function Trace (20) ______ ______ 4. Useful Pointers (20) ______ ______ 5. Data Structures (30) ______ ______ Total (100) ______ CS106A
-2- Problem 1:Strings-strtok is your friend!(15 points) Function strtok is a function defined in string.h.It divides string into tokens by inserts\0' characters into the input string to turn it into several small strings instead of one large one.In this problem,you will implement a simplified version of this function.Here is the prototype: char *strtok(char *str,char delim); The first argument to the function is the string to be divided into tokens.The second argument is the character that serves as the delimiter between tokens.For example,we might make the call strtok ("Don't you love finals week?",') The second argument,which in this call is the space character,serves as the delimiter (i.e.,boundary) between the tokens. The function is supposed to retum the tokens to its caller.Since there can be lots of tokens in the string,the designers of C decided on the following scheme.When you call strtok as shown above, the first token is created by replacing the first occurrence of the delimiter with a'\o',and a pointer to the token is returned.The function also maintains an internal state (yes,you can use a global variable for this)that holds information about how far the search has proceeded. To get the next token,you then call the function with first argument NuLL,like this: strtok (NULL,'') This causes it to replace the next delimiter with'\o',return a pointer to the next token,and update its internal state.This process can be repeated to get the rest of the tokens,including the one that was the end of the original string.When there are no more tokens,the function returns NuLL. To be sure you understand how this works,consider the following code: token strtok (str,'); printf("号s\n",token)； while ((token strtok (NULL,''))!NULL) printf("&s\n",token); If str is the string "Don't you love finals week?",this code prints the following: Don't you love finals week? Originally the memory pointed to by str looked like this:
– 2 – Problem 1: Strings – strtok is your friend! (15 points) Function strtok is a function defined in string.h. It divides string into tokens by inserts '\0' characters into the input string to turn it into several small strings instead of one large one. In this problem, you will implement a simplified version of this function. Here is the prototype: char *strtok(char *str, char delim); The first argument to the function is the string to be divided into tokens. The second argument is the character that serves as the delimiter between tokens. For example, we might make the call strtok("Don't you love finals week?", ' ') The second argument, which in this call is the space character, serves as the delimiter (i.e., boundary) between the tokens. The function is supposed to return the tokens to its caller. Since there can be lots of tokens in the string, the designers of C decided on the following scheme. When you call strtok as shown above, the first token is created by replacing the first occurrence of the delimiter with a '\0', and a pointer to the token is returned. The function also maintains an internal state (yes, you can use a global variable for this) that holds information about how far the search has proceeded. To get the next token, you then call the function with first argument NULL, like this: strtok(NULL, ' '); This causes it to replace the next delimiter with '\0', return a pointer to the next token, and update its internal state. This process can be repeated to get the rest of the tokens, including the one that was the end of the original string. When there are no more tokens, the function returns NULL. To be sure you understand how this works, consider the following code: token = strtok(str, ' '); printf("%s\n", token); while ((token = strtok(NULL, ' ')) != NULL) printf("%s\n", token); If str is the string "Don't you love finals week?", this code prints the following: Don't you love finals week? Originally the memory pointed to by str looked like this:
-3- Don't you love finals week?\0 and now it looks like this: Don't\Oyou\0love\ofinals\Oweek?\0 The calls of strtok have mutilated the original string,and returned pointers to the tokens thus created.Note:the\o'characters are inserted as needed.It is not the case that the first call goes through and puts them all in the string Your job is to implement strtok as described above.Here are some ground rules(the real strtok is a little more general): ?You cannot use strlib.h functions on this problem. ?The first argument in the initial call is a pointer to a valid string. ?If the first argument is the empty string,the function returns NULL. ?The string neither starts nor ends with the delimiter. ?There are never two consecutive delimiters in the string ?If no delimiters are present in the first argument,the initial call returns the first argument and the next call returns NULL. ?You are allowed only one global variable,whose declaration you can write just above the code for the function: char *strtok(char *str,char delim)
– 3 – Don't you love finals week?\0 and now it looks like this: Don't\0you\0love\0finals\0week?\0 The calls of strtok have mutilated the original string, and returned pointers to the tokens thus created. Note: the '\0' characters are inserted as needed. It is not the case that the first call goes through and puts them all in the string. Your job is to implement strtok as described above. Here are some ground rules (the real strtok is a little more general): ?? You cannot use strlib.h functions on this problem. ?? The first argument in the initial call is a pointer to a valid string. ?? If the first argument is the empty string, the function returns NULL. ?? The string neither starts nor ends with the delimiter. ?? There are never two consecutive delimiters in the string. ?? If no delimiters are present in the first argument, the initial call returns the first argument and the next call returns NULL. ?? You are allowed only one global variable, whose declaration you can write just above the code for the function: char *strtok(char *str, char delim) {
-4- More space for the answer to Problem 1
– 4 – More space for the answer to Problem 1
-5- Problem 2:Arrays(15 points) This problem involves a simple method for identifying images.Suppose,for example,you were working on a videoconferencing system,and that you would like to automatically display the name of the person who is on camera.You could take a picture of each participant in the meeting in advance,so all you would need is some software to find the best match of those known images with the picture of the person who is on camera. Image recognition is,in general,a difficult task.But in the situation described,you are probably dealing with a small number of participants,and we are going to suggest a simple scheme that would probably work quite well. First let's say what an image is.For our purposes,we will assume that the result of digitizing an image is a two-dimensional array with sIze rows and sIze columns,where sIze is a #defined constant.We will call the images that we collect in advance our"known"data set,and we will assume that there are N_pIcrs images.Thus we could hold the known data in a three dimensional array declared as follows: int knownData[N PICTS][SIZE][SIZE]; As a refresher on three dimensional arrays,what this declaration says is that knownData is an array ofN pIcrs elements,each of which is a sIze x sIze two dimensional array.To put it another way,if i is an integer in the range o to N pIcrs -1,then knownData[i]is a two dimensional array that can be used anywhere such an array is expected. We also have to describe the two dimensional data that makes up the pictures.We will assume that our digitization process produces a color image,and that there are N coLoRs possible colors.Each picture is thus an array of sIze rows and sIze columns of integers in the range o to N coLoRs 1. Now we can discuss the matching process we will use.Our technique is based on the notion of a color histogram,which is just a tally of how many times each color appears in an image.Here is an example,assuming for simplicity that the images are 4 x 4 arrays and that there are 10 possible colors: Image Histogram 2 4 4 1 3 4 1 3 6 4 0312521200 5 5 7 0123456789 The histogram values are in the boxes,and the color numbers are written in below for reference. Thus the histogram tells us that color 1 appears 3 times in the image,color 4 appears 5 times,and that color 8 doesn't appear at all
– 5 – Problem 2: Arrays (15 points) This problem involves a simple method for identifying images. Suppose, for example, you were working on a videoconferencing system, and that you would like to automatically display the name of the person who is on camera. You could take a picture of each participant in the meeting in advance, so all you would need is some software to find the best match of those known images with the picture of the person who is on camera. Image recognition is, in general, a difficult task. But in the situation described, you are probably dealing with a small number of participants, and we are going to suggest a simple scheme that would probably work quite well. First let's say what an image is. For our purposes, we will assume that the result of digitizing an image is a two-dimensional array with SIZE rows and SIZE columns, where SIZE is a #defined constant. We will call the images that we collect in advance our "known" data set, and we will assume that there are N_PICTS images. Thus we could hold the known data in a three dimensional array declared as follows: int knownData[N_PICTS][SIZE][SIZE]; As a refresher on three dimensional arrays, what this declaration says is that knownData is an array of N_PICTS elements, each of which is a SIZE x SIZE two dimensional array. To put it another way, if i is an integer in the range 0 to N_PICTS – 1 , then knownData[i] is a two dimensional array that can be used anywhere such an array is expected. We also have to describe the two dimensional data that makes up the pictures. We will assume that our digitization process produces a color image, and that there are N_COLORS possible colors. Each picture is thus an array of SIZE rows and SIZE columns of integers in the range 0 to N_COLORS – 1. Now we can discuss the matching process we will use. Our technique is based on the notion of a color histogram, which is just a tally of how many times each color appears in an image. Here is an example, assuming for simplicity that the images are 4 x 4 arrays and that there are 10 possible colors: Image Histogram 2 7 4 4 1 3 4 4 1 3 6 4 0 3 1 2 5 2 1 2 0 0 1 5 5 7 0 1 2 3 4 5 6 7 8 9 The histogram values are in the boxes, and the color numbers are written in below for reference. Thus the histogram tells us that color 1 appears 3 times in the image, color 4 appears 5 times, and that color 8 doesn’t appear at all
-6- If you consider that in a small group of people,there will be variation in hair color,skin color,clothes color,etc.,then it is likely that each person's histogram will be quite different from the others.If we compare the histogram of an unknown image with each of the known images,then we can probably identify the unknown person. What we will compute is a difference score between the unknown histogram and each known histogram.This score is simply the sum of the absolute values of the differences of the elements.For example: known histogram 0 2 52 0 0 unknown histogram 0 abs (known [i]unknown [i]) 1020410210 difference score 11 If we compare the unknown histogram to each of the known ones,then we will identify it as the one with the lowest difference score.(Note:abs in the integer absolute value function from stdlib.h.) Now we can write some code. Part(a)Making a histogram In this part,your job is to write a function that computes the histogram for an image.The prototype is as follows: void MakeHistogram(int pict[SIZE][SIZE],int hist[N COLORS]); pict is the image being analyzed,and the function places the histogram in the uninitialized array passed to it as hist.(As you know,we aren't required in C to write in the size of the first dimension of pict or the size of hist,but we will do so in this problem to make it absolutely clear to you what the arguments are.) Write your code for this part at the top of the next page
– 6 – If you consider that in a small group of people, there will be variation in hair color, skin color, clothes color, etc., then it is likely that each person's histogram will be quite different from the others. If we compare the histogram of an unknown image with each of the known images, then we can probably identify the unknown person. What we will compute is a difference score between the unknown histogram and each known histogram. This score is simply the sum of the absolute values of the differences of the elements. For example: known histogram 0 3 1 2 5 2 1 2 0 0 unknown histogram 1 3 3 2 1 3 1 4 1 0 abs(known[i] – unknown[i]) 1 0 2 0 4 1 0 2 1 0 difference score 11 If we compare the unknown histogram to each of the known ones, then we will identify it as the one with the lowest difference score. (Note: abs in the integer absolute value function from stdlib.h.) Now we can write some code. Part (a) Making a histogram In this part, your job is to write a function that computes the histogram for an image. The prototype is as follows: void MakeHistogram(int pict[SIZE][SIZE], int hist[N_COLORS]); pict is the image being analyzed, and the function places the histogram in the uninitialized array passed to it as hist. (As you know, we aren’t required in C to write in the size of the first dimension of pict or the size of hist, but we will do so in this problem to make it absolutely clear to you what the arguments are.) Write your code for this part at the top of the next page
-7- void MakeHistogram(int pict[SIZE][SIZE],int hist[N_COLORS]) Part(b)Making histograms for the known data set Now you need to use your function to create histograms for the known data.Assume that main has the following declarations: main() int knownData[N PICTS][SIZE][SIZE]; int histograms [N PICTS][N COLORS]; int i; You can assume that the image data has already been stored in knownData.You will no doubt use a for loop,so we will write that for you.All you need to do for this part is show how to call the function you wrote in part (a)from inside the loop to create the histograms for the known data. for (i=0;i N PICTS;i++)
– 7 – void MakeHistogram(int pict[SIZE][SIZE], int hist[N_COLORS]) { Part (b) Making histograms for the known data set Now you need to use your function to create histograms for the known data. Assume that main has the following declarations: main() { int knownData[N_PICTS][SIZE][SIZE]; int histograms[N_PICTS][N_COLORS]; int i; You can assume that the image data has already been stored in knownData. You will no doubt use a for loop, so we will write that for you. All you need to do for this part is show how to call the function you wrote in part (a) from inside the loop to create the histograms for the known data. for (i = 0; i < N_PICTS; i++) {
-8-
– 8 – }
-9- Part(c)Identifying an unknown image Your final task is to write a function to identify an unknown image.The function has the following prototype: int BestMatch(int unknown[SIZE][SIZE],int histograms [N PICTS][N COLORS]); The arguments are the unknown image and the array of histograms of the known images.The function creates the histogram of the unknown,compares it to the known histograms using the difference score method discussed above,and returns the index of the known histogram that produces the lowest difference score.(If there is a tie,you may return the index of any of the tying histograms.) Write you answer here(additional space is available on the next page).Decomposition will simplify your code. int BestMatch(int unknown[SIZE][SIZE],int histograms [N PICTS][N COLORS])
– 9 – Part (c) Identifying an unknown image Your final task is to write a function to identify an unknown image. The function has the following prototype: int BestMatch(int unknown[SIZE][SIZE], int histograms[N_PICTS][N_COLORS]); The arguments are the unknown image and the array of histograms of the known images. The function creates the histogram of the unknown, compares it to the known histograms using the difference score method discussed above, and returns the index of the known histogram that produces the lowest difference score. (If there is a tie, you may return the index of any of the tying histograms.) Write you answer here (additional space is available on the next page). Decomposition will simplify your code. int BestMatch(int unknown[SIZE][SIZE], int histograms[N_PICTS][N_COLORS]) {
-10- More space for the answer to Problem 2
– 10 – More space for the answer to Problem 2