Introduction to Algorithms
Week 5: Exercises

1. Ninety-Nine Percent

Consider this program:

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

count = 0

while x > 1:
  x = x * 99 / 100
  count += 1

print(count)

What is its running time as a function of x?
What value will it print?

2. Ascending and Descending

Write a function largest that takes a list that is guaranteed to contain an ascending sequence of numbers followed by a descending sequence of numbers. For example, the list might be

[ 2, 4, 7, 10, 13, 15, 17, 14, 13, 5, 1 ]

The function should return the largest value in the input array. It is guaranteed that the input sequence will ascend at least once and descend at least once, i.e. the largest value will not be the first or last in the array. How efficient can this function be, in the worst case?

3. Approximate Square Root

Write a function my_sqrt(x) that takes a float x ≥ 0 and returns a value close to sqrt(x). Specifically, your function should return a number z such that |z² – x| < 0.000001 = 10^-6. Use a binary search.

4. Bubble Read/Writes

Given an array of N elements, exactly how many times will bubble sort read and write array elements in the worst case? In the best case?

5. Insertion Read/Writes

Given an array of N elements, exactly how many times will insertion sort read and write array elements in the worst case? In the best case? In the average case?

6. 100,000 Numbers

Suppose that we generate a list of 100,000 random floats in Python in the range from 0.0 to 1.0, and sort the list using insertion sort. How long do you think it will take to run? Justify your estimate.

Now run code that actually does this. How accurate was your estimate?

7. Lost Car

You are standing on a straight road that goes infinitely far in both directions. You remember that you parked your car somewhere on this road, but you don't know how far away it is or in which direction it is.

Describe an algorithm that you can use to find your car 100% of the time.
Let D be the distance from the start point to your car. What is your algorithm's best-case and worst-case asymptotic running time, as a function of D?
Give an exact upper and lower bound on your algorithm's running time, as a function of D.

8. Largest Palindrome Product

Solve Project Euler's problem 4. Do not use any strings or lists in your solution.

9. Pythagorean Triplet

Solve Project Euler's problem 9.

Introduction to Algorithms Week 5: Exercises