15-105 PRACTICE PROBLEMS - LAB EXAM 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 level of difficulty of the problems will be similar.

1. Write a Python program that implements the following algorithm that computes the least common multiple of x and y:

1. Input x
2. Input y
3. Set z = x * y
4. While y ≠ 0, do the following:
   a. Set a = y
   b. Set b = x modulo y
   c. Set x = a
   d. Set y = b
5. Output z / x

2. Write a Python program that prints out a table of powers of 2 less than 500000.

Algorithm: Start with i equal to 0. Set up a loop that prints i and 2ⁱ and then adds 1 to i. This loop should repeat while 2ⁱ is less than 500000.

Here is what the output should look like:

0 	1
1 	2
2 	4
3 	8
4 	16
5 	32
6 	64
7 	128
8 	256
9 	512
10 	1024
11 	2048
12 	4096
13 	8192
14 	16384
15 	32768
16 	65536
17 	131072
18 	262144

3. Write a Python program that computes the average of a set of integers stored in an array, rounded to the nearest integer. For example, the average of the integers in the array [42, 21, 63, 24, 93, 73, 50] is 52.0.

Algorithm: Initialize an array A with a set of numbers. (You do not have to read them in from the keyboard.) Add all of the numbers together into a single sum using a loop. Divide the total sum by the size of the array and output this result, rounded to the nearest integer. Your algorithm should work for any size array.

4. Complete the following Python program so that it prints out the following pattern:

*  
* *  
* * *  
* * * *  
* * * * *  
* * * * * *  
* * * * * * *  
* * * * * * * *  
* * * * * * * * *  

def main():
        i = 1
        while i < 10:
                displayStars(i)
                i = i + 1

def displayStars(n):
        # displays n stars on one line, separated by spaces
	# you complete this function:



main()

5. The GCD of x and y can be defined recursively as follows, assuming x and y are not negative:

gcd(x,y) = x if y = 0
gcd(x,y) = gcd(y, x modulo y) if y > 0

Complete the following Python program to compute GCD recursively:

def main():
	# Computes the GCD of 42 and 18
	print gcd(42, 18)
	# Computes the GCD of 15 and 105
	print gcd(15, 105)

def gcd(x,y):
	# Computes the GCD of x and y recursively
	# You complete this function:



main()