CS211 - Algorithms and Data Structures II

Department of Computer Science, NUIM



T Naughton, CS NUIM

Solutions for Tutorial 4







Problem 1.3



#include<iostream>



void main(void){



  int iarray[10];

  double darray[10];

  int counter;



  cout << endl<< "Hi! Please enter 10 integers, one on each line:" << endl;

  counter = 0;

  while (counter < 10) {

    cin >> iarray[counter];

    counter = counter + 1;

  }

  cout << "Thanks." << endl;



  counter = 0;

  while (counter < 10) {

    darray[counter] = double(iarray[counter]) / 2.0;

    counter = counter + 1;

  }



  counter = 0;

  while (counter < 10) {

    cout << iarray[counter] << "\t" << darray[counter] << endl;

    counter = counter + 1;

  }



}











Problem T2.4



#include<iostream>



/* This program shows two different ways of passing by reference.

** Exchange1 uses the standard pointer rules and preserves

** strong typing conventions. Exchange2 uses a C/C++ trick to make

** code look neater.

** As explained in lectures, I (TJN) have two reasons for

** preferring convention 1.

** 1) Less rules to remember -- convention 1 can be derived from the

**    basic pointer rules. This will be useful if/when coding

**    data structures with pointers to pointers of pointers.

** 2) In the calling function, it is obvious that the parameters will

**    be passed by reference without having to look at the called

**    function's prototype.

*/



void Exchange1(int * elem1, int * elem2){

  int temp;

  temp = *elem1;

  *elem1 = *elem2;

  *elem2 = temp;

}



void Exchange2(int & elem1, int & elem2){

  int temp;

  temp = elem1;

  elem1 = elem2;

  elem2 = temp;

}



void main(void){



  int iarray[2] = {3,4};



  int x = 5;

  int y = 6;



  cout << endl << endl;

  cout << "Swapping variables:" << endl;



  cout << iarray[0] << ' ' << iarray[1] << endl;

  Exchange1(&iarray[0], &iarray[1]);

  cout << iarray[0] << ' ' << iarray[1] << endl;

  Exchange2(iarray[0], iarray[1]);

  cout << iarray[0] << ' ' << iarray[1] << endl;



  cout << endl;

  cout << x << ' ' << y << endl;

  Exchange1(&x, &y);

  cout << x << ' ' << y << endl;

  Exchange2(x, y);

  cout << x << ' ' << y << endl;



}











Problem 1.5



#include<iostream>

void SortArray(int list[], int len);

int FindSmallest(int list[], int begin, int len);

void Exchange(int * elem1, int * elem2);





int FindSmallest(int list[], int begin, int len){

/*

** list ranges from [0..(len-1)]. FindSmallest returns the index

** corresponding to the smallest element in the subrange

** [begin..(len-1)].

*/

  int sindex, counter;

  sindex = begin;

  counter = begin + 1;

  while (counter < len){

    if (list[counter] < list[sindex]){

      sindex = counter;

    }

    counter++;

  }

  return sindex;

}





void Exchange(int * elem1, int * elem2){

  int temp;

  temp = *elem1;

  *elem1 = *elem2;

  *elem2 = temp;

}





void SortArray(int list[], int len){

/*

** list ranges from [0..(len-1)]. SortArray sorts list[], which is

** passed by reference. It works by exchanging the smallest unsorted

** element in the list with the smallest unsorted index.

*/

  int counter = 0;

  while (counter < len){

    Exchange(&list[counter], &list[FindSmallest(list,counter,len)]);

    counter++;

  }

}





void main(void){



  int * iarray;

  double * darray;

  int length, counter;



  cout << endl << "How many integers do you have?" << endl;

  cin >> length;



  iarray = new int[length];

  darray = new double[length];



  cout << endl << "Please enter the " << length << " integers, ";

  cout << "one on each line:" << endl;

  counter = 0;

  while (counter < length) {

    cin >> iarray[counter];

    counter++;

  }

  cout << "Thanks." << endl;



  /*

  ** Now sort the integers

  */

  SortArray(iarray, length);



  counter = 0;

  while (counter < length) {

    darray[counter] = double(iarray[counter]) / 2.0;

    counter++;

  }



  counter = 0;

  while (counter < length) {

    cout << iarray[counter] << "\t" << darray[counter] << endl;

    counter++;

  }



  delete [] iarray;

  delete [] darray;



}











