Introduction to Computer Science - Fall Semester 1998/9 Exercise 6

Due: 4/2/1999

Ex 6.1 LARGE numbers

The largest number fitting into a long int is 4 billion. In this exercise we do arithmetic with n digit numbers (implemented by arrays of integers).

1. Write a function void add(int sum[], int a[], int b[]) that adds two LARGE numbers. (don’t forget the carry!).

2. Write a program that reads two large numbers from the user, adds them, and prints the result on the screen.

For example, your output may look like this:

Please enter two integers with < 20 digits,
First integer:  88099005798957
Second integer:   776988213577
Sum:            88875994012534

Ex 6.2 Euclid’s gcd Algorithm

Write a program that computes the gcd (greatest common divisor) of two positive integers.

int gcd(int p, int q)
{
   int r;
   if ((r = p % q) == 0)
      return q;
   else
      return (gcd(q,r));
}

First, write a program to test the function (notice that it works only if p > q). Then write and test an equivalent iterative function.

Ex 6.3 Merge Sort* - bonus

Write a recursive algorithm implementing the following merge sort algorithm:

Given an array n[0..l],

1. Independently sort n[0..l/2-1] and n[l/2..l]

2. Merge the two arrays.

Ex 6.4 Lexicographically comparing two strings

Implement the function int strcmp(char s1[], char s2[]), that receives two strings and outputs: 0 if s1 equals s2 (as strings) 1 if s1 appears after s2 in the dictionary -1 otherwise.