Computing Concepts with C++ Essentials
Laboratory Notebook
Chapter 9 - Vectors and Matrices

Cay S. Horstmann
Geof Pawlicki

Computing Concepts with C++ Essentials Laboratory Notebook
Chapter 9 - Vectors and Matrices


Your name:
Your email address:
Your student ID number:

Once this form has been customized for your institution, you can use this button to send your lab work. Be sure to read the instructions before starting your work.


Lab Objectives

To gain experience with

P1. Vector Subscripts

In the text, we have frequently used the rand_int function to generate random integers. For example, rand_int(1, 6) generates random numbers between 1 and 6, simulating the throw of a die. In this lab assignment, you will use a vector to test whether the random generator is fair, that is, whether each possible value is generated approximately equally often.

Your program should ask the user

Make a vector with high - low + 1 elements, one for each possible outcome. Set each element to 0. Then keep calling the random number generator. If it returns a value v, then increment the counter belonging to v. There is just one catch. The random numbers are generated in the range low...high. The vector subscripts fall in the range 0...high - low. Therefore, you need to shift the ranges: the vector element corresponding to the random value v has subscript v - low.

After all numbers have been generated, print the counters. Here is a typical program run:

How many numbers do you want to generate? 1000
What is the low value? 1
What is the high value? 10
1    78
2   101
3   118
4    97
5   103
6   102
7   112
8    91
9    94
10  104

P2. Using Vectors to Collect Data Items

Vectors are frequently used to store and provide random access to a collection of objects of like type. In the following lab program, you will generate random circle objects and store them in a vector. If a circle does not intersect any of the previously stored circles, you will add it to the vector. Finally, display all circles that you collected in the vector. The result should look something like this: (Note that none of the circles intersect.)

Randomly generated non-overlapping circles

Use the code of the circle_intersect function that is given below to test whether two circles intersect. To randomly generate a circle, simply pick random x- and y- positions between -10 and 10 for the center and a random radius between 0 and 1. You need to compare each newly generated circle with all other circles before you can add it. (For that reason, we need a vector to hold all circles.) If the new circle passes the test, use push_back to add it to the end of the vector.

#define CCC_WIN
#include "ccc.h"

bool circle_intersect(Circle c1, Circle c2)
/* PURPOSE: Test if two circles intersect
            (distance between centers is less than sum of radii)
*/
{  if ( (c1.get_radius() + c2.get_radius()) < 
         sqrt( pow((c2.get_center().get_x() - 
                    c1.get_center().get_x()),2) + 
               pow((c2.get_center().get_y() - 
                    c1.get_center().get_y()),2)))
      return false;
   else
      return true; 
}

int main()
/* PURPOSE: Program to plot a finite number of non-overlapping, 
            randomly sized circles.
*/
{  vector<Circle> rand_circles;
   int max_circles;
   float rand_radius;
   float x,y;
   Point rand_center;
   Circle c1;
   bool intersect;

   max_circles = cwin.get_int("How many random circles would you like to see ? ");
   
   /*
      YOUR WORK GOES HERE
   */

   return EXIT_SUCCESS;
}

P3. Return Parameters and Return Values

As with any other data type, when passing a vector as a parameter to a function, you need to choose between "pass by value" and "pass by reference". If vector elements are being changed in the function, pass the vector as a reference parameter, for example, vector<Employee>& empl. If the vector's contents aren't going to be changed, then pass it as a value, vector<Employee> empl, or, for greater efficiency, as a const reference paramter, like vector<Employee> const& empl.

Copying an entire vector into a function can be expensive. Similarly, returning an entire vector as the result of a function can be expensive. Rewrite (and re-comment) the following function into a procedure that accepts a reference parameter and updates that parameter instead of returning a new vector as the result. Supply a main function that tests your function.

/* PURPOSE:  procedure to reverse elements in an integer vector
   RECEIVES: int_values - a vector of integer values
   RETURNS:  a copy of the vector, with the elements reversed
*/   
vector<int> reverse(vector<int> int_values)
{  int temp;
   vector<int> result(int_values.length());
   

   for(i = 0 ; i < int_values.length(); i++)
       result[int_values.length() - i - 1] = int_values[i];
   
   return int_values;
}

P4. Simple Vector Algorithms -

Consider finding an average grade from a sequence of 7 grades where the lowest and highest scores are discarded. Using the methods for Finding a Value, Counting, Collecting Matches and Deleting and Element given in the text, write a program to locate the max and min values in 87, 95, 90, 76, 43, 80, 84, discard them, and compute the average of the remaining scores.

How does your program handle duplicate grades ? For example, how would it process 95, 95, 95, 80, 78, 68, 68? What do you think it should do?


P5. Avoiding Parallel Vectors

Write a program that reads in the names and scores of students and displays the names of the students with the highest and lowest score.

A simple method of carrying out this task would be to have two parallel vectors

vector<string> names;
vector<int> scores;

However, you should avoid parallel vectors in your solution.


P6. Vectors as Object Data

Modify polygon.cpp to allow the interactive drawing of an irregular polygon. Use cwin.get_mouse(string) to collect mouse clicks. Stop collecting mouse clicks when the user clicks again on (or very near) the first point. Immediately after each mouse click, draw vertex points, and finally display the entire polygon, like this:

Polygon with user specified number and located of vertices

#define CCC_WIN
#include "ccc.h"

class Polygon
{
public:
        Polygon();
        void read();
        void plot() const;
private:
        vector<Point> corners;
};

Polygon::Polygon()
{
}

void Polygon::read()
{  /* your work here */
}

void Polygon::plot() const
{  int i;
        int n = corners.size();
        for (i = 0; i < n; i++)
                cwin << Line(corners[i], corners[(i + 1) % n]);
}

int main()
/* PURPOSE: Program to collect user input mouseclicks to use as the 
            vertices of an irregular polygon
*/            
{  int i;
   Point new_point
   Polygon poly;
 	
   poly.read();
   poly.plot(); 
	
   return EXIT_SUCCESS;
}


P7. Defining and Using Matrices

Vectors store a linear arrangement of values, accessed by a single index. Matrices store a tabular arrangement of values, accessed by two indexes, for example matrix[i][j], where i is the row index, and j is the column index..

Crosswords are a type of puzzle which have letters in common. For example,

          d
       across
          w
          n

share the letter 'o'.

Write a program that will accept a list of words into a vector of strings, then make a 20 x 20 matrix (of strings of length 1) that contains a crossword puzzle with these words.

For example, your program when given the list addle, apple, clowning, incline, plan, burr it displays it as:

   addle
   p   
   p   
  clowning
   e   n
       c
       l
       i
    plan
       e

That is, use the following method: Place the first word horizontally in the center of the top row. Place the next word vertically. Check if there is a common letter with the preceding word, and if all the squares into which you want to place that word are still empty. (If you can't place it, skip the word.) Then switch back to horizontal, place the next word if possible, and so on.


Don't forget to send your answers when you're finished.