Problem 2A.2



#include<iostream>



int findhighestlessthan100(int * list, int len){

  /* This function returns the index of the element with the

  ** highest value in 'list' that is less than 100. 'list' is

  ** an integer array of length 'len'.

  ** If no suitable values are found then an index to the first

  ** element is returned.

  */

  int highest; // the index with the highest value < 100

  int count;



  highest = 0;



  count = 1;

  while (count < len){

    if ((list[count]>list[highest]) && (list[count]<100)){

      highest = count;

    }

    count++;

  }

  return highest;

}



void main(void){

  const int len = 5;

  int array[len] = {12, 100, 81, 91, 200};

  cout << findhighestlessthan100(array, len) << endl;

}









Problem 2C.2



#include<iostream>



int findclosestto10(int * list, int len){

  /* This function returns the index of the element in 'list'

  ** that has a value closest to 10. 'list' is an integer

  ** array of length 'len'.

  ** If several values are equidistant from 10 then the first

  ** one encountered is returned.

  */

  int closest; // the element with a value closest to 10

  int diff;    // the difference between list[closest] and 10

  int newdiff; // the difference between list[count] and 10

  int count;



  closest = 0;

  if (list[closest]>10){

    diff = list[closest] - 10;

  } else {

    diff = 10 - list[closest];

  }

  count = 1;

  while (count < len){

    if (list[count]>10){

      newdiff = list[count] - 10;

    } else {

      newdiff = 10 - list[count];

    }

    if (newdiff<diff){

      diff = newdiff;

      closest = count;

    }

    count++;

  }

  return closest;

}



void main(void){

  const int len = 5;

  int array[len] = {12,4,67,11,21};

  cout << findclosestto10(array, len) << endl;

}











Problem 2B.3



#include<iostream>



void readints(int * array, int len);



/* This program reads 10 integers from the user and stores them

** in an array. Using a second array of type double of length 2,

** the program stores the sum and the average of the list of

** integers. Finally, the program outputs the sum and average.

*/



void readints(int * array, int len){

  int count;



  cout << endl << endl << "Please enter " << len;

  cout << " integers, one per line:" << endl;

  count = 0;

  while (count < len){

    cin >> array[count];

    count++;

  }

}



void main(void){

  const int len = 10;

  int array[len];     // holds 10 integers

  double info[2];     // holds sum and mean

  int count;



  readints(array, len);



  info[0] = double(array[0]);

  count = 1;

  while (count < len){

    info[0] = info[0] + double(array[count]);

    count++;

  }



  info[1] = info[0] / double(len);



  cout << endl << "Sum is " << info[0] << endl;

  cout << "Average is " << info[1] << endl;

}









Problem 2C.3



#include<iostream>



void readints(int * array, int len);



/* This program reads 31 integers from the user and stores them

** in an array. Using a second array of type int, of length 31,

** the program stores half the value of each of the first

** array's integers. Finally, the program outputs each int int

** pair where a rounding error has occurred.

*/



void readints(int * array, int len){

  int count;



  cout << endl << endl << "Please enter " << len;

  cout << " integers, one per line:" << endl;

  count = 0;

  while (count < len){

    cin >> array[count];

    count++;

  }

}



void main(void){

  const int len = 31;

  int array[len];     // holds integers

  int half[len];      // holds half of values in array[]

  int count;



  readints(array, len);



  count = 0;

  while (count < len){

    half[count] = array[count] / 2;

    count++;

  }



  cout << endl << endl << "Rounding errors occurred with the";

  cout << " following pairs:" << endl;

  count = 0;

  while (count < len){

    if ((half[count]*2) != array[count]){

      cout << array[count] << ' ' << half[count] << endl;

    }

    count++;

  }

}









