### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# DISCRETE MATH MODEL MATH 381

UW

GPA 3.76

### View Full Document

## 43

## 0

## Popular in Course

## Popular in Mathematics (M)

This 148 page Class Notes was uploaded by Addison Beer on Wednesday September 9, 2015. The Class Notes belongs to MATH 381 at University of Washington taught by Timothy Chartier in Fall. Since its upload, it has received 43 views. For similar materials see /class/192077/math-381-university-of-washington in Mathematics (M) at University of Washington.

## Reviews for DISCRETE MATH MODEL

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/09/15

Monte Carlo Simulation Tim Chartier University of Washington Math 381 Tim Chartier Monte Carlo Simulation 7 1 L Sa i 7 Computers can process huge amounts of data far beyond the capabilities of a human or group of people Computing Division Veterans Bureau Washington DC early 19203 At least 30 workers photographed using Burroughs electric adding machines to compute bonuses for World Warl veterans Tim Chartier Monte Carlo Simulation Finding enin in the 0 s an1 s 0 Let s generate random numbers and use these in a math model 0 We will use Monte Carlo methods which are essentially carefully designed games of chance 0 used effectively in a wide range of problems including physics mechanics and economics 0 developed by researchers working on the Manhattan Project during WWII o named after the famous Monaco casino town of Monte Carlo was created by John von Neumann and Stanislaw Ulam W Tim Chartier Monte Carlo Simulation Entering the Math Pub 0 Let us enter the Math Pub where all things mathematical but not necessarily physical can occur 0 We have a circular dart board with unit radius Then the area of the circle is A 7TI 2 7r 0 Now let us inscribe the circle in a square with an area of 4 as seen below Tim Chartier Monte Carlo Simulation Throwing Mathematical Darts 0 Suppose we randomly throw a dart at the board and we are guaranteed 0 to hit the board every time and 0 that we indeed throw it randomly somewhere on the board 0 Question What is the probability of a dart landing in the Circle 39 quot j I 4 39 Tim Chartier Monte Carlo Simulation Random Darts o How do we throw such darts mathematically 0 Pick random X and y such that 1 g Xy g 1 o This represents the coordinate Xy of our dart o How do we know if the dart is in the circle 0 Note that if xXZ y2 lt 1 then our dart is in the circle 39 quot j I k 39 Tim Chartier Monte Carlo Simulation Discrete Darts 0 Assume we are looking at a quarter of the Circle 0 Then the probability of throwing a dart in a quarter of the Circle is 7T4 0 Rather than Choosing random real numbers we will Choose numbers from 16 by rolling 2 dice 39 quot j I or 39 Tim Chartier Monte Carlo Simulation Dicey Challenge 0 Question How do we know if we are in the circle by looking at the two dice o Hint We want to approximate our underlying continuous probability as closely as we can 0 We have 36 outcomes with the dice and want n of these outcomes to represent landing in the circle and 36 n to represent not landing in the circle 0 Challenge Find n such that we approximately 7r4 as closely as we can 36 23111 2 a We will actually approximate Tim Chartier Monte Carlo Simulation 0 ae wee 63 999 oeaeeo 09099 00066 w Monte Carlo Simulation Continuous 7r 0 Suppose we do indeed pick random real numbers over and over and calculate 7r 0 What will we get Let s use a program to find out Here we are picking random X and y such that 1 g Xy g 1 as discussed earlier 0 Remember it depends on the random numbers Current estimate 71 m 3145 3 estimate 3 izzA 32 373 315 Aw w W www mun 2mm anon ADDU snug sum mun 33m anon 1mm number uHusses W Tim Chartier Monte Carlo Simulation Iyiulat 0 Note we aren t yet modeling We are computing probabilities We will use a similar idea to build a model in a coming lecture 0 Now let us look at a related application 0 Did you know that if you dropped a pencil on the Husky football field many times you could estimate 7r 0 How This is a method developed over 200 years ago Tim Chartier Monte Carlo Simulation Markov Chains steady state and eigenvalues Tim Chartier Department of Mathematics Math 381 Tim Chartier Markov Chains steady state and eigenvalues Announcement Wednesday s class will be in Communications B027 We will be using MATLAB Tim Chartier Markov Chains steady state and eigenvalues 0 A small town has only two dry cleaners Starch Cleaners and Spotless Cleaners 0 Starch Cleaners manager wants to increase business with an advertising campaign 0 A market research firm finds that after the marking campaign there is a 08 probability that a customer of Starchs will bring the next batch of dirty clothes to Starch and a 035 chance that a Spotless customer will switch to Starch for the next batch of clothes W Tim Chartier Markov Chains steady state and eigenvalues Transition Matrix This leads to the following transition matrix and transition diagram A 080 035 020 065 Tim Chartier Markov Chains steady state and eigenvalues iSf Ste if 0 Recall v1 Avo Av1 AAv0 A2v0 v3 Av2 AA2v0 A3v0 lt l vn1 Avn AAn 1v0 lql l l IVO7 0 Therefore v100 A100v0 o In MATLAB V100 would be found using the following command VlOO AAlOOkVO Tim Chartier Markov Chains steady state and eigenvalues Stpn39ace i 0 Last time we noticed that for large n 0 Moreover we are converging so that Av v 0 That is a time step leaves the percentages unchanged 0 This relationship means that the vector v is an eigenvector ofA with an eigenvalue of 1 W Tim Chartier Markov Chains steady state and eigenvalues Eigenvalue and eigenvector review 0 Let A be a square m X m matrix with real elements 0 Recall from linear algebra that a scalar value A is an eigenvalue of the matrix A if there is a nonzero vector v the corresponding eigenvector for which Av AV 0 If v is an eigenvector then so is ON for any scalar value a W Tim Chartier Markov Chains steady state and eigenvalues Carateristic polnomial o In general A has m eigenvalues A1 Am which can be determined by finding the roots of a polynomial of degree m in A 0 Why AvvgtA lv0 where I is the m X m identity matrix 0 Since v is a nonzero null vector of this matrix it must be singular Hence its determinant is zero detA Al o 0 Computing the determinant gives the polynomial W Tim Chartier Markov Chains steady state and eigenvalues To find the eigenvalues of H13 we can write detA l 12A 33A 1 A3 8 Solving the quadratic equation yields A 1or5 Tim Chartier Markov Chains steady state and eigenvalues A more complex example 0 Keep in mind that even real matrices can have complex eigenvalues 0 Consider the matrix 3 0 Then to find the eigenvalues we find detA l 1 3 8 A2 4A11 0 Setting this polynomial to zero we find AZ 282ii Tim Chartier Markov Chains steady state and eigenvalues Retuteampl 7 i i if 0 We know the eigenvalues of Al are 1 and 5 Let s find the eigenvectors associated with A 1 0 To find the eigenvectors associated with the eigenvalue A 1 find nonzero vectors v v1 v2T satisfying 1233Agtiigtrgt8gt 0 Using Gaussian elimination we find iilawmlal w Tim Chartier Markov Chains steady state and eigenvalues Exaect i 7 i 7 if 0 Again Gaussian elimination yielded 2 2 0 gt 2 2 0 4 4 0 0 0 0 39 0 Therefore the solution set consists of all vectors v such that 2V1 2V2 0 Le such that v2 v1 0 We can take v1 to have any nonzero value say v1 1 and then the eigenvector is 1 1T Tim Chartier Markov Chains steady state and eigenvalues Is this vector unique 0 Why does the Markov process converge to an eigenvector associated with the eigenvalue 1 0 Further is this even a unique eigenvector o The following theorem guarantees the uniqueness of the steady state vector and that it will have positive entries Theorem Perron Every real square matrix P who entries are all positive has a unique eigenvector with all positive en tries its corresponding eigenvalue has multiplicity one and it is the dominant eigenvalue in that every other eigenvalue has strictly smaller magnitude Tim Chartier Markov Chains steady state and eigenvalues Properti f transition matrics 0 Let M be a Markov transition matrix 0 Recall that the columns of M sum to 1 Therefore 1M 1 where 1 is the column vector of all ones 0 That is 1 is an left eigenvector of M associated with the eigenvalue 1 most notably for our purposes having all positive entries 0 Perron s Theorem ensures that 1 is the unique left eigenvector with all positive entries and hence its eigenvalue must be the dominant one o The right and left eigenvalues of a matrix are the same therefore 1 is the dominant left eigenvalue as well 0 So there exists a unique steady state vector v that satisfies vM v Normalizing this eigenvector so that Z v 1 gives a steadystate vector Tim Chartier Markov Chains steady state and eigenvalues 0 Still why does the Markov process yield this unique dominant eigenvector o The answer will be yes if M satisfies two conditions specified in the PerronFrobenius theorem 0 First the matrix must be irreducible This occurs if every state is reachable from every other state via a path in the transition diagram 0 We have this which actually guarantees the second condition of the PerronFrobenius theorem 0 Therefore convergence is guaranteed Tim Chartier Markov Chains steady state and eigenvalues Convergto wht 7 i i 0 We have established convergence but not yet to what vector 0 In the development to come we will use the following A gtOasn gtooiflt1 A 1 forallnif 1 A gtooasn gtooifAgt1 Tim Chartier Markov Chains steady state and eigenvalues 7 eenvms i 7 0 Assume M has n linear independent eigenvectors 0 Thus for an arbitrary initial guess x0 such that foO 1 we can express it as a linear combination of the eigenvectors V1V2 vn of M x0 C1v1 02v2 Can Tim Chartier Markov Chains steady state and eigenvalues a a a a a a ff 0 After one iteration of the Markov chain x Mv0 c1Mv1 02Mv2 c Mvn C1 A1V1 l C22V2 l l CnAnVn o Multiplying again by M yields x2 Mx1 C1 A1 MV1 l C2A2MV2 l C3AnMVn C1 A1 2V1 l C222V2 l l vnn2vn Tim Chartier Markov Chains steady state and eigenvalues Estaln a Pater i 7 if 0 Therefore in general we have xk ka0 c11kv1 02A2kx2 Cnnkvn 0 Recall we know from Perron s theorem that A1 1 and A lt 1 fori gt 1 0 Therefore our Markov process will converge to c1v1 0 But 01 will equal 1 since Exfo 1 Tim Chartier Markov Chains steady state and eigenvalues Guaranteed convergence Therefore the Markov process is guaranteed to converge to the desired dominant eigenvector Keep in mind however that this assumes that the transition matrix is irreducible Further we also had the uniqueness of the steady state vector stemming from the entries of the transition matrix being positive Next time we will see examples that don t meet all these assumptions Tim Chartier Markov Chains steady state and eigenvalues Queuing Theory Tim Chartier Department of Mathematics Math 381 Tim Chartier Queuing Theory 7 1 Qg i 7 0 Today we use Monte Carlo simulation to model queues 0 Think of the various ways you wait in line on your feet in your car or on the phone 0 There are various types of queues 0 Independent lines such as a grocery store 0 Next available server such as an airport Tim Chartier Queuing Theory Our Mod 7 7 i if 7 We will model one line with one server 0 We will model customer arrivals as a Poisson process where a average rate of arrivals per minute and b average number of people served per minute also a Poisson process 0 This isn t the only option as another model would be to set some minimum service time plus a random length of time after that W Tim Chartier Queuing Theory Ceatig data i 7 7 7 0 Given a and b we want to know when people arrive and how long they are serviced as in Ross 0 One option is to break a day into N units and in each time unit determine if a customer arrived or not 0 Similarly we could also determine if a customer was finished being serviced in each time unit 2an i E i N N N 0 Note we would deal with how large to make N and how many experiments we need to get convergence of results 0 This is a lot of wasted computation as we have probabilities derived last class period that could produce this W Tim Chartier Queuing Theory Leaningnthe ininite i if i 0 So we lean on the infinite as N gt oo o What is the probability of the next arrival time larger than a time unit T 0 Keep in mind we are saying that starting at time 0 what is the probability based on a Poisson distribution that there are 0 arrivals by time T 0 From last time we see that Probability that interarrival time is larger than T e aT W Tim Chartier Queuing Theory Excuse edo 0 have the ti o How do we produce the times 0 Again Probability that interarrival time is larger than T eaT 0 Let us set r e aT 0 We find the time by solving for T lnr o In MATLAB this becomes r T rand lalogr Keep in mind these are interarrival times W Tim Chartier Queuing Theory Recall Ross 0 Similar to your homework out of Ross we can create an array of arrival times and an array of service times m arrival times m times 0 Then our task just like your homework is now to find the departure times for each customer W Tim Chartier Queuing Theory Closer look at queue m 0 Let us look at MATLAB code that performs this o Simple queuing theory simulation MMl queue Single server single queue 0 What is MMl l o M arrival times are exponential distribution or Markovian o M service times are Markovian o 1Qnmesenmr 0 Note this implies that other queues are possible to model which they are W Tim Chartier Queuing Theory queue m initialization Let us look at code that initializes the vectors for the code noust 1000 Notation at arrival time of a person joining the queue st service time once they reach the front ft finish time after waiting and being served o initialize arrays at zerosncustl ft zerosncustl W Tim Chartier Queuing Theory queue m arrival times With several comments removed let us look at the code that finds the arrival times Generate random arrival times r randncustl iat la logr atl iatl for i2zncust ati ati l iati end W Tim Chartier Queuing Theory queue m service times Similarly we find the service times The code below has several commenting statements removed r randncustl st lb logr Compute time each customer finishes ftl atlstl finish time for 1st customer for i2ncust compute finish time for each customer as the larger of arrival time plus service time if no wait finish time of previous customer plus service time if wait fti maxatisti fti lsti end o o o o W Tim Chartier Queuing Theory queue m ending commands Finally we tidy things up and find ending statistics that will aid in having a sense of the simulation s behavior totaltime ft at waittime totaltime st aveservicetime sumstncust avewaittime sumwaittimencust avetotaltime sumtotaltimencust Plot histogram of waiting times histtotaltime0520 W Tim Chartier Queuing Theory Runigth Coe i 7 0 Using queuem available on the course web page set 0 a 1 average rate of arrivalmin o b 15 average number of people servedmin o simulation runs for 1000 customers 0 Talk with a partner what can you interpret from the graphs below queue length vs time histogram ofwaiting times a 1 15 35B b 15 1 averagetotaltime 21487 3m average service time 06786 12 10 E E l lill lliil ii it ill lillilli llilii 1 El ZEI EIEI EU 2EE n Bun B mun Tim Chartier Queuing Theory queue length vs time histogram ofwaiting times a 1 15 35B b 15 1 averagetotaltime 21487 3m average service time 06786 12 in E E l l l l l l ill iiil i ll l llll llllilll lull l El ZUEI EIEI EDD EDD lEIEIEI lZEIEI 0 Note that the queue length can exceed 10 multiple times 0 Several people wait for over 8 minutes 0 Remember this is one run of a random process 0 We should run several more times to look for general patterns W Tim Chartier Queuing Theory Runigth code aain 0 Now we run again for the settings 0 a 1 average rate of arrivalmin o b 15 average number of people servedmin o simulation runs for 1000 customers 0 Talk with a partner what can you interpret from the graphs below what similar behavior do you see queue length vs time histogram ofwaiting times a 1 1 EEIEI mu Bun BEIEI mun average total time 22084 average service time 06693 IHlmllll ll H mm 2mm 3mm Tim Chartier Queuing Theory Observe and compare runs queue length vs time 2mm histogram ofwaiting times a 1 b 15 average total time 22084 average service time 06693 E l llillli 0 We again see queue lengths over 10 minutes multiple times 0 This time several people wait over 10 minutes 0 We may want to run 100 or 200 more times Ideas of how to do this without looking at the graphs every time W Tim Chartier Queuing Theory Changinrameers h 7 7 7 0 Now let us reduce b from 15 to 11 0 Note that this implies that service time is approaching length of interarrival times 0 What do you expect to see in the resulting data To change the code find the following line in queuem b 15 average number of people served and change it to b 11 average number of people served W Tim Chartier Queuing Theory Simulation results 0 Again our new settings are 0 a 1 average rate of arrivalmin o b 11 average number of people servedmin o simulation runs for 1000 customers 9 Do the results match your expectations queue length vs time 1 1 1 histogram of waiting times 1 1 1 1 1 12m average total time 62679 average service time 091675 D mm mm EDD Bun mun 12mm Tim Chartier Queuing Theory Sin esuls yet aain 7 i if a For a second run with the settings 0 a 1 average rate of arrivalmin o b 11 average number of people servedmin o simulation runs for 1000 customers queue length vs time histogram ofwaiting times EU a 1 EU 1130 b 11 25 a 1 U m 7 120 average total time 113831 1EE 15 7 average service time 088394 Tim Chartier Queuing Theory 0 Such results help to show how such queues may behave given the proper parameters 0 For example in the previous example decreasing your average service time will aid in your queue 0 Markov chain theory can also help determine these values In particular we find for a lt b the expected waiting time is 1b a w Tim Chartier Queuing Theory lprovinge model 7 i i i if 0 Our simple queue model assumed a single line and a single server 0 With a partner and write down answers to the following o What othertypes of queues could be modeled o What types of additions could be made to our simple model to make it more realistic of people waiting in line 0 This is the type of incremental thinking necessary for your final project Tim Chartier Queuing Theory Solving all Sudoku Puzzles with an IP formulation Tim Chartier Department of Mathematics Math 381 4 A m 11 339 39 4 Tim Chartier Solving all Sudoku Puzzles with an leormulation 78 52 8 6 4 5 1 939 8 4 2819 7 5 761 2 7 3 6 3 1 6 4 25 81 Rules Fill in the matrix so that every row column and 3 x 3 submatrix contains the digits 1 through 9 exactly once Each puzzle appears with a certain number of givens The number and location of these determines the games level of difficulty W Tim Chartier Solving all Sudoku Puzzles with an leormulation Mathecal 7 i 7 i i o The word Sudoku is a Japanese abbreviation for the phrase suji wa dokushin ni kagiru which translates as the the digits must remain single 0 The puzzles require logic to solve While the type of logic used solving puzzles is associated with mathematical thinking it is not soley a mathematical process 0 Sudoku puzzles have numbers but they could as easily be completed with a set of pictures 7 8 5 2 8 8 4 5 1 t i 8 i z 4 2 89 f7 5 7 6 1 2A 7 339 6 3 1 6 4 W Tim Chartier Solving all Sudoku Puzzles with an leormulation 0 Can we solve Sudoku puzzles with math That is can a mathematical process find the solution for us Yes can we sit back and let the mathematics once formulated work for us 0 Solution 1 Code a program to run through the logic that a person uses to solve the problem 0 Issue What if the programmer has yet to learn some level of logic that solves more difficult problems 0 Solution 2 Formulate the problem in a way that an exact solution if it exists will be found We will do this through optimization and linear programming W Tim Chartier Solving all Sudoku Puzzles with an leormulation A puzzli atrix 7 i o Sudoku most commonly appears in its 9 x 9 matrix form Rules Fill in the matrix so that every row column and 3 x 3 submatrix contains the digits 1 through 9 exactly once 0 Each puzzle appears with a certain number of givens The number and location of these determines the games level of difficulty 0 Let s try and formulate a 4 x 4 puzzle which is often used with younger children This can serve to aid us in developing our mathematics W Tim Chartier Solving all Sudoku Puzzles with an leormulation L39quote i Formulate an LP that solves a 4 x 4 Sudoku puzzle of the following form W Tim Chartier Solving all Sudoku Puzzles with an leormulation Decisions decisions 0 Step 1 Determine our decision variables What do we need to know when we are done We need to know where every number goes in the puzzle 0 What does this mean Let s consider the number 1 For every element in the 4 x 4 matrix we need to know if a 1 should be placed in that element of the matrix 0 Therefore your decision variables become X I if element i of the 4 X 4 contains integer k quotk 0 otherwise 0 Therefore we are actually formulating a binary integer program BILP to solve the puzzle W Tim Chartier Solving all Sudoku Puzzles with an leormulation 0 Now let us turn to our constraints These lie in the rules of the game 0 Rule 1 Fill in the matrix so that every column contains the digits 1 through 4 exactly once 0 This becomes the constraint 4 injk1j14k14 i1 W Tim Chartier Solving all Sudoku Puzzles with an leormulation Your Turn 0 Formulate the constraint for the following rule 0 Rule 2 Fill in the matrix so that every row contains the digits 1 through 4 exactly once W Tim Chartier Solving all Sudoku Puzzles with an leormulation YburThrn 0 Formulate the constraint for the following rule 0 Rule 2 Fill in the matrix so that every row contains the digits 1 through 4 exactly once This becomes the constraint 4 EWKL i14k14 j1 W Tim Chartier Solving all Sudoku Puzzles with an leormulation Submatrix constrint Rule 3 Fill in the matrix so that every 2 x 2 submatrix contains the digits 1 through 4 exactly once This becomes the constraint mg mp Z Z X39jk1 k 4p mq m jmq m1 imp m1 This is written in a general form If we have an n x n puzzle then n m2 This will help when we consider larger puzzles Tim Chartier Solving all Sudoku Puzzles with an leormulation A closer look 0 Let s take a closer look at this constraint where m 2 2q 2p 2 X39jk1 k14p12q12 j2q 21 i2p 21 o The variables p and q indicate the submatrices For a 4 x 4 puzzle we have 2 submatrices in each direction Let us consider the 11 submatrix Then p 1 and q 1 Therefore our double summation becomes 2 2 ZZXUKM k14 j1 i1 0 Now consider the 12 submatrix Then p 1 and q 2 and we have Ms Xijk21 k1394 i1 39 x H A Tim Chartier Solving all Sudoku Puzzles with an leormulation ff o i ff Let s take a moment and reflect We are almost done but 0 What constraints are left 0 What else do we need Tim Chartier Solving all Sudoku Puzzles with an leormulation 0 Every position in the matrix must be filled a We create this constraint in the BILP with n ZxUk1 i1nj1n k1 W Tim Chartier Solving all Sudoku Puzzles with an leormulation m39eiquot ii We also have the givens that are part of the initial Sudoku puzzle This is given by XIIk 1 for all ijk E G where G is the set correlating to the givens in the puzzle W Tim Chartier Solving all Sudoku Puzzles with an leormulation Finally we have an BILP so we have the constraint Xijk E 01 W Tim Chartier Solving all Sudoku Puzzles with an leormulation Maximize or minimize o If there exists any solutions that satisfy these constraints then we have a solution to our Sudoku puzzle so we actually don t need to concern ourselves with the function to optimize o MATLAB solves minimization problems so we will minimize gx OTx W Tim Chartier Solving all Sudoku Puzzles with an leormulation f quotP f f f i ff min 0Tx 4 suchthat injk 1 j14k14 i1 4 injk21i1i4k14 j1 2q 2p 2 Z xijk1 k14p12q12 j2q 21 i2p 21 I39I ZXijk 1 i1nj1nxjk 1 forallijk e G k1 Xin E 0 1 w Tim Chartier Solving all Sudoku Puzzles with an leormulation MATLB d 7 i 7 7 i o For an 4 x 4 puzzle we have 64 G constraints and 64 decision variables We will use MATLAB to help form these constraints and to solve the BILP 0 To simplify the discussion let s consider the 2 x 2 puzzle seen below 2 0 While this is not a Sudoku puzzle we can get a handle on some of the constraints with this small problem which has only 8 decision variables which is more manageable W Tim Chartier Solving all Sudoku Puzzles with an leormulation Converti o MALAB i i i 0 We will store our constraints in a matrix named Aeq Each row will correlate to a constraint 0 The number of columns in this matrix will be the number of decision variables We have 8 decision variables 0 We will organize our columns as the following 0 column 1 decision variable for whethera 1 appears in the 11 element 0 column 2 decision variable for whether a 1 appears in the 12 element column 3 decision variable for whether a 1 appears in the 21 element column 4 decision variable for whether a 1 appears in the 22 element column 5 decision variable for whether a 2 appears in the 1 1 element 0 and so on O 0 O W Tim Chartier Solving all Sudoku Puzzles with an leormulation Column constraint 0 Consider the constraint that every column contains the digits 1 through 2 exactly once There are 4 such constraints Each number 1 2 has a constraint for each of the 2 columns 4 injk1j12k12 i1 0 Assume we have set in MATLAB that Aeqzeros 4 nA2nA3 Then we can create these constraints with the command assuming n 2 for ilznA2 Aeqii lnlinonesln end W Tim Chartier Solving all Sudoku Puzzles with an leormulation A closer look for ilznA2 Aeqii lnlinonesln end Wi1thenAeqll2 onesl2andWiZthen Aeql34 onesl2SOWeget Aeq OOOOOOOOOOOOOOOI I OOOOOOOOOOOOOOOI I OOOOOOOOOOOOOOI O OOOOOOOOOOOOOOI O OOOOOOOOOOOOOI OO OOOOOOOOOOOOOI OO OOOOOOOOOOOOI OOO OOOOOOOOOOOOI OOO W Tim Chartier Solving all Sudoku Puzzles with an leormulation Movggtlt4 i 7 if ii We can pass this BILP into MATLAB but we need to pass in the givens for the puzzle Suppose we are solving the following puzzle1 3 2 1Note Tim Chartier created this puzzle so it s solution may not be unique 39 Tim Chartier Solving all Sudoku Puzzles with an leormulation 0 We will pass this into MATLAB with the following matrix 14 2 62 1 3 31 K34 gi 2 0 Each line in this matrix gives the row index column index and integer value respectively of each element appearing in the initial Sudoku matrix W Tim Chartier Solving all Sudoku Puzzles with an leormulation Your Turn 0 Download sudokum from the course web page 0 Run the program It will solve the 4 x 4 given in this lecture 0 Look at the code and how it implements the various constraints 0 Alter the code to solve the following puzzle 7 8 l5 2 8 6 i4 5 8 4 2 ale 7 l 211 if1 7 3i 6 3 1 is 4 2 l8 1 W Tim Chartier Solving all Sudoku Puzzles with an leormulation Sudoku quot 7 i 7 7 i o The Sudoku X puzzle is like the standard puzzle with an extra requirement the two long diagonals of the board must also contain each digit from 1 to 9 exactly once 0 Challenge Formulate the IP necessary to solve the Sudoku X puzzle below 2 W Tim Chartier Solving all Sudoku Puzzles with an leormulation Answer 0 The only additional requirements of a Sudoku X puzzle are that the two long diagonals have exactly one of each digit This results in 18 additional constraints two diagonals with nine digits each 0 To capture the requirement for the positive diagonal we add the nine constraints 9 Zxk1k19 r1 0 That is each number on the positive diagonal appears exactly once Similarly for the antidiagonal the following set of nine constraints are added 9 Zx10k 1 k 1 9 r1 0 As a result of these two additional constraints every digit must appear exactly once on each diagonal Tim Chartier Solving all Sudoku Puzzles with an leormulation Ranking Web Pages Tim Chartier Department of Mathematics Math 381 Tim Chartier Ranking Web Pages 0 Have a question Looking for an old friend Need a reference for a paper A popular and often effective form of information acquisition is submitting queries to Googlecom o In fact in January 2003 just over 1 200 searches would have been conducted in the past second 0 Google is a play on the word googol the number 10100 reflecting the company s goal of organizing all information on the World Wide Web Google Tim Chartier Ranking Web Pages GOOat a a a as 0 Suppose that we submit the query mathematics to Google 0 Why is the page we see at the top of the list deemed the best page related to the query 0 The web page listed first by Google is deemed loosely speaking the best web page related to the query 0 How is this page given such distinction W Tim Chartier Ranking Web Pages The Pank alorithm i i i o Developed by Google s founders Larry Page and Sergey Brin who were graduate students at Stanford University when the foundational ideas of Google developed 0 Google ranks webpages according to the percentage of time one would end up at each web on a random walk through the web Tim Chartier Ranking Web Pages Knowledge can be poer if i if 0 In October of 2003 George Johnston initiated a Google bomb called the miserable failure bomb which targeted President George W Bush and detonated by late November of that same year 0 The result was Google returning the official White House Biography of the President as the highest ranked result to the query miserable failure Tim Chartier Ranking Web Pages Ingrediesof a Google bomb 7 if 7 0 Putting together a Google bomb was relatively easy it involved several web pages linking to a common web page with an agreed upon anchor text the text that one clicks to go to the hyperlink o In the case of the miserable failure project of the over 800 links that pointed to the Bush biography only 32 used the phrase miserable failure in the anchor text Langville et al 2006 o This ignited a sort of political sparring match among the web saavy and by January 2004 a miserable failure query returned results for Michael Moore President Bush Jimmy Carter and Hillary Clinton in the top four positions Tim Chartier Ranking Web Pages quotquotte r39 77 Let s return to Monte Carlo simulation to mathematically model such a random walk through a web network W Tim Chartier Ranking Web Pages Surf over mini web 0 Assume we start at web page 1 0 We will assume that at each stage the surfer will randomly follow one of the links on the page The surfer can choose any link with equal probability Tim Chartier Ranking Web Pages ia atrix 0 We will represent the structure of a network with a matrix 0 The adjacency matrix for the network below is 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 6 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 W Tim Chartier Ranking Web Pages Your Turn 0 From the course webpage download googleSiml m 0 Find the PageRank of the system 0 Experiment with altering networks and viewing the results 0 How many iterates do you need to distinguish the rankings of the various webpages W Tim Chartier Ranking Web Pages Whatout Google 7 ML 0 Google indexes billions of webpages o How is PageRankfound by Google Tim Chartier Ranking Web Pages Transition t Marov 7 0 Instead let us formulate this as a Markov process where the states are web pages 0 We only need to define the probability of going from one state to the next 0 We just did this in our simulation The probability at any state of going to the next state is determined by the links on that page Tim Chartier Ranking Web Pages Entering some trnsiion 0 Transition matrix M is created from our adjacency matrix 0 That is element mj gives the probability of a surfer visit webpage i from webpagej which implies mijgijZgij i 0 Therefore for 011000 011000 000100 00000 000110 oooggo G 100001 M 100001 000100 00000 000010 0000g0 Tim Chartier Ranking Web Pages 0 Now let s start our random walk at state 1 o What is the probability that we land at web page i after one step 0 While trivial to compute we can also find this with our transition matrix Again this is transient behavior as opposed to finding the steady state vector 0 First we represent our initial state by the vector T v 1 0 0 0 0 oSimplycompute Mv0 o o 1 oT Tim Chartier Ranking Web Pages 0 Now let s take another step 0 Compute v2Mv1 0 033 033 0 033 0T 0 Your Turn Find v3 W Tim Chartier Ranking Web Pages 0 Now let s take another step 0 Compute v2Mv1 0 033 033 0 033 0T 0 Your Turn Findv3 Answerv3Mv2067 o 017 o o 017T W Tim Chartier Ranking Web Pages i 0 Let us find the steady state vector A way to approximate it is again finding say V500 and V700 0 Do this now 0 What do you notice W Tim Chartier Ranking Web Pages off so a a a a ff 0 Let us find the steady state vector A way to approximate it is again finding say V500 and V700 0 Do this now 0 What do you notice 0 To three decimal places VM700 VM500vM1oo 0263 0105 0158 0316 0105 0053 W Tim Chartier Ranking Web Pages 0 We have our rankings Pagea i a vetor i 7 i i 0 Keep in mind we are really finding an eigenvector of M associated with the eigenvalue 1 0 Google defines the PageRank of page i to be v 0 Therefore the largest element of v corresponds to the page with the highest PageRank the second largest to the page with the second highest PageRank and so on 0 The limiting frequency that an infinitely dedicated random surfer visits any particular page is that page s PageRank W Tim Chartier Ranking Web Pages Find eRan vi eigenvetrs o The following will find PageRank by finding the dominant eigenvector of M o The code actually finds all the eigenvectors of M which is more work than Google does VD eig M Assuming the eigenvalue 1 is in the first row first column of D pageRank Vl pageRank pageRanksumpageRank Tim Chartier Ranking Web Pages cotheae 0 Note the code googleEvec mwill perform these calculations for you 0 Let s surf again and adapt googleEvec mfor the network below anking Web Pages Tim Chartier R Dng39ne a 0 Note web page 6 is what is called a dangling node with no outlinks What web pages have this behavior 0 What problem did you see with our current model 0 Ideas to fix it Let s see if we can come up with the one of Brin and Page that lies deep within Google s algorithm Tim Chartier Ranking Web Pages Revised random surfing 7 H The rules to our Monte Carlo game are now 0 Again restrict ourselves only to indexed web pages 0 Assume that forp 085 or 85 of the time a surfer follows a link that is available on the current web page that the surfer is visiting The other 15 of the time the surfer randomly visits with equal probability any web page available in the network A Tim Chartier Ranking Web Pages It s elementary 0 Let 0 denote the column sum of row i 0 Therefore the transition matrix M has elements p1 01750 C n mi C 0 n 0 Again p 085 o This model creates a transition matrix that is often called the Google matrix W Tim Chartier Ranking Web Pages orming the Trantion Matrix 0 Therefore for our problem the adjacency matrix is 011000 000100 G 000110 100000 000100 000010 0 The first column of the transition matrix M is 156 156 156 85156 156 156T W Tim Chartier Ranking Web Pages Forming the Tranition Matrix cnt Therefore for 011000 000100 G 000110 100000 000100 000010 the Google matrix is 00250 08750 08750 00250 00250 01667 00250 00250 00250 03083 00250 01667 00250 00250 00250 03083 04500 01667 08750 00250 00250 00250 00250 01667 00250 00250 00250 03083 00250 01667 00250 00250 00250 00250 04500 01667 Tim Chartier Ranking Web Pages 0 You will find that the dominant eigenvector of M is 02680 01117 01594 02644 01117 00846T 0 Therefore page 1 has the best ranking followed by page 4 Compare this to the network Tim Chartier Ranking Web Pages Existence and uniqueness o If this vector is not unique which one would you choose Would you bid between companies for which one to choose 0 The following theorem Lax 1997 guarantees the uniqueness of the steady state vector and that it will have positive entries Theorem Perron Every real square matrix P who entries are all positive has a unique eigenvector with all positive entries its corresponding eigenvalue has multiplicity one and it is the dominant eigenvalue in that every other eigenvalue has strictly smaller mag n ude Tim Chartier Ranking Web Pages Stochas atrics i 7 7 0 Recall that the columns of M sum to 1 Therefore 1M 1 where 1 is the row vector of all ones That is 1 is a left eigenvector of M associated with the eigenvalue 1 most notably for our purposes having all positive entries 0 Perron s Theorem ensures that 1 is the unique right eigenvector with all positive entries and hence its eigenvalue must be the dominant one o The right and left eigenvalues of a matrix are the same therefore 1 is the dominant right eigenvalue as well So there exists a unique steadystate vector v that satisfies Mv v Normalizing this eigenvector so that 2v 1 gives a steady state vector Tim Chartier Ranking Web Pages Your Turn o It is time to experiment and play Indeed we will become Google search engines simple ones ourselves 0 To search from a homepage you will type a statement like U G surfer http WWWXXX ZZZ I1 o This starts at the given URL and tries to surf the Web until it has visited n pages That is an n by n matrix is formed 0 Note surfing can cause problems and as such you may even have to terminate MATLAB Yet nonetheless we can create our own PageRank example 0 Further the MATLAB Mfiles you will run find the PageRank vector in a different way than we have discussed in this lecture Tim Chartier Ranking Web Pages Google 7 i i 0 Download surfer m pagerank m and pagerankpow m from the course webpage Note these files use only G and never form the transition matrix M 0 These codes were written by Cleve Moler although pagerank m is an adapted version of Cleve s codes 0 Let s begin with www washington edu as our starting URL and create a network of 20 pages Therefore type UG surfer httpwwwwashingtonedu 20 0 U a cell array of n strings the URLs of the nodes 0 G an nbyn sparse matrix with Gij 1 if node is linked to node i 0 Type pagerank and the pagerank will be computed 0 Note The program hangs sometimes and requires breaking from the program CTRLC or shutting down MATLAB altogether Tim Chartier Ranking Web Pages Sensitivity Analysis Tim Chartier Department of Mathematics Math 381 Tim Chartier Sensitivity Analysis 7 1 Announcement Monday s class will be in Communications B027 We will again be using Excel Tim Chartier Sensitivity Analysis Weck c c f i i ff Recall the LP for the Whole Paycheck grocery max 24X 36y subject to 4000X 8000y 3 56000 6X 8y 3 72 X 2 0 y 2 o W Tim Chartier Sensitivity Analysis Questions Questions This resulted in the feasible region below which had as an optimal value 8 3 Whole Paycheck LP 6X8y72 8i 4X8y56 Arctic Refrigerators 0 l y 4 6 8 1o 12 14 X Frigid Refrigerators Tim Chartier Sensitivity Analysis A question to ponder 7 Recall that X the number of Frigid Refrigerators and y the number of Arctic Refrigerators Further we are maximizing volume as captured in the objective function max 24X 36y Question Suppose the measurement of the volume of a Frigid Refrigerator is exact but we know that there may be measurement error in the volume of an Arctic Refrigerator What is the largest volume for an Arctic Refrigerator that will include a nonzero num ber of Frigid Refrigerators in the optimal solution but any larger volume will result in zero Frigid Refrigerators Step by e 7 h 7 7 7 Question Assuming the volume of each Frigid Refrigerator is fixed what is the largest volume for an Arctic Refrigerator that will include a nonzero number of Frigid Refrigerators in the optimal so lution but any larger volume will result in zero Frigid Refrigerators Let s take this a step at a time W Tim Chartier Sensitivity Analysis Gettin raphic i o If we increase the volume of Arctic Refrigerators what happens to the contour lines of the objective function That is what happens to the lines perpendicular to a line that is parallel to the gradient vector of the objective function 0 Talk with a partner We will discuss this as a group so be prepared to give an answer 2 Whole Paycheck LP a i i 6x8y 72 8K 4x8y 56 7 w a 5 H E6 a 93 55 n 04 a 8 lt3 gt2 1 G 0 2 4 6 8 1o 12 14 x Frigid Refrigerators Tim Chartier Sensitivity Analysis Just tilt yur head 7 0 Increasing the volume of Arctic Refrigerators tilts the objective function counterclockwise in this case 0 For example let us change the objective function from max 24X 36y left to max 24X 40y right Whole Paycheck LP 6x8y 72 8K 4x8y 56 9 Whole Paycheck LP 6x8y 72 4x8y 56 8 17 w L L o x o 56 16 739 E E 9 9 6 55 a 04 n 5 e e 4 8 8 lt3 lt 3 ll II gt gt 2 2 1 1 G G 0 2 12 14 0 2 12 14 Tim Chartier Sensitivity Analysis How much tilt to tilt 7 Question What amount of tilting so to speak will be the most amount of tilting where anymore will exclude Frigid Refrigerators from the optimal solution Whole Paycheck LP Whole Paycheck LP a i i i H i i 6x8y 72 6x8y 72 8K 4x8y 56 9 4x8y 56 7 8 7 g g 77 y w E 6 E ag g 6 55 s n 4 n 5 e e 4 8 8 lt1 3 lt1 3 II gt gt 2 2 1 1 n n Tim Chartier Sensitivity Analysis To be palll 7 i 7 if i o This occurs when the contour lines of the objective function are parallel to the constraint 4X 8y 56 0 Therefore we are interested in an objective function max 24X ay where the contour lines of this objective function are parallel to the constraint above Question How do we choose such an a W Tim Chartier Sensitivity Analysis To b edicar a a of o The vector 2 J is parallel to the line 4x 8y 56 which can also be expressed as y x 7 V 1 2 2 o The vector is perpendicular to v1 since v1 v2 O 0 We want an objective function max 24X ay such that its gradient is parallel to v2 That is we want i2iiiw4a 0 Therefore for any value a gt 48 the objective function max 24X ay will result in no Frigid Refrigerators in the optimal solution Tim Chartier Sensitivity Analysis Similar qetion 7 i 7 7 0 Similarly we can ask another question o If we fix the volume of each Arctic Refrigerator how much can decrease the volume of each Frigid Refrigerator until a nonzero number of Frigid Refrigerators are in the optimal solution but any further reduction would lead to no Frigid Refrigerators in the optimal solution 0 Now we want an objective function max 6X 36y such that its gradient is parallel to v2 That is we want ls ll2lww 0 Therefore for any value 6 lt 18 the objective function max 6X 36y will result in no Frigid Refrigerators in the optimal solution W Tim Chartier Sensitivity Analysis Questions Questions Let us ask another question Question What is the effect of perturbing the availability of re sources W Tim Chartier Sensitivity Analysis Perturbing nsit Therefore we want to look at the system which depends on 61 and 62 V61 62 24X 36y subject to 4000X 8000y 3 56000 61 6X 8y 3 72 62 X 2 0 y 2 o W Tim Chartier Sensitivity Analysis Intero Point 7 o For small 61 62 the solution lies on the intersection of 4000X 8000y 3 56000 61 6X 8y 3 72 62 0 We want to solve this system which is easy on MATLAB Whole Paycheck LP 9 i i i 6x8y 72 8 K 4x By 56 m l l Arctic Refrigerators gt U I y W Tim Chartier Sensitivity Analysis f OTAB a a a a ff 0 We will perform Gaussian Elimination on MATLAB and put the system in reducedrow echelon form Note that 4000X 8000y e1 2 56000 6X 8y 62 72 0 Therefore we have the augmented system 4000 8000 1 0 56000 6 8 O 1 72 W Tim Chartier Sensitivity Analysis f ATL 0 f i i f f The following session will solve this system in MATLAB gtgt format rat gtgt A A 4000 8000 1 0 56000 6 8 0 1 72 gtgt rrefA ans 1 0 12000 12 8 0 1 l2667 14 3 W Tim Chartier Sensitivity Analysis Extr olutin 7 i i if 0 Therefore X 201W 1628 y 261W61 623 0 Substituting into the equation V61 2 24X 36y and collecting terms we get ve162 61 12 962 192 108 2 e1 362 300 0 Near O 0 since we are interested in small 6162 we find 1 15 76753 lt marginal value of cost 3 lt marginal value of oor space W Tim Chartier Sensitivity Analysis Intertin i 7 i i if 0 How do we interpret these values 0 Therefore for each additional dollar in the budget to buy refrigerators above the base of 56000 there is a contribution of 11576753 2 00015 ft3 to the volume in the objective function 0 Similarly for each additional ft2 of floor space available above the base of 72 kg there is a contribution of 3 ft3 to the volume in the objective function W Tim Chartier Sensitivity Analysis Eel s Senitivit eort i i i 7 7 e We can find these values on Excel s sensitivity report 0 They are listed as Shadow Prices which is another name for marginal values W Tim Chartier Sensitivity Analysis Your Turn Finally let s work on a handout for modeling a Plastic Cup factory Yourjob will be to set up the LP produce the sensitivity report and answer the questions W Tim Chartier Sensitivity Analysis Monte Carlo Simulation Poisson processes Tim Chartier Department of Mathematics Math 381 4 A m 11 339 39 4 Tim Chartier Monte Carlo Simulation Poisson processes On or ofn the fih store 0 Last time we assumed that each day 1 or 0 customers could enter the fish store 0 We implemented this strategy in MATLAB with the following code randomNumber rand if randomNumber lt a customer 1 else customer 0 end What about if 2 or more customers arrive in one day at random times This surely could happen even with an average of one customer per week W Tim Chartier Monte Carlo Simulation Poisson processes quot9 aera if 0 Let a equal the average number of customers per day 0 Then we can test if a lt 1 to see if a customer arrived on a given day 0 If a gt 1 then we no longer can use this as a probability directly 0 Are we at a loss W Tim Chartier Monte Carlo Simulation Poisson processes Making tngs prbable 0 Remember what we did last time we had that an average of 1 sale per week This led to a 17 probability of a sale on any given day 0 If we had an average of 2 sales per week Then we could assume a probability of 27 for a sale on any given day 0 If we had an average of 8 sales per week then what 0 Assuming a probability of 87 for a sale on any given day won t work But we could assume with probability of 47 that there is a sale on any given half of a day W Tim Chartier Monte Carlo Simulation Poisson processes Pausea flect i 7 7 7 0 Note that shrunk the time unit to form a probability 0 Goal Given a the average number of customers per day Find pk the probability of exactly k customers arriving on a given day 0 Note that if we had such probabilities the MATLAB code to capture this in arrivals at the store easily follows randomnum randl if randomnum lt p0 customers O elseif randomnum lt p0pl customers l elseif randomnum lt pOplp2 customers 2 else customers 3 it Tim Chartier Monte Carlo Simulation Poisson processes MC trscue 7 i 7 if 0 We can use Monte Carlo simulation to compute pk 0 Split the day into N pieces as seen below Unit 1 Unit 2 Unit 3 Unit N 0 Note that the interval size could be an hour minute second or even smaller 0 Assume in each interval that the probability of one customer is aN 0 Note that we are assuming 0 or 1 customer will appear in each interval W Tim Chartier Monte Carlo Simulation Poisson processes 0 Run the experiment on several days and find the percentage of times that you have 2 customers per day 0 This gives an estimate to pg 0 For example let us split our day into 5 intervals Then two customers arrived on the following day man man 0 On the course web page poissonm performs such experiments and also on this day W Tim Chartier Monte Carlo Simulation Poisson processes 7 i 7 0 Remember we need to run enough days to gain accurate results 0 Let s run our experiment for over 27 years 0 That is let s run our simulation for a simulated 10000 days Tim Chartier Monte Carlo Simulation Poisson processes Estimate oisson 7 if 7 o Repeating this experiment 3 times yields 0 Running the simulation 3 times gives some reassurance that the value of 10000 is large enough 0 If we had run it for only 100 days each we would see quite a bit of variation from run to run 0 Here it seems fairly clear that po 3 036 p1 3 037 pg 3 018 etc Tim Chartier Monte Carlo Simulation Poisson processes Aaly veloment i 7 if 0 These probabilities can be computed without simulation as they follow a Poisson distribution 0 In fact probability of exactly k customers in a single day is ake a pk k oTherefore p0 e az03679 p1 ae a p2 aZe aZ 0 Download poisson2 m from the course web page to compare the computed probabilities with the actual W Tim Chartier Monte Carlo Simulation Poisson processes To the innte and beyond 0 The Poisson distribution is continuous How is our finite process leading to this continuous distribution 0 The arrival of customers is being modeled using a Poisson process 0 As we saw before we can split our day into units and test if 1 or 0 customers arrive in that unit of time o For instance let us take 3 such intervals When we test if a customer arrives or not we are taking a Bernoulli trial 0 Therefore we have the following Unit 1 Unit 2 Unit 3 where there is a probability p of a customer arriving in interval i Tim Chartier Monte Carlo Simulation Poisson processes 0 Therefore our possible outcomes are the following o 3 ways to observe 1 customer during the entire day 0 3 ways to observe 2 customers 0 1 way to observe O or 3 customers W Tim Chartier Monte Carlo Simulation Poisson processes 0 Adding up the probabilities we find pf the probability of observing k customers when N 3 0 customers 1 p3 2 p83 3 1 customers 31 p2p p1 2 customers 31 pp2 pg 3 customers p3 pg 0 Note that these probabilities sum to 1 0 We can see this easily using the fact that X l3 X33X2y3xy2 y3 withx1 pandyp o The binomial expansion leads to pIEN since XyNXN I XN 1y I XN 2y2 N71 XyN 1yN o The values lt I N Choose k the binomial coef cients 0 The probabilities we seek are p5 1 pgtN plN 1 pN 1p N1 pN 1p N p2 1 pW Zp2 N2 N1 pW Zp2 NZ Z o This is called the binomial distribution for the total number of successes in N Bernoulli trials Tim Chartier Monte Carlo Simulation Poisson processes giConnec ngthe n etothein n e 0 We are now ready withablomandwavmg to connect this to the Poisson distribution 0 In particular we consider as N gt oo o For example N 3 V a pO Nllnoopo Ngtnoolt1 N e 39 p1 am lt1 3 lt altuolt1 gt ae a 0 Similarly Z W Tim Chartier Monte Carlo Simulation Poisson processes Hmeorep 7 i 7 7 7 0 Let us go over the next homework assignment 0 Problem 3 Finding your Perfect Mate in Monte Carlo o R mark com by Milk Pansv 39 You riEVER 39 39 TAKE ME MYHHERL I v a I a E39a w 5quot l i I r v II VIYWI 2 91 DYNA m 139 4 9 Develop a dating strategy to find a spouse and use Monte Carlo simulation to optimize the implementation of the strategy W Tim Chartier Monte Carlo Simulation Poisson processes i matheaical love life 7 if i 0 There are several rules and assumptions to our dating game 0 0 0 O 0 0 You may date only one person at a time While the length of time that you date someone is not specified you must eventually pass on a dating partner and move to another candidate or select a dating partner as a mate at which time the strategy ends and you have a spouse Once a dating partner is passed you cannot date that person again That is no is forever lfyou knew the N potential mates in advance and ranked them according to their fit where a ranking of 1 indicates the best fit 2 indicates the second best fit and so forth there would be no ties Therefore among the pool of N people to date one person is the best match for you While we will assume there are N people in the pool for you to date you will know the number of people in the pool but do not know who these people are in advance and will meet them one at a time as you date Therefore you will only know all N people if you date all N The order in which you date the N people is random W Tim Chartier Monte Carlo Simulation Poisson processes

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.