Data Structures and Algorithms lab 1

1) Implement the GCD (GreaterCommonDivisor) Algorithm
Input: Two positive integers, m and n
Output: The GCD of m and n
While (r ← m mod n) ≠ 0 ?←? ?←?
Output n

Answer

import java.util.Scanner;

public class lab1_part1 {
	private int n;
	private int m;

	private void GCD(int m, int n){	
		int r;
		int k=n;
		while ((r= m % n) !=0){
		  m=n;
		  n=r;
		}
		System.out.println("The greatest common divisor for " +m + " and " +k+ " is " +n);
	}


	public static void main (String[] args){
		 lab1_part1 ans = new lab1_part1 ();
		 Scanner keyboard =new Scanner(System.in);
		System.out.print("Enter first integer: ");
		int m=keyboard.nextInt();
		System.out.print("Enter second integer: ");
		int n=keyboard.nextInt();
		ans.GCD(m, n);
		    
	}
}

2) Check the correctness of the algorithm for the following values of m and n:
(m, n): (12, 18) (54, 40) (67, 97) (420, 54) (2480, 735)
Output m, n, gcd(m,n). You may want to verify your results by hand or risk losing marks if your results are incorrect.

Answer

When (m,n) is (12,18)
Factors of 12 are: 1 , 2 , 3 , 4 , 6 , 12
Factors of 18 are: 1 , 2 , 3 , 6 , 9 , 18
GCD is 6

When (m,n) is (54, 40)
Factors of 54 are: 1 , 2 , 3 , 6 , 9 , 18 , 27 , 54
Factors of 40 are: 1 , 2 , 4 , 5 , 8 , 10 , 20 , 40
GCD is 2

When (m,n) is (67, 97)
Factors of 67 are: 1 , 67
Factors of 97 are: 1 , 97
GCD is 1

When (m,n) is (420, 54)
Factors of 420 are: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 10 , 12 , 14 , 15 , 20 , 21 , 28 , 30 , 35 , 42 , 60 , 70 , 84 , 105 , 140 , 210 , 420
Factors of 54 are: 1 , 2 , 3 , 6 , 9 , 18 , 27 , 54
GCD is 6

When (m,n) is (2480, 735)
Factors of 2480 are: 1 , 2 , 4 , 5 , 8 , 10 , 16 , 20 , 31 , 40 , 62 , 80 , 124 , 155 , 248 , 310 , 496 , 620 , 1240 , 2480.
Factors of 735 are: 1 , 3 , 5 , 7 , 15 , 21 , 35 , 49 , 105 , 147 , 245 , 735.
GCD is 5

3) Modify your implementation of gcd(m.n) to create a function gcdIterations(m,n) that returns the number of times the while loop is executed. (Basically modify gcd to include a counter in the loop).

Answer

import java.util.Scanner;

public class lab1_part3 {
	private int n;
	private int m;

	private void gcdIterations(int m, int n){	
		int r;
		int k=n;
		int counter=0;
		while ((r= m % n) !=0){
		  m=n;
		  n=r;
		  counter++;
		}
		System.out.println("The greatest common divisor for " +m + " and " +k+ " is " +n);
		System.out.println("counter is " + counter);
	}

	public static void main (String[] args){
		 lab1_part3 ans = new lab1_part3 ();
		 Scanner keyboard =new Scanner(System.in);
		System.out.print("Enter first integer: ");
		int m=keyboard.nextInt();
		System.out.print("Enter second integer: ");
		int n=keyboard.nextInt();
		ans.gcdIterations(m, n);	    
	}
}

4) Generate pairs of positive integers (m,n) using a nested loop as shown below. Record and plot the results. On the same graph, plot the function 2 log m.
// Create an array max with indices 0 to 100. Initialized to zeroes.
for m = 1 to 100
for n = 1 to m
max[m] = maximum(max[m], gcdIterations(m,n))
// Plot n going from 1 to 100 on the x axis, and two curves y = max[m] and y = 2 log m.

Answer

import java.util.Scanner;

public class lab1_part4 {
	private int n;
	private int m;

	private int gcdIterations(int m, int n){	
		int r;
		int k=n;
		int counter=0;
		while ((r= m % n) !=0){
		  m=n;
		  n=r;
		  counter++;
		}
		return counter;
	}

	public static void main (String[] args){
		lab1_part4 ans = new lab1_part4 ();
		int max [];
		max = new int [100];
		for (int i = 0; i<100; i++){
			max[i]=0;
		}
		
		for (int m = 1 ; m < 101; m++){
			for (int n = 1; n <= m; n++){
				ans.gcdIterations(m, n);
				if (max[m-1] < (ans.gcdIterations(m, n)) )
					max[m-1] = (ans.gcdIterations(m, n)) ;
			}
		}
		for (int i = 0; i<100; i++){
			System.out.println(max[i]);
		}
	}
}

5) So … looking at the graph you generated, what observations can you make? In particular, what do you notice about the relationship between the two curves (e.g., no apparent relationship, intersecting, not intersecting, one always greater, always equal, etc.)?

Answer

Both function y = max[m] and y=2⌈log m⌉ start at the same point y=0 (intersection at y=0) and x=1(n=1)
y=2⌈log m⌉ is always greater than y = max[m] for n>1