CS XXXXXXXXXXAsst 1 Assignment 1 CS 1027 Computer Science Fundamentals II Due date: Wednesday, February 8 at 11:55 pm Learning Outcomes In this assignment, you will get practice...

CS XXXXXXXXXXAsst 1
Assignment 1
CS 1027
Computer Science Fundamentals II



Due date: Wednesday, Fe
uary 8 at 11:55 pm
Learning Outcomes
In this assignment, you will get practice with:
 Creating classes and their methods
 A
ays and 2D a
ays
 Working with objects that interact with one another
 Conditionals and loops
 Implementing linear alge
a operations
 Creating a subclass and using inheritance
 Programming according to specifications
Introduction
Linear alge
a is an important subject in mathematics, but also in computer science and a
variety of other areas. One of the fundamental structures in linear alge
a is the matrix: a 2-
dimensional table of numbers organized in rows and columns.
[
8 14 2
5 3 12
1 7 9
15 6 4
]
Figure 1. A matrix with four rows and three columns.
Matrices are useful in many different areas to represent data in a table-like structure. A benefit
of using matrices to store the data is that they have several standard operations for making
computations on the data. For example, multiplying two matrices together is an important
operation in many different applications including computer graphics, solving linear equations,
modelling of data (money, population, etc.), and much more.
Another structure in linear alge
a is called a vector. Vectors are special types of matrices that
have only 1 row or only 1 column, meaning they are 1-dimensional rather than 2-dimensional.
So vectors are similar to a
ays and matrices are similar to a
ays of a
ays, or 2-dimensional
a
ays.
Matrices and vectors are also used in structures called Markov chains to make predictions
about the future based on historic patterns. This approach requires that there are a finite
number of independent "states" of which one or more must be active at all times, and that there
are known probabilities of transitioning from one state to itself or to another state. For example,
suppose you have exactly 3 possible states in your life: sleeping, eating, and working. You can
transition from sleeping to sleeping, sleeping to eating, sleeping to working, eating to sleeping,
and so on. You can never be stateless nor in a state other than the specified ones for this
Assignment 1
CS 1027
Computer Science Fundamentals II



model. If this is confusing, do not wo
y. This assignment is not really about Markov chains, but
we give you some background information so you can see how the code you will work on could
e used in applications.
The probabilities of the state-to-state transitions are based on historic data and they are stored
in a matrix called a transition matrix. The states are stored in a vector called the state vector.
The state vector might store the value 1 in one of its entries and the remaining entries could
have value 0, but it also could contain different values in all its entries as long as these values
add up to 1 (i.e. [0.3, 0.6, 0.1]).
Given the initial state of a system modelled with a Markov chain, we can predict what the state
will be after one time unit (i.e. day, or month, or year depending on the system being modelled)
y multiplying the transition matrix by the state vector. We can predict what the state will be
after two time units by multiplying the transition matrix by itself and them multiplying that
esulting matrix by the state vector. We can predict what the state will be after n time units by
aising the transition matrix to the nth power (multiplying it by itself n times) and then multiplying
the resulting matrix by the state vector, thus allowing us to predict future states simply with the
state vector and transition matrix.
Figure 2. An example of a Markov chain with 3 possible states, S (sleeping), E (eating), and
W (working), and the probabilities of transitioning between states.
[
? ?? ? ? ?? ? ? ?? ?
? ?? ? ? ?? ? ? ?? ?
? ?? ? ? ?? ? ? ?? ?
] = [
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
]
Figure 3. The transition matrix representing the probabilities shown
in the Markov chain diagram from Figure 2.
Assignment 1
CS 1027
Computer Science Fundamentals II



