This page is archived

Key for Homework 1

Problem 1
(a) code: bad.cxx

//****************************************************************************
// g++ bad.cxx -o bad
// bad
//****************************************************************************

#include <cstdlib> // CORRECTION: the line added which provides EXIT_SUCCESS
#include <iostream>

using namespace std;

int main(){
	int List[100];

	int number, first;
        int second; // CORRECTION: declaration of this variable was missing
	cin >> number;

	for(int i = 0; i < number; i++)
       		cin >> List[i];

        first = second = List[0];

	for(int i = 1; i < number; i++) // CORRECTION: earlier this was i <= number;
		if(List[i] >= first){
			second = first;
			first = List[i];
		}
		else if (List[i] >= second)
		  second = List[i]; // CORRECTION: ";" was missing

	cout << first << " " << second << endl;
		
	return EXIT_SUCCESS;
}

(b) description of the program
It reads the total number of integers that you will enter, followed by the integers, then prints out the first and second largest numbers in the list for all the cases except those in which the largest element is the first element in the list. In this case, it prints out the largest element twice.

Problem 2
(a) code: a part of SmallList.cxx (also need to modify SmallList.h)

void SmallList::makeRandomList(int n){
	assert(n <= MAX_SIZE);
	RandGen rnd(n);
	for(int i = 0; i < n; i++)
          myList[i] = rnd.RandInt(1,n);

	mySize = n;
}

(b) code: a part of test_CountDistinct.cxx

//****************************************************************************
// g++ -c rando.cxx -o rando.o
// g++ -c SmallList.cxx -o SmallList.o
// g++ test_CountDistinct.cxx SmallList.o rando.o -o test_CountDistinct
// test_CountDistinct
//****************************************************************************

#include <cstdlib>
#include <iostream>
#include "SmallList.h"

using namespace std;

int CountDistinct(int n) {
        SmallList list;
	list.makeRandomList(n);
        list.removeDuplicates();
        int number;
        number = list.size();
	return number;
}

int main(){

        float count;
        for(int n = 100; n <=1000; n+=100){
                count = 0.0;
                for(int i = 0; i < 10; i++)
                        count += CountDistinct(n);
                cout << count/10 << endl;
        }

        return EXIT_SUCCESS;
}

(d) comments on the plot
The number of distinct element increases as the size of list increases. It gives us a straight line. The slope of the straight line tells us that about 60% of the elements in this list are distinct.

Problem 3
(a) code: test_removeDuplicates.cxx --- program to time removeDuplicates

//****************************************************************************
// g++ -c rando.cxx -o rando.o
// g++ -c SmallList.cxx -o SmallList.o
// g++ -c systimer.cxx -o systimer.o
// g++ test_removeDuplicates.cxx SmallList.o rando.o systimer.o -o test_removeDuplicates
// test_removeDuplicates
// in order to run this program you need to change "static const int MAX_SIZE = 1000;"
// in SmallList.h to "static const int MAX_SIZE = 10000;"
//****************************************************************************

#include <cstdlib>
#include <iostream>
#include "SmallList.h"
#include "systimer.h"

using namespace std;

int main() {
        SmallList list;
        SysTimer test_time;
        for (int i=1000; i<=10000; i=i+1000) {
	  list.makeRandomList(i);
          test_time.start();
          list.removeDuplicates();
          test_time.stop();
          cout << "n = "<< i << ": " << test_time.elapsedTime() << endl;
	}	
	return EXIT_SUCCESS;
}

(b) plot

(c) comments on the plot
It takes more time to perform removeDuplicates as the size of list increases.
From the plot you can see that the running time of the algorithm is a curve that grows faster than the straight line.

Problem 4
code: rational.cxx

//****************************************************************************
// g++ -c rational.cxx -o rational.o
//****************************************************************************

#include <iostream>
#include <cstdlib>
#include <cassert>

#include "rational.h"

using namespace std;

int gcd(int x, int y) {
  int a = y;
  while (a != 0) {
    y = a;
    a = x % a;
    x = y;
  }
  return x;
}

rational::rational() {
  top=0;
  bottom=1;
}

rational::rational(int i) {
  top=i;
  bottom=1;
}

rational::rational(int i, int j) {
  assert(j!=0);
  top=i;
  bottom=j;
  normalize();
}

rational::rational(const rational &source) {
  top=source.top;
  bottom=source.bottom;
}

int rational::numerator() const{
  return top;
}

int rational::denominator() const{
  return bottom;
}

void rational::operator = (const rational &r) {
  top = r.top;
  bottom = r.bottom;
}

void rational::operator += (const rational &r) {
  top = top * r.bottom + r.top * bottom;
  bottom = r.bottom * bottom;
 (*this).normalize();
}

void rational::operator -= (const rational &r) {
  top = top * r.bottom - r.top * bottom;
  bottom = r.bottom * bottom;
 (*this).normalize();
}

void rational::operator *= (const rational &r) {
  top = top * r.top;
  bottom = bottom * r.bottom;
 (*this).normalize();

}

void rational::operator /= (const rational &r) {
 top = top * r.bottom;
 bottom = bottom * r.top;
 (*this).normalize();
}

// returns 1 if p > q, returns 0 if p = q, and -1 if p < q
int rational::compare(const rational &r) const {
  if (top * r.bottom > bottom * r.top)
    return 1;
  if (top * r.bottom < bottom * r.top)
    return -1;

  return 0;
}

void rational::normalize() {
  int m = gcd(top, bottom);
  assert(m != 0);
  top /= m;
  bottom /= m;
}