Confidential Teaching Materials:
Final Exam Grading Criteria, Page 1 of 17
Final Exam Grading Criteria
Note: To receive any credit whatsoever, the date, your name, your student number, and your answers must
be legible and readily readable in the judgment of the grader.
Add brief explanatory comments as necessary to make sure your answers are clear and unambiguous
to the grader.
[p1] 15.0 points
Write a recursive module called Multiply. It will be passed two numbers as parameters, and will return the
product of the two numbers. You may assume that the numbers that will be passed to the module will always be
non-negative integers. You may use only the + and – operators in your answer.
[c1] 15 points
Sample Solution (particulars may very):
GRADING:
-0.5 for not making it return a num
-0.5 (x2) not making them a num
-1 for not returning 0 on 0 terminating condition
-1 for not returning appropriately at 1
-1 for not making recursive call with right parameter
[p2] 25.0 points
a) Declare the necessary data structures for a binary search tree of CDs in a music store. Each
CD has the following information associated with it:
Confidential Teaching Materials:
* UPC number (example: 2928)
* Artist (example: R.E.M.)
* Title (example: Reckoning)
* Year published (example: 1984)
b) Using your declaration from part (a), write a module that, passed an already-filled-in CD record
and a pointer to the root of a CD binary search tree as parameters, adds the new CD to the tree
by order of UPC number.
[c2] 25 points
Sample solution (particulars may vary):
a) CD_Rec definesa record
upc isoftype Num
b) procedure Add_CD (root isoftype in/out ptr toa CD_Tree_Node.
data_to_add isoftype in CD_Rec)
if (root = NIL) then
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 3 of 17
procedure
-1 for not making it a procedure
-1 for flawed pointer parameter
-4 for not terminating at the proper place
-2 if they did not terminate on other condition
-2 for not assigning the data field
-2 for not setting current to temp
-2 for recursing with wrong parameters
[p3] 20.0 points
Given the following declaration:
Number_List_Node definesa record
data isoftype Num
next isoftype ptr toa Number_List_Node
endrecord // Number_List
Write a module that will return the average of all of the numbers in a linked list of numbers. If the list is empty,
your module should return 0.
[c3] 20 points
Sample solution A:
function List_Average returnsa Num (current isoftype in
ptr toa Number_List_Node)
sum, count isoftype Num
count = 0
sum = 0
Confidential Teaching Materials:
GRADING A:
-0.5 for not making it a function
-1 for missing parameter
-0.5 for not making it a ptr
-1 (x2) for each missing initialization
-1 for not exiting at NIL
-1 for not adding to count
Sample solution B:
function List_Average returnsa Num (current isoftype in ptr toa
Number_List_Node)
GRADING B:
Average function
-0.5 for not making it return a Num
-0.5 for not making it an in
-1 for not returning 0 where appropriate (not dividing by 0)
-2 for not returning proper average
Confidential Teaching Materials:
Sum/Count functions
-0.5 for not making it a function
-1 for missing parameter
-0.5 for not making it a ptr
-1 for not returning 0 on terminating condition
-1 for not passing proper parameter to recursive call
-1 for not adding proper value to recursive call
[p4] 35.0 points
A queue is a data structure that provides first-in, first-out behavior. This means that the first item you put in the
queue (“enqueue”) is the first item that you will get out of the queue (“dequeue”).
Write a Queue class. Since the potential user of your queue should be able to create a queue of any data type,
you must use a generic parameter in your implementation. The following are the headers for the modules
that your queue must have in its public section (note that the Data_Type refers to the generic parameter):
procedure Enqueue (data_to_add isoftype in Data_Type)
procedure Dequeue (data_dequeued isoftype out Data_Type)
function Is_Empty() returnsa boolean
procedure Initialize()
Use a linked list to implement the queue in the protected section. You must use these exact headers for your
public modules – you may not add or remove any parameters. Be sure to include necessary module contracts
(purpose, pre-, and post-condition comments), and feel free to use helper modules in the protected section.
[c4] 35 points
Sample solution (particulars may vary):
class Queue (Data_Type isoftype type)
public:
procedure Enqueue (data_to_add isoftype in Data_Type)
procedure Dequeue (data_dequeued isoftype out Data_Type)
Final Exam Grading Criteria, Page 6 of 17
GRADING:
-3 for not having “class Queue ( Data_Type isoftype in Type)”
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 7 of 17
[p5] 25.0 points
Given the following declarations:
Number_List_Node definesa record
data isoftype Num
next isoftype ptr toa Number_List_Node
endrecord // Number_List_Node
Number_Tree_Node definesa record
data isoftype Num
left,
right isoftype ptr toa Number_Tree_Node
endrecord // Number_Tree_Node
Write a module that converts all of the data from a binary search tree of numbers to a linked list of numbers.
Your module will take in a pointer to a filled-in tree of numbers, convert it to a linked list of numbers, and pass
back the new list to the calling module (also via a parameter). The order of the data in the binary search tree must
be reflected in the resulting linked list.
[c5] 25 points
Sample solution (particulars may vary):
procedure Add_To_List (current isoftype in/out ptr toa Number_List_Node,
data_to_add isoftype in Num)
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 8 of 17
GRADING:
If they did not have the Convert/ Convert_Work procedure thing
Convert_Work
-1 for not making it a procedure
-0.5 for not making it an in
-1 for not having the list parameter
-0.5 for not making it a pointer to a Number_List_Node
-2 for not recursing left
-2 for not going right
Add_To_List module
-1 for not making it a procedure
-1 for not having the data_to_add parameter
[p6] 20.0 points
Give the Big-O (worst-case running time) of the following algorithms. Also include a brief explanation of the
Big-O. Answers without explanations will receive no credit.
a) Searching a full and balanced binary search tree of numbers for its smallest value. The BST is of size N.
b) Determining the median of all the values in a sorted array of numbers. The median for a collection of numbers
is the middle value. e.g.: for -1,-1,1,4,5 the median would be 1 since there are two numbers below the 1 and two
numbers above the 1. If there are an even number of numbers then the average of the two numbers is the median.
e.g.: for 1,2,3,5,6,7 the median would be (3+5)/2 = 4. The array is of size N.
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 9 of 17
c) // assume i, j, and k have been declared as variables
// assume N has been defined as a constant
i <- 1
loop
exitif (i > N)
print (i)
i <- i + 1
endloop
j <- 1
loop
exitif (j > N)
k <- 1
loop
exitif (k > N)
print (j+k)
k <- k + 1
endloop
j <- j + 1
loop
exitif (k=1)
print (j-k)
k <- k – 1
endloop
endloop
d) converting the data of an unsorted array of size N to a binary search tree.
[c6] 20 points
[p7] 15.0 points
What is the output of the following algorithm? Include a separate line for each print statement in your answer.
algorithm Tracer
function Confusion isoftype Num (x, y isoftype in Num)
if (x > y + 3) then
if (x > 5) then
Confusion returns 8
else
Confusion returns 4
endif
else
Confusion returns 3
endif
endfunction // Confusion
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 10 of 17
procedure Ambiguity (a isoftype in Num,
b isoftype in/out Num,
c isoftype out Num)
c <- 2 * (a + b)
a <- a + 1
b <- c – 1
print (a, b, c)
endprocedure // Ambiguity
// begin main algorithm
value1,
value2,
value3 isoftype num
value1 <- 1
value2 <- 2
value3 <- 3
Ambiguity (value1, value2, value3)
print (value1, value2, value3)
value3 <- Confusion (value1, value2)
Ambiguity (value2, value3, value1)
print (value2, value1)
Value1 <- Confusion (value3, value2)
print (value1)
endalgorithm // Tracer
[c7] 15 points
[p8] 20.0 points
Answer each of the following questions:
a) What is a “greedy algorithm”? Why are greedy algorithms used?
b) Explain the difference between a concurrent and a parallel system, and give examples of each.
c) Explain the difference between procedures and functions. When should each be used?
d) List and explain at least three benefits of object-oriented programing.
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 11 of 17
[c8] 20 points
Sample solutions:
a) Used to find a good solution in a reasonable amount of time, but does not necessarily find
GRADING:
There are obviously a lot of ways to answer these…
[p9] 15.0 points
Draw a precedence and dependence graph for the following code segment. You may assume that all variables
have been declared and initialized. Note: you may either draw a picture, or provide textual representations as you
did in the homework.
x <- 1 // S1
y <- 2 // S2
print(x) // S3
x <- y + 7 // S4
y <- x // S5
. . .
[c9] 15 points
ANSWER:
Time Chunk Statement Precedence Dependence
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 12 of 17
GRADING:
-5 for not having the correct number of time chunks
[p10] 10.0 points
Identify and correct all errors in the following code segment. You may assume that the comments and linked list
declaration are correct.
List_Node definesa record
data isoftype Num
next isoftype ptr toa List_Node
endrecord // List_Node
procedure Insert_In_Order (data_to_insert isoftype in/out Num,
current isoftype in/out ptr toa List_Node)
// inserts a number into a linked list in ascending order
if (current^.data > data_to_insert) then
temp <- new(List_Node)
temp^.data <- data_to_insert
temp^.next <- NIL
current <- temp
else
Insert_In_Order (current^.data, data_to_insert^.data);
endif
endprocedure // Insert_In_Order
[c10]
ANSWER:
[p11] 10.0 points
For the module:
function Mod returnsa Num (x, y isoftype in Num)
if (x < y) then
Mod returns x
else
Mod returns Mod (x-y, y)
endif
endfunction // Mod
Show a stack trace for Mod (11, 2) called from the main algorithm.
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 13 of 17
[c11] 10 points
ANSWER:
[p12] 25.0 points
a) Define a two-dimensional array of numbers. Your array should be 5 rows by 5 columns.
b) Using your definition from part a, write a module that will return TRUE if the two outer columns of the array
have the same sum. Your module will take in an already-filled-in two-dimensional array as a parameter.
Examples:
Array Module Should Return
—– ——————–
1 2 3 4 5
2 1 2 3 4
1 4 5 6 8 FALSE
1 3 4 5 6
1 3 2 8 10
1 2 3 4 5
4 5 1 2 3
3 4 2 3 4 TRUE
2 3 4 5 1
4 2 3 2 1
[c12] 25 points
Sample Solution:
exitif (i > MAX)
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 14 of 17
GRADING:
a) Data Type Definition
(4 points)
b) Function Implementation
(21 points)
-1 for not making it a function
-1 for not making it return a Boolean
[p13] 10.0 points
Given the following:
MAX is 10
Letter_Array definesa array [1..MAX] of Char
procedure Trace_Array (my_array isoftype in Letter_Array)
i isoftype Num
i <- 3
loop
exitif (i > MAX)
print (i, my_array[i])
if (i >= 5) then
i <- i + 1
elseif (i = 1) then
i <- i + 4
else
i <- i – 1
endif
endloop
endprocedure // Trace_Array
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 15 of 17
What is the output of a call to Trace_Array when the array passed to it is:
Position: 1 2 3 4 5 6 7 8 9 10
Value: a k e f o c q s y z
[c13] 10 points
ANSWER:
GRADING:
[p14] 30.0 points
Given the following class public section:
class Set (Data_Type isoftype type)
public:
procedure Add (data_to_add isoftype in Data_Type)
// Purpose: Adds a new piece of data to the set.
// Pre: data_to_add is not already in the set
// Post: data_to_add is added to the set.
procedure Remove (data_to_remove isoftype in Data_Type)
// Purpose: Removes a piece of data from the set.
// Pre: data_to_remove is in the set
// Post: data_to_remove is removed from the set
function Contains returnsa boolean (data_sought isoftype in Data_Type)
// Purpose: Determines whether or not a given piece of data is in the set
// Pre: None
// Post: Returns TRUE if data_sought is in the set, or FALSE otherwise
function Count_Elements returnsa Num()
// Purpose: Returns the number of elements in the set
// Pre: None
// Post: The number of elements in the set is returned.
procedure Initialize()
// Purpose: Initializes a Set object
Write an algorithm that allows the user to manipulate a set of strings. Your algorithm should provide the user
with the following options:
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 16 of 17
1. Add an element to the set
2. Remove an element from the set
3. See if an element is contained within the set
4. Print the number of elements in the set
5. Quit
After each selection is processed, the menu should be re-displayed until the user selects the quit option. Make
sure that all pre-conditions are enforced according to the contracts given in the Set class headers. For example, if
the user tries to delete an element from the set that does not exist, your algorithm should display an error message.
You do not have to write the code for the protected section of the class!
[c14] 30 points
Sample solution:
Confidential Teaching Materials:
Final Exam Grading Criteria, Page 17 of 17
GRADING: (deduct no more than 30 points)
Remove: (7)
-3 for not checking pre condition
Contains: (4)
Element count: (3)