Eric Roberts Handout #26CS106B April 24, 2009Practice Midterm Exam #1Review session: Tuesday, April 28, 7:00–9:00P.M., Braun AuditoriumMidterm #1: Thursday, April 30, 3:15–5:15P.M., Herrin T-120Midterm #2: Thursday, April 30, 7:00–9:00P.M., Braun AuditoriumThis handout is intended to give you practice solving problems that are comparable informat and difficulty to the problems that will appear on the midterm examination onThursday, April 30. A solution set to this practice exam will be handed out on Mondayalong with a second practice exam.Time and place of the examThe midterm exam is scheduled for a two-hour block at two different times and places(note that neither of the exams is in the regular lecture room). You may take the exam ateither time and need not give advance notice of which exam you plan to take. If you areunable to take the exam at either of the scheduled times, please send an e-mail message toeroberts@cs stating the following:• The reason you cannot take the exam at either of the scheduled times.• A two-hour period on Thursday or Friday at which you could take theexam. This time must be during the regular working day, and musttherefore start between 8:30 and 3:00 (so that it ends by 5:00).In order to schedule an alternate exam, I must receive an e-mail message from you by5:00P.M. on Monday afternoon. Late requests will not be honored. Instructions fortaking the midterm at an alternate time will be sent to you by e-mail on Tuesday.Review sessionThere will be a general review session for the midterm on Tuesday, April 28, from7:00–9:00P.M. in Braun Auditorium. We’ll go over problems from the practice exams,but you should also bring any questions that you have.CoverageThe midterm covers the material presented in class through Wednesday’s lecture thisweek, which means that you are responsible for the chapters in the text through Chapter 8(“Algorithmic Analysis”).The instructions that will be used for the actual midterm are reprinted beginning on thenext page. To conserve trees, I have cut back on answer space for the practice midterm;the actual exam will have much more room for your answers and for any scratch work.– 2 –General instructionsAnswer each of the questions given below. Write all of your answers directly on theexamination paper, including any work that you wish to be considered for partial credit.Each question is marked with the number of points assigned to that problem. The totalnumber of points on the exam is 60. We intend for the number of points to be roughlycomparable to the number of minutes you should spend on that problem. This leaves youwith an hour to check your work or recover from false starts.In all questions, you may include functions or definitions that have been developed in thecourse. First of all, we will assume that you have included any of the header files that wehave covered in the text. Thus, if you want to use a Vector, you can simply do sowithout bothering to spend the time copying out the appropriate #include line. If youwant to use functions that appear in the book that are not exported by an interface, youshould give us the page number on which it appears. If you want to include code fromone of your own assignments, we won’t have a copy, and you’ll need to copy the codeyou want to the exam.Unless otherwise indicated as part of the instructions for a specific problem, commentsare not required on the exam. Uncommented code that gets the job done will besufficient for full credit on the problem. On the other hand, comments may help you toget partial credit on a problem if they help us determine what you were trying to do.The examination is open-book, and you may make use of any texts, handouts, or coursenotes. You may not, however, use a computer of any kind.Problem 1: Tracing C++ programs and big-O (10 points)Assume that the functions Mystery and Enigma have been defined as follows:int Mystery(int n) { if (n == 0) { return 1; } else { return Enigma(2, Mystery(n - 1)); }}int Enigma(int n1, int n2) { if (n1 == 0) { return 0; } else { return n2 + Enigma(n1 - 1, n2); }}(a) What is the value of Mystery(3)?(b) What is the computational complexity of the Mystery function expressed in terms ofbig-O notation, where N is the value of the argument n. In this problem, you may assumethat n is always a nonnegative integer.– 3 –Problem 2: Vectors, grids, stacks, and queues (10 points)Many of the figures in my books are generated by creating pictures in PostScript®, apowerful graphics language developed by the Adobe Corporation in the early 1980s.PostScript programs store their data on a stack. Many of the operators available in thePostScript language have the effect of manipulating the stack in some way. You can, forexample, invoke the pop operator, which pops the top element off the stack, or the exchoperator, which swaps the top two elements.One of the most interesting (and surprisingly useful) PostScript operators is the rolloperator, which takes two arguments: n and k. The effect of applying roll(n, k) is torotate the top n elements of a stack by k positions, where the general direction of therotation is toward the top of the stack. More specifically, roll(n, k) has the effect ofremoving the top n elements, cycling the top element to the last position k times, and thenreplacing the reordered elements back on the stack. Figure 1 at the bottom of the pageshows before and after pictures for three different examples of roll.Your job in this problem is to write a functionvoid Roll(Stack<char> & s, int n, int k)that implements the roll(n, k) operation on the character stack s. In doing so, you willprobably find it useful to use other structures (stacks, queues, vectors, and so forth) astemporary storage. Your implementation should check to make sure that n and k are bothnonnegative and that n is not larger than the stack size; if either of these conditions isviolated, your implementation should call Error with the messageRoll: argument out of rangeFigure 1. Three examples of the roll operator)1,4(llor)2,3(llor)0,2(llorDCBACBADbefore afterDCBABDCAbefore afterDCBADCBAbefore after– 4 –Problem 3: Lexicons, maps, and iterators (15 points)For the cell-phone mind-reading problem on Assignment #3, you wrote a procedurevoid ListCompletions(string digits, Lexicon & lex);that printed all words from the lexicon that could be formed by extending the