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