CS211 - Algorithms and Data Structures II

Department of Computer Science, NUIM



T Naughton, CS NUIM

Solutions for Tutorial 1







Problem T1.4



void findduplicates(int * list, int len, int * dup1, int * dup2){

  /*

  ** This function finds the indexes of the first two duplicates

  ** found in the list. 'list' is an integer array of length 'len'.

  ** If no duplicates set indexes to -1

  */

  int check;   /* checks each element in sequence */

  int counter; /* cycles through the list */

  bool found;  /* have we found a duplicate yet? */



  *dup1 = -1;

  *dup2 = -1;

  found = false;

  check = 0;

  while ((check < len) && (!found)){

    /*

    ** Compare list[check] with each element that appears after it

    ** in the list and stop as soon as one is found

    */

    counter = check + 1;

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

      if (list[check] == list[counter]){

        *dup1 = check;

        *dup2 = counter;

        found = true;

      }

      counter++;

    }

    check++;

  }

}







Problem T1.5



#include<iostream>



void getinputs(int * list, int len);

void findduplicates(int * list, int len, int * dup1, int * dup2);



/*

** This program inputs a list of integers from the user and outputs the

** first occurance of duplicates in the list.

*/



void getinputs(int * list, int len){

  /*

  ** This function reads 'len' integers into array 'list'

  */

  int counter;



  cout << endl << "Please enter the " << len << " digits, one per line:";

  cout << endl;

  counter = 0;

  while (counter < len){

    cin >> list[counter];

    counter++;

  }

  cout << endl << "Thanks!" << endl;

}



void main(void){

  int * list = NULL;

  int len = 0;

  int dup1 = -1; // The indexes of the duplicates

  int dup2 = -1;



  cout << endl << endl << "How many integers will you enter?" << endl;

  cin >> len;



  list = new int[len];

  getinputs(list, len);



  /* test *

  int counter = 0;

  cout << endl << "List: ";

  while (counter < len){

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

    counter++;

  }

  */



  findduplicates(list, len, &dup1, &dup2);

  if ((dup1 == -1) && (dup2 == -1)){

    cout << endl << "No duplicates found." << endl;

  } else {

    cout << endl << "Duplicate " << list[dup1] << " and " << list[dup2];

    cout << " found at locations " << dup1 << " and " << dup2;

    cout << ", respectively." << endl;

  }



  delete [] list;

}