Problem 3A.1



#include<iostream>



int * ReadInts(int * listsize);

int CheckSqrRoot(const int list[], int listsize);



/* This computer program reads positive integers, one per line,

** from the keyboard into a list. The user indicates that they

** are finished by entering any negative integer (the negative

** integer itself is not stored). The computer program then checks

** if any of the numbers in the list is the square root of any other

** number in the list. The program terminates after finding the

** first such number. This program is written using fixed-size arrays,

** the new and delete commands, and a routine to copy the elements

** from one array to another.

*/



int * ReadInts(int * listsize){

  /*

  ** This function reads into a list as many integers as entered by

  ** the user and returns a pointer to the list. The length of the list

  ** is implicitly returned.

  */



  int newint;       // Holds the new int from the user

  int * list = NULL;

  int * templist = NULL;

  int counter;



  cout << endl << "Please enter a list of positive integers, one ";

  cout << "per line. Indicate the list is finished by entering any ";

  cout << "negative integer:" << endl;



  cin >> newint;

  /* When this loops first begins the list is of length *listsize

  ** and as each integer is entered by the user we increase this length

  ** by one.

  */

  while (newint >= 0){

    /* save a pointer to list called templist, create a new list,

    ** copy templist into list, append tempint, delete templist.

    */

    templist = list;



    (*listsize)++; // increase the length by one

    list = new int[*listsize];



    counter = 0;

    /* copy the old list into the new (longer) list

    */

    while (counter < ((*listsize)-1)){

      list[counter] = templist[counter];

      counter++;

    }

    list[counter] = newint;



    delete [] templist;



    /*

    ** Temporary code to test the function...

    *

    counter = 0;

    cout << "List is now " << *listsize << " long: ";

    while (counter < *listsize){

      cout << list[counter] << ',';

      counter++;

    }

    cout << endl;

    */



    cin >> newint; // read in the next int and check if it is >0

  }



  return list;

}



int CheckSqrRoot(const int list[], int listsize){

  /* Square each element in the list and compare it to each element

  ** in the list (including itself). If its square is found in the list

  ** then return its index (it will be the square root).

  ** Otherwise, return -1 to indicate no square root was found.

  */

  int rootindex;          // index to square root (if any)

  int counter;            // index to potential squares

  long int rootsquared;   // set to 'long' just in case

  bool found;             /* have we found a square root? This is used

                          ** to break out of the loop as soon as the

                          ** first is found.

                          */



  rootindex = 0; // start searching from the beginning of the list

  found = false;

  while ((rootindex < listsize) && !found){

    // Check if the square of list[rootindex] also exists in list[]

    rootsquared = list[rootindex]*list[rootindex];



    counter = 0; // start searching again from the beginning of list

    while ((counter < listsize) && !found){

      if (rootsquared == list[counter]){

        found = true; // stop when the first is found

      }

      counter++;

    }

    rootindex++;

  }

  rootindex--;   // It will have been incremented once too often



  if (found) {

    return rootindex;

  } else {

    return -1;

  }

}



void main(void){

  int root;          // Index of first root found

  int * list = NULL; // The list

  int listsize = 0;  /* Size of the list (zero before the user

                     ** enters any integers)

                     */



  list = ReadInts(&listsize);



  root = CheckSqrRoot(list, listsize);



  if (root >= 0){

    cout << endl << "The number " << (list[root]*list[root]);

    cout << " has a square root of " << list[root];

    cout << " in the list." << endl;

  } else {

    cout << endl << "No square root found in the list.";

  }



  delete [] list; /* This is not needed here, but it's

                  ** good programming practice to explicitly free

                  ** memory (i.e. delete) if one explicitly allocates

                  ** it (i.e. with new).

                  */



}









Problem 3B.1



#include<iostream>



char * ReadChars(int * listsize);

void CheckNeighbours(const char list[], int listsize, int * i1, int * i2);



