Assignment 3

Parameterized Vector Class(es) and Linear Independence

Due Date: Friday, March 1, 2019 at class time

Required for submitting:

• Grade Sheet Print this sheet and bring it to class the day the program is due.

• Bring your UML diagram to class. Note: you've already handed in your very last hand-drawn UML diagram

Purpose:

• The purpose of this exercise is to give you more practice with the first few items listed below. In addition to these, we will revisit a topic or two you saw in your Cs 228 course (or equivalent, if you transferred credit). I want you to have some experience coding the necessary constructs using the OOP paradigm for some basic vector analysis, too. You might recall studying Jacobi and/or Gauss-Seidel iteration to solve a linear system of linear equations? Ok, maybe not. But you can read; I suggest you start now by reviewing this topic. I will describe Jacobi iteration in class for you. As for the vector analysis, I will be covering topics there in the lectures for the next week or more. I'll describe below what you will be doing in this realm.

  1. templated classes

  2. templated functions

  3. overloading operators

  4. the STL; in particular, the vector class

  5. the concept of possibly implementing algorithms as classes

Resources:

• UML Quick Reference

• Documentation for the Standard Template Library

• Unix help This is an S&T help site for the basics of Unix.

The Concept:

• • It is common in mathematics that n-tuples of values are used. You see this in just about every branch of scientific investigation. This is the reason we spend so much time in our classes studying vectors and arrays. Now, one of the key questions when working with a set of vectors of real numbers is whether or not they are linearly independant. This is a key concept as a set of linearly independent vectors forms a basis (a set of basic building blocks) for the vector space spanned by this set. (We'll talk about this in class in the coming week.) We define linear dependence of a set of non-zero vectors

  • S = {v₁, v₂, .... ,v_n}

• as follows: S is linearly dependent if there exist real constants α₁, α₂, ... ,α_n not all zero such that

  • α₁v₁ + α₂v₂ + ...+ α_nv_n = 0

• Furthermore, S is linearly independent if the only solution to the above equation is α₁ = α₂ = ... = α_n = 0. An alternative way of stating this is: if any one of the vectors v_k can be written as a linear combination of the other vectors, then the set is linearly dependent. What this means is that for, say v_k, there are constants β₁, β₂, etc. such that

  • v_k = β₁v₁ + β₂v₂ + ... + β_jv_j, for some j != k.

• Well, this is the characterization of linear dependence/independance that you are going to use for coding as a part of this assignment. For a given set, S, of n-dimensional vectors, you will code functionality to determine whether the set is linearly dependent or not. You will do this by systematically searching for a member of the set that can be formed by other members of the set. You will do this: Start with two vectors from S (say, v₁ and v₂)and see if they are linearly dependent. This is easy; just see if one is a multiple of the other. You can work out the details of that part. If so, then you have determined that this subset of S is linearly dependent, thus S is linearly dependent and you're done. If not, consider those two along with a third one from S (say, v₃) and see if the third can be written as a linear combination of the first two. This is bit more difficult. You need to determine whether there exist constants α₁ and α₂ such that

  • α₁v₁ + α₂v₂ = v₃ (1)

• You accomplish this in two steps: First solve the 2 x 2 system α₁u₁ + α₂u₂ = u₃, where u_k contains the first two components of v_k. Since you haven't yet developed your matrix classes yet, you can't use gaussian elimination and so you will do this using Jacobi or Gauss-Seidel iteration. You did this in CS 228 and can review it. I'll also discuss it in class briefly. Now, if that iteration converges, the second step is to see if those constants α₁ and α₂ satisfy equation (1) above. If so, then that subset of S is linearly dependent and so S is also and you're done. If not, add v₄ to your list and start again. This time you are looking for three constants that will solve

  • α₁v₁ + α₂v₂ + α₃v₃ = v₄

• which will involve solving a 3 x 3 system using Jacobi iteration. [Note: These α's will be different from the ones above.] You continue this process until you have found a vector that is a multiple of the vectors before it or until you run out of vectors! If that happens, then you can conclude that, within the computational tolerances you set, that set is linearly independent.

Program Specifications:

• • You will start by writing a templated vector class. For your vector class, I suggest that you start with the text authors' array class and add functionality you think appropriate. It is mandatory to have the following:

  • overloaded operators +, - binary, - unary, * dot product, [ ], =

  • appropriate constructors

  • stream operators << and >>

• You will write function classes to perform the above operations. How? You decide an appropriate structure for your program. Sit back tonight with a tall glass of warm milk and a cookie and use your UML to design a really awesome program. You will need a vector of your vectors. You decide whether using the STL vector class or array class or your vector class is to contain your set of vectors.

  • Among other considerations for this assignment, you will have to give attention to memory dynamics -- the allocation and use of that very resource. Consider how you will use memory, how you will program your vector class, how STL vectors use memory, etc.

  • Again, I want you to have your program read in data from a file. Some data to run your program on is: input_dataset3. The format of the file is this: the first number is an integer giving the dimension of the vectors to follow. You can assume that the number of vectors in the set is the same as the dimension of the vectors. Whitespace separates each value. You can also assume that your program will be tested on double precision data.

  • Use command line arguments (argc and argv[ ]) to give the user (you and the grader) the ability to pass a file name to the program for reading in data.

  • Your program is to output the following:

    1. a testing of your vector class that includes:

       • the sum, difference, and dot product of the first two vectors in the data set read in

       • demonstration of your output stream operator

       • demonstration of your [ ] operator

• 1. the determination of linear independence or not

  2. if they are linear dependent, the linear combination that you found among the set of vectors

  3. the tolerance used in your Jacobi or Gauss-Seidel iteration process

Deliverables:

1. Code: We will test that the code you submit does indeed compile and run. You are to submit in the usual way.

2. makefile: Supply the makefile which compiles and builds your program as detailed above. I really suggest that you play around with and use the third of the makefiles I posted.

3. Your gradesheet and UML (during class)