PSEUDOCODE ANALYSIS
1. Introduction
These exercises are intended to be done by hand with pencil and paper. Their
purpose is to gain experience in how computers follow instructions: Computers do
exactly what the instruction says in that order.
Because humans make mistakes in devising and implementing algorithms, it is
vitally important to be able to perform analyses of algorithms by hand to be able
to diagnose errors.
Question 1.
What is the final length of the list ’L’ if all of the following pseudocode is executed?
-----------------------------------------
Set the list ’L ’ to be [1 , 2].
Set the variable ’N ’ to have the value 3.
For every p in {1 , ... , 3} do the following :
| Set K to be the current length of the list L .
| For every q in {1 , ... , K } do the following :
| | Append the value of N to the list L .
| | Reset the value of N to be N +1
-----------------------------------------
16
1
2 PSEUDOCODE ANALYSIS
Question 2.
How many times will ”step” be printed on the screen if the following snippet of
pseudocode is executed?
-----------------------------------------
For every i in {1 , ... , 13 } do :
| For every j in {1 , ... , 14} do :
| | Print " step " to screen .
-----------------------------------------
182
PSEUDOCODE ANALYSIS 3
Question 3.
How many times will ”step” be printed on the screen if the following snippet of
pseudocode is executed?
-----------------------------------------
For every i in {1 , ... , 8 } do :
| For every j in {1 , ... , i } do :
| | Print " step " to screen .
-----------------------------------------
36
4 PSEUDOCODE ANALYSIS
Question 4.
How many times will ”step” be printed on the screen if the following snippet of
pseudocode is executed?
-----------------------------------------
For every i in {1 , ... , 10 } do :
| For every j in {1 , ... , i } do :
| | Print " step " to screen .
-----------------------------------------
55
PSEUDOCODE ANALYSIS 5
Question 5.
What is the final value of the variable x12 if all of the following pseudocode is
executed?
-----------------------------------------
Set the variable x0 to have the value 3.
Set the variable x1 to have the value 2.
Set the variable x2 to have the value 1.
For every k in {3 , ... , 12} do the following :
| Set the value of the variable xk to be xk−1 + xk−2 + xk−3 .
-----------------------------------------
1181
6 PSEUDOCODE ANALYSIS
Question 6.
What is the final value of the variable p if all of the following pseudocode is exe-
cuted?
What is the value of 2p after all of the following pseudocode is executed?
How many times will “step” be printed to the screen if all of the following
pseudocode is executed?
-----------------------------------------
Set the variable p to have the value 0
While 2p is strictly less than 10000 , do the following :
print ‘‘ step ’ ’
Reset the value of p to equal p +1
-----------------------------------------
14, 16384, 14
PSEUDOCODE ANALYSIS 7
Question 7.
What is the final value of the variable n if all of the following pseudocode is exe-
cuted?
How many times will “step” be printed to the screen if all of the following
pseudocode is executed?
-----------------------------------------
Set the variable n to have the value 96
While n is divisible by 2 , do the following :
Redefine the value of n as n/2
Print ‘‘ step ’ ’ to the screen
-----------------------------------------
3, 5
8 PSEUDOCODE ANALYSIS
Question 8.
The following algorithm describes one way to check if a number is prime.
For each of the cases for n below, how many times is the step marked (A)
executed?
• n = 31
• n = 22
• n = 15
• n = 247
-----------------------------------------
For every j in {2 , ... , n -1} do the following :
| Check if j divides n . If yes , then < - - - - - - - - - - -( A )
| | return False ( and stop ).
Return True ( and stop )
-----------------------------------------
29, 1, 2, 13