Suppose you are cu
ently working. The state vector would be:
[???????? ?????? ???????] = [0 0 1]
The first two entries of the state vector are zero, because you are not sleeping (so the
probability that you are sleeping is zero) and you are not eating.
We can predict what your next state will be after one unit of time, i.e. in an hour, by multiplying
the state vector by the transition matrix. This operation produces a vector representing the
probability of being in each state. Notice in Figure 4 that the resulting state vector is the same
as the bottom row of the transition matrix – this is because the state vector had 0's in the first
two entries and a 1 in the last entry. In state vectors that have different values in all their entries
(not just one 1 and some 0's), the resulting vector will not necessarily be identical to a row from
the transition matrix.
[0 0 1] × [
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
] = [ XXXXXXXXXX]
Figure 4. The calculation of probabilities of your states after one time unit.
We can also predict what your state will be in two units of time, i.e. in two hours, by multiplying
the transition matrix by itself and then multiplying the state vector by that produced matrix:
[0 0 1] × [
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
] × [
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
] = [ XXXXXXXXXX]
Figure 5. The calculation of probabilities of your states after two time units.
Classes to Implement
For this assignment, you must implement three (3) Java classes: Matrix, Vector, and
MarkovChain. Follow the guidelines for each one below.
In these classes, you may implement more private (helper) methods if you want. However, you
may not implement more public methods except public static void main(String[] args) for testing
purposes (this is allowed and encouraged). You may not add instance variables other than the
ones specified in these instructions nor change the variable types or accessibility (i.e. making a
variable public when it should be private). Penalties will be applied if you implement additional
instance variables or change the variable types or modifiers from what is described here.
Assignment 1
CS 1027
Computer Science Fundamentals II


Matrix.java
This class is used to represent a matrix containing double (i.e. decimal) numbers.
The class must have exactly (no more and no less) the following private instance variables:
 private int numRows
 private int numCols
 private double[][] data
The class must have the following public methods:
 public Matrix (int r, int c): constructor
o Initialize the instance variables numRows and numCols and initialize data to
have r rows and c columns
 public Matrix (int r, int c, double[] linA
): constructor
o Same as above, but now you have to populate the 2-dimensional a
ay data with
the elements in linA

o Note that linA
is a 1-dimensional a
ay whereas data is 2-dimensional, so you
have to map the items from linA
to data. The first values from linA
must be
copied in left to right order across the first row of data, the following values of
linA
must then be copied to the second row, and so on. For example, [1, 2, 3, 4]
would be put into a 2 by 2 a
ay with [1, 2] in the first row and then [3, 4] in the
next row.
 public int getNumRows()
o Return the number of rows in the matrix
 public int getNumCols()
o Return the number of columns in the matrix
 public double[][] getData()
o Return the 2-dimensional a
ay containing the matrix data
 public double getElement(int r, int c)
o Return the value from data at row r and column c
 public void setElement(int r, int c, double value)
o store value at row r and column c of data
 public void transpose()
o Transpose the matrix and update the instance variables to store the transposed
matrix as the new instance of 'this' matrix (* see explanation below about how to
transpose a matrix *)
 public Matrix multiply (double scalar)
o Create a new Matrix object with the same dimensions as 'this' matrix.
o Multiply each value in 'this' matrix by the given scalar and insert the resulting
values into the new Matrix object and return it (* see explanation below *)
 public Matrix multiply (Matrix other)
Assignment 1
CS 1027
Computer Science Fundamentals II



o If the number of columns of 'this' matrix is not equal to the number of rows of
other matrix, return null immediately.
o If the above condition is not true, create a new Matrix object with the number of
ows from 'this' and the number of columns from other.
o Multiply 'this' Matrix object by other and insert the resulting values into the new
matrix object and return it. (* see explanation below *)
 public String toString()
o If the matrix data a
ay is empty, return "Empty matrix"
o Otherwise, build a string containing the entire matrix following the format shown
elow and return that string (* see explanation below *)
Transposing a Matrix
Given a matrix M, transposing M into matrix N means reflecting all the elements from M along
the diagonal to go into N. In other words, the first row of M becomes the first column of N, the
second row of M becomes the second column of N, and so on, thus N[i][j] = M[j][i] for all i,j
indices. This means the number of rows and columns must be swapped.
Example:
[
8 12
3 7
19 5
]
?????????
⇒ [
8 3 19
12 7 5
]
Matrix-Scalar Multiplication
When multiplying a matrix by a scalar (single number), each number in the matrix must be
multiplied by that scalar. The resulting matrix is the same size as the original matrix and each
number is just multiplied by that scalar's value.
Example:
3 × [
3 0
2 1
]
= [
3 × 3 3 × 0
3 × 2 3 × 1
]
= [
9 0
6 3
]
Matrix-Matrix Multiplication
Multiplying two matrices together can only be done if the number of columns of the first matrix
(this) is equal to the number of rows of the second matrix (other). Consider 2 matrices A and B
satisfying the above condition and let M be the matrix obtained by multiplying A and B. The
Assignment 1
CS 1027
Computer Science Fundamentals II



entry M[i][j] is obtained by multiplying the i-th row of A with the j-th column of B. To multiply a
ow r with a column c we add the products r[i] all the values forx c[i] stored in r and c, so
?[?][?] = ∑ ?[?] × ?[?]
?−1
?=0

where n is the number of values in row r and column c. For the example below, the top-left
value in the resulting matrix will be calculated by multiplying the top row of the first matrix [3, 0]
y the left column of the second matrix [7,4] (vertical vector) so we multiply 3 by 7 and then 0 by
4 and add them together to get 21. For the top-right element, we multiply the top row of the first
matrix by the right column of the second matrix: 3 x 2 + 0 x 3 = 6.
Example:
[
3 0
2 1
] × [
7 2
4 3
]
= [
3 × 7 + 0 × 4 3 × 2 + 0 × 3
2 × 7 + 1 × 4 2 × 2 + 1 × 3
] = [
21 6
18 7
]
Matrix toString Format
When returning the string for a non-empty matrix in the toString() method, you must format it in
a specific way. Each value in the matrix must be converted to a string of exactly 8 characters
(that includes numbers, decimal point, and spaces needed to complete 8 characters) in which
the number of decimal digits is exactly 3.