Introduction to Algorithms, 2021-2
Week 4: Exercises

1. Doubling

Consider this program:

n = int(input('Enter n: '))

sum = 0
i = 1

while i < n:
    for j in range(n):
        sum += j
    i *= 2


print(sum)

1. What is the program's big-O running time as a function of n?

2. In the program, change "range(n)" to "range(i)". Now what is its running time?

2. Largest Prime Gap

A prime gap is the difference between two consecutive prime numbers. For example, 7 and 11 are consecutive primes, and the gap between them has size 4.

Write a program that reads an integer N ≥ 3 and prints the largest prime gap among primes that are less than N. The program should print the pair of consective primes along with the gap size.

3. Goldbach's Conjecture

Goldbach's conjecture says that

Every even integer greater than 2 is the sum of two primes.

The conjecture seems obvious, but after more than 350 years it remains unproven.

Write a program that reads an integer N and checks whether Goldbach's conjecture is true for all integers that are ≤ N.

4. Random Array

Write a program that reads an integer N and generates a random array of N integers in ascending order. The first number in the array should be 0, and the difference between each pair of consecutive array elements should be a random number from 1 to 10.

Next, the program should generate N new random integers in the range from 0 to 10N. The program should count how many of these integers are present in the array, and print this count.

If the input number N is large, what value do you think this program will print, approximately?

5. Integer Square Root

Write a program that reads an integer n ≥ 0 and prints the square root of n (if it is an integer), or otherwise 'Not a square'. Do not use any floating-point numbers. Your program should run in O(log n).