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:

Type

Supply

Cost per Pint

A

7 pts.

$1

AB

6 pts.

$2

B

4 pts.

4$

O

5 pts.

$5

Patient

Blood Type

Needs

1

A

2 pts.

2

AB

3 pts.

3

B

1 pts.

4

O

2 pts.

5

A

3 pts.

6

B

2 pts.

7

AB

1 pts.

 

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?