/* This computer program reads single characters, one per line,

** from the keyboard into a list. The user indicates that they

** are finished by entering a '%' character (the '%' is itself not

** stored). The computer program then checks if any of the letters,

** anywhere in the list, appear next to each other alphabetically.

** The program terminates after finding the first such pair of

** letters. This program is written using fixed-size arrays,

** the new and delete commands, and a routine to copy the elements

** from one array to another.

*/



char * ReadChars(int * listsize){

  /*

  ** This function reads into a list as many characters as entered by

  ** the user and returns a pointer to the list. The length of the list

  ** is implicitly returned.

  */



  char newchar;       // Holds the new char from the user

  char * list = NULL;

  char * templist = NULL;

  int counter;



  cout << endl << "Please enter a list of letters, one ";

  cout << "per line. Indicate the list is finished by entering a ";

  cout << "'%' character:" << endl;



  cin >> newchar;

  /* When this loops first begins the list is of length *listsize

  ** and as each character is entered by the user we increase this length

  ** by one.

  */

  while (newchar != '%'){

    /* save a pointer to list called templist, create a new list,

    ** copy templist into list, append tempint, delete templist.

    */

    templist = list;



    (*listsize)++; // increase the length by one

    list = new char[*listsize];



    counter = 0;

    /* copy the old list into the new (longer) list

    */

    while (counter < ((*listsize)-1)){

      list[counter] = templist[counter];

      counter++;

    }

    list[counter] = newchar;



    delete [] templist;



    /*

    ** Temporary code to test the function...

    *

    counter = 0;

    cout << "List is now " << *listsize << " long: ";

    while (counter < *listsize){

      cout << list[counter] << ',';

      counter++;

    }

    cout << endl;

    */



    cin >> newchar; // read in the next char and check for '%'

  }



  return list;

}



void CheckNeighbours(const char list[], int listsize, int * i1, int * i2){

  /* Compare the neighbours of each letter in the list with each element

  ** in the list (including itself). If a match is found in the list

  ** then implicitly return the indexes of both it and its its neighbour.

  ** Otherwise, set both indexes to -1 to indicate no neighbours found.

  ** We choose to assume that case is important, so that uppercase 'C'

  ** is not a neighbour of 'd'.

  ** We also assume that list[] contains only valid letters.

  */

  int firstindex;         // index to tested letters

  int counter;            // index to its potential neighbours

  bool found;             /* have we found neighbours? This is used

                          ** to break out of the loop as soon as the

                          ** first is found.

                          */



  firstindex = 0; // start searching from the beginning of the list

  found = false;

  while ((firstindex < listsize) && !found){

    /* Check if the its neighbours also exists in list[]. Start

    ** searching from the beginning of list.

    */

    counter = 0;

    while ((counter < listsize) && !found){

      if ( char(int(list[firstindex])-1) == list[counter] ||

           char(int(list[firstindex])+1) == list[counter] ){

        found = true; // stop when the first is found

      }

      counter++;

    }

    firstindex++;

  }

  counter--;      // Will have been incremented once too often

  firstindex--;   // Will have been incremented once too often



  if (found) {

    *i1 = firstindex;

    *i2 = counter;

  } else {

    *i1 = -1;

    *i2 = -1;

  }

}



void main(void){

  int i1, i2;         // Indexes of the neighbouring letters

  char * list = NULL; // The list

  int listsize = 0;   /* Size of the list (zero before the user

                      ** enters any letters)

                      */



  list = ReadChars(&listsize);



  CheckNeighbours(list, listsize, &i1, &i2);



  if (i1 >= 0){

    cout << endl << "Letters " << list[i1] << " and " << list[i2];

    cout << " appear next to each other alphabetically." << endl;

  } else {

    cout << endl << "No letters appear next to each other ";

    cout << "alphabetically." << endl;

  }



  delete [] list; /* This is not needed here, but it's

                  ** good programming practice to explicitly free

                  ** memory (i.e. delete) if one explicitly allocates

                  ** it (i.e. with new).

                  */



}