15-105 PRACTICE PROBLEMS - EXAM 1

NOTE CORRECTIONS TO VECTOR PROBLEMS - INDEX OF FIRST DATA VALUE SHOULD BE 0 NOT 1

Use these problems to get an idea about the format for the actual exam and the level of difficulty of the exam questions. The actual exam may or may not have problems that look like these problems, but the amount and difficulty of the problems will be similar. Note that there are additional topics in the course material that you should study that are not included in the problems below.

1. The following questions deal with the history of computation.

(a) Put the following computational devices in increasing order based on their year of invention, and write one sentence explaining the major significance of each device.

• Difference Engine
• ENIAC
• Abacus
• Pascaline
• Napier's Bones

(b) Babbage wants to set up his Difference Engine to compute the values of the function f(x) = x² + 8x + 3. What initial values does he use to set his machine?

#2 CORRECTED

1. Set i = 0
2. Set sum = 0
3. While i < n-1 do the following:
   a.  Add 1 to i
   b.  If A[i] < A[0], add A[i] to sum
4. Output sum

(a) Trace the algorithm above for n = 7 and A = [6, 3, 9, 7, 5, 6, 4], showing the contents of i and sum after each iteration of the loop.

(b) In general, how many times does the loop in step 3 repeat as a function of n? Explain your answer.

(c) Explain in one sentence what this algorithm does.

(d) Write the algorithm above as a Python program.

#3 CORRECTED

3. The following algorithm finds the largest data value in a vector of length n and exchanges it with the data value in the first position of the vector (if it isn't already there).

1. Input n
2. Input A[0], A[1], ..., A[n-1]
3. Set position = 0
4. Set maxPosition = 0
5. Do the following n-1 times:
   a.  Add 1 to position
   b.  If A[position] > A[maxPosition], set maxPosition = position
6. If maxPosition is not equal to 0, do the following:
   a.  Exchange A[maxPosition] with A[0]
7. Output A

(a) Typically, we cannot input all values of a vector at once. Draw a flowchart for step 2. (You do not have to draw the entire flowchart for the algorithm; just draw the part of the flowchart that represents step 2.)

(b) Draw a flowchart for step 6 and its substep 6a. Show explicitly how to do the exchange operation in your flowchart.

4. Consider the following sequence of data values in the order given:

74  25  63  97  30  18  26  82

(a) Insert these data values into a binary search tree in the order given and draw a picture of the resulting data structure.

(b) Insert these data values into a (max)heap in the order given and draw a picture of the resulting data structure.

(c) If these numbers were pushed on to a stack in the order given, and then popped off and displayed one by one until the stack is empty, what sequence would be displayed? Explain.

(d) Assume the sequence is stored in memory as a linked list as shown below with memory cell 120 being the "head" of the linked list:

MEMORY CELL     DATA          POINTER
ADDRESS         VALUE         (NEXT)
100             18            108
104             25            116
108             26            124
112             30            100
116             63            128
120             74            104
124             82            0 (null)
128             97            112
132             --            --

Rewrite this table after the data value 58 is inserted between the values 97 and 30 in the original sequence using memory cell address 132 to store the new data node.

5. Complete the flowchart shown here for an algorithm that prints out the pattern given below on the screen. The ¶ symbol in the flowchart indicates that the cursor should move to the next line.

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55