Week 5: Exercises

1. Integer Square Root

Write a static method int sqrt(int n) that computes the integer square root of an integer n, i.e. the non-negative integer i such that i * i = n. If no such integer exists, return -1. Do not call any library functions. Your method must run in time O(log N) in the worst case.

2. Big Addition

Write a program that reads two integers, one per line, and prints their sum. The integers may be of any size. Do not use any library classes.

3. Big Multiplication #1

Write a program that reads two integers I and J, one per line, and prints their product. I may be of any size, and J is guaranteed to fit in an int. Do not use any library classes.

4. Big Multiplication #2

Write a program that reads two integers I and J, one per line, and prints their product. The integers may be of any size. Do not use any library classes.

5. Googol

A googol is the number 10¹⁰⁰.

Write a program that computes and prints the number

10¹⁰⁰ mod 47

6. Very Big Number

Consider the number N = 2^(2^300).

a) Suppose that we want to write N as a decimal number. There are approximately 10⁸⁰ atoms in the observable universe. If we write one digit on each atom, are there enough atoms to write N?

b) Write a program that computes and prints the value of (N mod 1,000,003).

7. Minimal Multiplication

Write a program that reads an integer n, and prints the number

n¹⁰⁰ mod 47

Your program should perform at most 10 multiplication operations. Do not call any library functions.

8. Shortest Path

Write a class Graph that holds a directed graph in adjacency-list representation. In this exercise, a graph with N vertices will have vertex numbers 0 .. (N – 1).

Your class should have these members:

• Graph() - read a graph from standard input in this format:

5      # number of vertices = N
2 3    # neighbors of vertex 0 (i.e. vertex 0 points to these vertices)
0 2 4  # neighbors of vertex 1
3 4    # ...
0 2    #
1 2 3  # neighbors of vertex (N - 1)

• int[] shortestPath(int start, int end)

Return an array containing a list of vertices along the shortest path from (start) to (end). If there is no path from (start) to (end), return null.

9. Knight with a Broken Leg

A knight on a chessboard has a broken leg. On odd moves (including his first move), he moves like a knight. On even moves, he may only move one square horizontally or vertically (not diagonally).

Write a method int knight_path((int, int) start_pos, (int, int) end_pos) that returns the length of the shortest path that the knight can take between positions (start_pos) and (end_pos) on a chessboard. Each position is a pair of coordinates (x, y), where 1 ≤ x, y ≤ 8.

10. Knight's Path Displayed

Modify your solution to the previous exercise to print out the chessboard, using digits to show the knight's path. The digit 0 should indicate the starting position, 1 should indicate the position after a single move, and so on.