University of California Berkeley College of Engineering Department of Electrical Engineering and Computer Sciences Spring 2007 Instructor Dr Dan Garcia 2007 03 05 CS61C Midterm After the exam indicate on the line above where you fall in the emotion spectrum between sad smiley Last Name First Name Student ID Number Login cs61c Login First Letter please circle a b c d e f g h i j k l m Login Second Letter please circle a n b o c p d q e r f s g t h u i v j w k x l y m z Aaron Alex Brian David Matt Michael Valerie The name of your SECTION TA please circle Name of the person to your Left Name of the person to your Right All the work is my own I had no prior knowledge of the exam contents nor will I share the contents with others in CS61C who have not taken it yet please sign Instructions Read Me Don t Panic This booklet contains 7 numbered pages including the cover page Put all answers on these pages don t hand in any stray pieces of paper Please turn off all pagers cell phones beepers Remove all hats headphones Place your backpacks laptops and jackets at the front Sit in every other seat Nothing may be placed in the no fly zone spare seat desk between students Question 0 1 point involves filling in the front of this page and putting your name login on every front sheet of paper You have 180 minutes to complete this exam The exam is closed book no computers PDAs or calculators You may use one page US Letter front and back of notes and the green sheet There may be partial credit for incomplete answers write as much of the solution as you can We will deduct points if your solution is far more complicated than necessary When we provide a blank please fit your answer within the space provided You have 3 hours relax Question Minutes Points Score 0 1 1 1 36 15 2 36 14 3 36 15 4 36 15 5 36 15 Total 180 75 Name Login cs61c Question 1 Is this the best midterm in memory No we freed it 15 pts 36 min a I have N bits to represent data and every bit pattern has a unique meaning I want to represent 3 times as many things How many more bits do I need b We are given two nibbles A 0xF and B 0b0010 and we wish to calculate their SUM A B We only have a nibble to store the SUM result What is SUM if all three nibbles A B SUM were Algorithm SUM encode decode into decimal A decode into decimal B SUM single hex character sign magnitude ones complement unsigned twos complement encoded with a bias of 7 like the way the exponent is encoded w float Decimal number SUM encodes Was there overflow 0x 0x 0x 0x 0x c Put the following in chronological order We ve started it for you 1 Code and Data from various places are stitched together A CS61C student is assigned a project that implements big nums Execution begins at main The student writes his or her code in C Link tables are produced MAL is translated into TAL Static code and global space are reserved initialized in memory The student s C code is translated into MIPS Links are edited d Assume we have just enough bits to byte address 51210 zebibytes We want to define some number of the most significant bits to encode 910 x 250 things and some number of the least significant bits to encode 2 00010 things How many things can we encode with the remaining bits Use IEC language like 16 mebithings Show your work e For every line of code on the right we want to know if any memory is used and if so where and how much If zero leave it blank Static Stack Heap 1 2 3 4 5 6 7 8 9 10 typedef struct bignum int len char num char description 100 bignum t bignum t res int main bignum t b b num char malloc 5 sizeof char more code below 2 7 Name Login cs61c Question 2 If swimming in the 61 6 1 7 Cs keep a float 14 pts 36 min The figure below shows the layout of the different types of 32 bit float numbers on a not to scale real number line with zero in the center and NaNs considered to be further from zero than infinity Negative Zero Positive Zero Most positive NaN Most negative NaN Least negative denorm Least positive denorm Most negative denorm Most positive denorm Least negative normalized number Least positive normalized number Least negative NaN Least positive NaN Negative Infinity Positive Infinity Most negative normalized number Sign bit 1 Most positive normalized number Sign bit 0 0 For each of the a f values below draw marks below the number line like we ve done for 0 indicating where the value would fall Label the mark with the corresponding letter and actual value below it a The sign magnitude number closest to b The result of casting the double number closest to but is not into a float c 1 X 1 where X is the largest ones complement number d The number represented by the float bits 0x80000001 e The number represented by the float bits 0x00000000 times the number represented by the float bits 0xFFFFFFFF using normal floating point multiply mul s f The difference between the int value closest to and the float that can most closely represent that int s value g The default float rounding mode often needs to break ties for numbers that fall between floats it can represent What is the largest unsigned int that falls exactly between two floats and what does it round to e g If this were in decimal you might write 3 5 4 Show your work below and put your answer in the box You may leave your result as a simplified expression 3 7 Name Login cs61c Question 3 Goodness Grandma what bignums you have 15 pts 36 min Part A After your extensive C bignum experience you were hired by Lawrence Berkeley Labs to make an arbitrary precision math package The scientists use scientific notation and keep track of significant figures The scientists have written a function called sci bignum cmp as shown below Unfortunately the implementation has at least one bug In the boxes at the bottom briefly explain all of them and give sample values for a and b i e 1 23 x 104 that causes sci bignum cmp to reveal the bug You may not necessarily use all the boxes As an example to store the number 1 23 x 104 the sign would be the char the significand would be the null terminated string 123 num sigfigs would be 3 and the define POS exponent would be 4 There is an implicit decimal point after the first significand digit define NEG typedef struct …
View Full Document
Unlocking...