# Question 2

What does the following psuedocode output when n is 4?

product <- 1
for <- 1 to n do
product <- product * i
output product

• 1
• 0
• 10
• 24
• 4

# Question 1.2

What is the big O notation for this?

• O(n)
• O(n^3)
• O(log n)
• O(n^2)

# Question 4

Consider the following psuedo code to search if a value key is in a linked list and an instance of the linked list. What is being output at the end of the code if key is:

1. 25
2. 40
node ← head, found ← false
while node != NIL and found != true do
begin
if node.data == key then
found ← true
node ← node.next
end
if found == true then
output "FOUND!"
else output "NOT FOUND!"


1. true 2. false
1. NOT FOUND! 2. FOUND!
1. true 2. true
1. FOUND!. 2. FOUND!
1. FOUND!. 2. NOT FOUND!

# Question 6

State the order of growth of the following functions:

10n²log n + n log² n + 2n³ + 30n + 100

• O(n² log n)
• O(n³)
• O(100)
• O(30n)
• O(n log² n)

# Question 7

Consider the following binary tree rooted at the vertex r. What are the orders of vertices in an in-order traversal?

• r, a, b, c, d, e, f
• r, a, c, f, d, b, e
• f, c, d, a, e, b, r
• f, e, d, e, a, b, r
• c, f, a, d, r, e, b

# Question 8

Which of the following statements is incorrect?

• Dynamic programming uses recursion.
• Dynamic programming uses a table.
• Dynamic programming computes solutions in a bottom up manner.
• Dynamic programming needs a base case.
• All are correct