Take Home Part of the Final Exam
Do THREE of the four questions and bring your solutions to
the final exam on Monday, June 8. This will make up 30% of your final exam
score. We talked about Markov Chains in class. For the other three, you have to
do your own research. You can ask me or Kolya general
questions about the topic and ask for other examples, but you have to do the
problems on your own. Feel free to search online for similar examples. There
are some suggested references below for each topic. I also put some books on
reserve at the Odegaard Library.
Markov Chains
Markov Chains are designed to model systems that change from
state to state. In particular, the current state should depend only on the
previous state. Here, linear algebra is used to predict future conditions.
Key Words: Stochastic
process, Markov chains, Transition probabilities, State vectors, Steady-state
vectors.
Suggested References:
http://aix1.uottawa.ca/~jkhoury/markov.htm
Introductory Linear Algebra
with Applications, Bernard Kolman, 4th Ed.
Question:
John is either happy or pouting (a simple soul, our John). If he is happy one
day, he is happy the next day four times out of five. If he is pouting one day,
the chances that he will also pout the next day are one time out of three. Over
the long term, what are the chances that John is happy on any given day?
Linear
Programming
Linear programming is
concerned with maximizing or minimizing a certain quantity (like cost) whose
variables are constrained by various linear inequalities. Linear programming is
applicable to many problems in industry and science. In this project, you’ll
learn about the simplex method for solving such problems.
Key
Words: Max-min problems, Feasible solution/region, Optimal
solution, Decision variables, Objective function, Constraints, Simplex method,
Standard Form, Slack variables.
References:
http://aix1.uottawa.ca/~jkhoury/programming.htm
Introductory Linear Algebra
with Applications, Bernard Kolman, 4th Ed.
Questions:
There are two here. One to set up. One with easier numbers to solve. You have
to do both if you choose this section.
1. Seven
patients require blood transfusions. We assume four blood types: A, AB, B, and
O. Type AB is called the universal recipient; type O is called the universal
donor. The blood supply and patient data is as follows:
|
|
The problem is to ensure that
each patient receives the required amount of the proper type of blood and to
use the existing supply so that the cost of replacement is minimized. Formulate
this as a linear programming problem, but don’t actually solve it. Label the
decision variables, objective function, and constraints.
2. Solve
the following linear programming problem using the simplex method:
Minimize subject to
|
|
|
Cryptography
The study of encoding and
decoding secret messages is called cryptography. Codes are called ciphers,
encoded messages ciphertext, and uncoded
messages plaintext. The process of converting to from plaintext to ciphertext is called enciphering, while the reverse is
called deciphering. This question is about the Hill cipher which uses linear
algebra.
Key
Words: Enciphering, Deciphering, Modular Arithmetic, Linear
Transformations, Hill n-cipher,
digraph.
Suggested
References:
Kenneth H. Rosen, Elementary Number Theory and Its Applications, 1992.
http://practicalcryptography.com/ciphers/hill-cipher/
Question: In order
to increase the difficulty of breaking your cryptosystem, you encipher you
messages using a Hill 2-cipher by first applying the matrix working modulo 26 and then applying the matrix
modulo 29. Thus, while your plaintexts are in
the usual 26 letter alphabet with A=0 and Z=25, your ciphertexts
will be in the alphabet with 0-25 as usual and ∑=26, Ω=27, and J=28.
(a) Encipher the message SEND.
(b) Describe how to decipher a ciphertext by applying
two matrices in succession, and decipher “ZMOY”.
(c) Under what conditions is a matrix with entries module 29 invertible modulo
29?
Game Theory
Game theory is used to model
2-person (or 2-player) games requiring the same decisions to be made at each
step. Furthermore, these decisions may result in payoffs or penalties for each
player at each step. In such situations, it is often possible for each player
to formulate a strategy which will maximize their return. Linear algebra can be
used to describe this situation.
Key
Words: Two person zero-sum game, Payoff matrix, Strategy,
Expected payout, Optimal strategy, Value of a game, Saddle point, Fundamental
theorem of a 2-person zero-sum game.
Suggested
References
Introductory Linear Algebra
with Applications, Bernard Kolman, 4th Ed.
http://www.math.harvard.edu/archive/20_spring_05/handouts/zero_sum_games.pdf
Question: Two
clothing stores in a shopping center compete for the weekend trade. On a clear
day the larger store gets 60% of the business and on a rainy day the larger
store gets 80% of the business. Either or both stores may hold a sidewalk sale
on a given weekend, but the decision must be made a week in advance and in
ignorance of the competitor’s plans. If both have a sidewalk sale, each gets
50% of the business. If, however, one holds the sale and the other doesn’t, the
one conducting the sale gets 90% of the business on a clear day and 10% on a
rainy day. It rains 40% of the time. How frequently should each retailer
conduct sales?