Week 5: Exercises

1. Googol

A googol is the number 10¹⁰⁰.

Write a program that computes and prints the number

10¹⁰⁰ mod 47

2. Very Big Number

Consider the number N = 2^(2³⁰⁰).

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).

3. Minimal Multiplication

Write a static method int pow47(int n) that computes

n¹⁰⁰ mod 47

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

4. Long Exponentiation

Write a static method int pow47(long a, long b) that computes

a^b mod 47

Your method should run quickly even for large values of b.

5. Set of Longs

Write a class Set that represents a set of values of type 'long'. Your class should have the following members:

• Set() - create a new empty set

• int count { get; } - return the number of elements in a set

• void add(long l) - add a value to the set if not already present

• bool contains(long l) - return true if the set contains the given value, otherwise false

What will be the average-case big-O running time of add() and contains()?

6. Polynomials

Design and implement a C# class Polynomial representing a polynomial of a single variable. Your class should include the following:

• a constructor that takes a variable number of arguments of type double, yielding a polynomial with those coefficients. For example,

      new Polynomial(1.0, 4.0, 5.0)

  should yield the polynomial x² + 4x + 5.

• an overloaded operator + that adds two polynomials

• an overloaded operator - that subtracts two polynomials

• an overloaded operator * that multiplies two polynomials, or a polynomial and a scalar

• a method that evaluates a polynomial for a given value of x

• a method that returns the first derivative of a polynomial

• a ToString() method that yields a string such as "x^2 + 4x + 5"

• a static method Parse() that parses a string such as "x^2 + 4x + 5", yielding a polynomial.

7. Queue

Write a class Queue implementing a queue of integers. A queue should have an unlimited size. The Queue class should have these members:

• Queue()

• bool isEmpty()

• void enqueue(int i)

• int dequeue()

• bool tryDequeue(out int i)

All operations should run in O(1).

8. Double-Ended Queue

Write a class Deque implementing a double-ended queue of integers:

Your class should have these members:

• Deque()

• bool isEmpty()

• void enqueueFirst(int i)

• int dequeueFirst()

• void enqueueLast(int i)

• int dequeueLast()

All operations should run in O(1). In dequeueFirst() and dequeueLast(), you may assume that the queue is not empty.

9. Array to Tree

Write a method that takes an array containing a sorted list of integers and returns a binary search tree containing all the values in the array. The tree should be as balanced as possible, i.e. it should have the minimum possible height.

10. Tree Check

Write a method that takes a binary tree and returns true if the tree satisfies the ordering requirements of a binary search tree.