New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Discrete Mathematics and Probability Theory

by: Mr. Hayley Barton

Discrete Mathematics and Probability Theory COMPSCI 70

Marketplace > University of California - Berkeley > ComputerScienence > COMPSCI 70 > Discrete Mathematics and Probability Theory
Mr. Hayley Barton

GPA 3.93


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 38 page Class Notes was uploaded by Mr. Hayley Barton on Thursday October 22, 2015. The Class Notes belongs to COMPSCI 70 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 24 views. For similar materials see /class/226664/compsci-70-university-of-california-berkeley in ComputerScienence at University of California - Berkeley.


Reviews for Discrete Mathematics and Probability Theory


Report this Material


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: 10/22/15
CS 707 Fall 2003 Discussion 7 Amir Kamil UC Berkeley 101703 Topics Fingerprinting7 Secret Sharing 1 Fingerprinting Consider the ngerprinting function Fpz 1 mod p where p is some large prime Suppose Alice and Bob share a large prime p and Alice wants to send an important but public message m to Bob In order to make sure that he receives the correct she ngerprints the message as follows She breaks it into n 615 bit pieces then sends each piece along with its ngerprint When Bob receives the pieces he computes the ngerprint and checks against the received ngerprint If a mismatch occurs he asks Alice to resend the piece and its ngerprint Now suppose an adversary intercepts the communication but doesnlt know pl He wants to be able to change both the pieces of the message and their ngerprints so that Bob receives an incorrect message but believes he received the right one Can the adversary do this with success guaranteed For example adding 1 to both a piece and its ngerprint works most of the time but not all the time ls there a scheme that always works Since the adversary is listening in on the transmission he learns pairs ai Fp ai where the ai are the n bit pieces By the de nition of the ngerprinting function ai E Fp ai mod p so p divides zl aiEFp oi However I may be a large multiple of p and so may be hard to factor But note that gcdzizj is also a multiple of p and is very likely to be a smaller multiple of p than either I or zj it is quite unlikely that one is a multiple of the other And then gcdzizj 1k is an even smaller multiple of pi So by listening to y pieces of the message the adversary can compute gcdzl 12 my which we expect to either be p or a small easily factorable multiple of pi Thus the adversary can learn p allowing him to change the message as much as he wants As a result this ngerprinting scheme is insecure This is why the RSA ngerprinting scheme is a better alternative 2 Secret Sharing Suppose I want to encode a secret m using the secret sharing protocol discussed in class llll pick a prime p gt m and a degree k polynomial such that E m mod p Suppose you know Is points on this polynomial ie you know the value of mod p for k different Do you know any information about my secret Lets do a concrete example Suppose I pick p 11 and a degree 2 polynomial I tell you that E 7 mod 11 and E 5 mod 11 Does this tell you anything about my secret In order to answer this question rst let s decide what information you knew before you learned the value of and f7 and what you know now The only thing you knew before was that my secret is a value between 0 and 10 What you know now depends on how many degree 2 polynomial satisfy the given values for and In fact the following degree 2 polynomials all work fz4z2z0 9122zl 312312 8124z3 212514 7z26z5 1127z6 6128z7 Oz2918 5121019 fz 1012011oi These polynomials cover all possible values of the secret And each value has exactly one corresponding polynomiali Thus you still have no idea what value my secret is besides that it is between 0 and 10 Now what ifl also told you that E 7 mod 11 Now there is only a single degree 2 polynomial that satis es all three points namely 212 51 4 Thus my secret is the value 4 You may be wondering how I came up with the above polynomialsi Well for the rst set I used an inef cient program to compute themi For the actual correct polynomial I used the polynomial interpolation algorithm you proved in your homework Recall that the polynomial 12ka1 where Fkz IE 0z E l I E klzE 16E 1 IE 10 and bk Fkk 1 mod 11 has the value 0 for f 16 mod 11 and l for mod 11 But this isn7t quite what we want If we interpolated using these polynomials we7d end up with a polynomial such that E 0 mod 11 for I g 67 8 We need polynomials for k 6 678 such that E 1 mod 11 and E 0 mod 11 forj 6 678 E 16 but is unforced for j g 6 78 So the polynomials we are looking for are f5z b5F5z F5z I E 7z E 8 b5 F56 1 mod 11 f7z b7F7z F7z I E 6z E 8 b7 F77 1 mod 11 f3z b3FgI F3ltIgt z E 6z E 7 b3 Fg8 1 mod 11 Then our desired polynomial is f6f5 This polynomial has the correct E 8 valuesatz 1 an in Using the above method we recover the polynomial 212 51 4 Thus the secret is 4 Now suppose I did not tell you the degree of the polynomial that encodes my secret How many points would be required for you to gure out the secret In this case it is impossible for you to gure out the secret Suppose I pick a degree 100 polynomial and carefully choose 10 points to give you such that there is a degree 3 polynomial that satis es all 10 points You can try all possible degrees from 1 to 9 and even if that degree 3 polynomial is the only polynomial in this range that satis es the 10 points you can7t be sure that the polynomial is correct In fact in this case it is not so you would recover the wrong secreti CS 70 Discrete Mathematics for Spring 2005 ClancyWagner Notes Random Variables and Expectation Question The homeworks of 20 students are collected in randomly shuf ed and returned to the students How many students receive their own homework To answer this question we rst need to specify the probability space plainly it should consist of all 20 permutations of the homeworks each with probability Note that this is the same as the probability space for card shuf ing except that the number of items being shuf ed is now 20 rather than 52 It helps to have a picture of a permutation Think of 20 books lined up on a shelf labeled from left to right with 127 720 A permutation n is just a reordering of the books which we can describe just by listing their labels from left to right Let s denote by 71 the label of the book that is in position i We are interested in the number of books that are still in their original position ie in the number of is such that 71 139 These are often known as xed points of the permutation Of course our question does not have a simple numerical answer such as 6 because the number depends on the particular permutation we choose ie on the sample point Let s call the number of xed points X To make life simpler let s also shrink the class size down to 3 for a while The following table gives a complete listing of the sample space of size 3 6 together with the corresponding value of X for each sample point We use our bookshelf convention for writing a permutation thus for example the permutation 312 means that book 3 is on the left book 1 in the center and book 2 on the right You should check you agree with this table permutation 71 value of X 123 3 132 1 213 1 231 0 0 1 312 321 Thus we see thatX takes on values 0 1 or 3 depending on the sample point A quantity like this which takes on some numerical value at each sample point is called a random variable or rv on the sample space De nition 201 random variable A random variable X on a sample space 9 is a function that assigns to each sample point co 6 Q a real numberXco Until further notice we 11 restrict our attention to discrete random variables ie their values will be integers or rationals rather than arbitrary real numbers The rv X in our permutation example above is completely speci ed by its values at all sample points as given in the above table Thus for example X 123 3 etc Rather than the value at each sample point we are usually more interested in the set of points at which the CS 70 Spring 2005 Notes 20 1 rv takes on some given value Let a be any real number Then the set 6069 Xcoa is an event in the sample space why We usually abbreviate this event to simply X a SinceX a is an event we can talk about its probability PrX a The collection of these probabilities for all possible values of a is known as the distribution of the rv X De nition 202 distribution The distribution of a discrete random variableX is the collection of values aPrX a a E 52 where 52 is the set of all possible values taken be In most of our examples 52 will be some subset of the integers Thus the distribution of the random variable X in our permutation example above is PrX0139 PrXl139 PrX3139 7 7 3 7 7 7 2 7 7 7 6 7 and PrX a 0 for all other values of a Notice that the sum of the probabilities PrX a over all possible values of a is exactly 1 This must always be the case for any random variable Why Because any random variable X must take on one and only one value X co at every sample point co Ie the events X a partition the sample space So when we sum up the probabilities of the events X a we are really summing up the probabilities of all the sample points Expectation In most applications the complete distribution of a rv is very hard to calculate for example suppose we go back to our original question with 20 students In principle we d have to enumerate 20 m 24 X 1018 sample points compute the value of X at each one and count the number of points at whichX takes on each of its possible values Moreover even when we can compute the complete distribution of a rv it is often not very informative For these reasons we seek to compress the distribution into a more compact convenient form that is also easier to compute The most widely used such form is the expectation or mean or average of the rv De nition 203 expectation The expectation of a discrete random variable X is de ned as EX 2 agtlt PrX a 16ng where the sum is over all possible values taken by the rv For our running permutation example the expectation is l l l l l EX7lt0gtlt gtlt1gtlt gtlt3gtltggt 70 7L Ie the expected number of xed points in a permutation of three items is exactly 1 The expectation can be seen in some sense as a typica value of the rv though note that it may not actually be a value that the rv ever takes on The question of how typical the expectation is for a given rv is a very important one that we shall return to in a later lecture Here are some simple examples of expectations CS 70 Spring 2005 Notes 20 2 1 Single die Throw one fair die LetX be the number that comes up ThenX takes on values 12 6 each with probability so 1 21 7 EXg123456 3 Note thatX never actually takes on its expected value 2 Two dice Throw two fair dice LetX be the sum of their scores Then the distribution ofX is a 2 3 4 5 6 7 8 9 10 11 12 1 1 1 1 5 1 5 1 1 1 1 IPriXai E l The expectation is therefore EX 2gtlt1 3gtlt1 4gtlt1 12gtlt1 7 T 36 18 12 36 T 39 3 Roulette A roulette wheel is spun You bet 1 on Black If a black number comes up you receive your stake plus 1 otherwise you lose your stake LetX be your net winnings in one game ThenX can take on the values 1 and 71 and PrX 1 PrX 71 Recall that a roulette wheel has 38 slots the numbers 12 36 half of which are red and half black plus 0 and 00 which are green Thus EX 1X18 1X20 7 139 T 38 38 T 19 ie you expect to lose about a nickel per game Notice how the zeros tip the balance in favor of the casino Linearity of expectation So far we ve computed expectations by brute force ie we have written down the whole distribution and then added up the contributions for all possible values of the rv The real power of expectations is that in many reallife examples they can be computed much more easily using a simple shortcut The shortcut is the following Theorem 201 For any two random variablesX andY on the same probability space we have EXY EX EY Also for any constant c we have EcX cEX Proof To make the proof easier we will rst rewrite the de nition of expectation in a more convenient form Recall from De nition 203 that EX 2 agtltPrXa 16ng Let s look at one term a X PrX a in the above sum Notice that PrX a by de nition is the sum of Prco over those sample points co for whichXco a And we know that every sample point co 6 Q is in CS 70 Spring 2005 Notes 20 3 exactly one of these events X a This means we can write out the above de nition in a more longwinded form as EX 29Xco gtltPrco 1 This equivalent de nition of expectation will make the present proof much easier though it is usually less convenient for actual calculations Now let s write out EX Y using equation 1 EXY ZwEQXYco gtltPrco ZweoXw Yw X Prlwl 2 mo x PM mm mm x mm EX EY In the last step we used equation 1 twice This completes the proof of the rst equality The proof of the second equality is much simpler and is left as an exercise D Theorem 201 is very powerful it says that the expectation of a sum of rv s is the sum of their expectations with no assumptions about the rv s Note that we didn t require for example that X and Y are indepen dent We can use Theorem 201 to conclude things like E3X7 SY 3EX 7 5EY This property is known as linearity of expectation Important caveat Theorem 20 does not say that EX Y EXEY or that Ei 1 etc These claims are not true in general It is only sums and d erences and constant multiples of random variables that behave so nicely Now let s see some examples of Theorem 201 in action 4 Two dice again Here s a much less painful way of computing EX whereX is the sum of the scores of the two dice Note thatX X1 Xz whereX is the score on die i We know from example 1 above that EX1 EX So by Theorem 201 we have EX EX1EXz 7 V39 More roulette Suppose we play the above roulette game not once but 1000 times LetX be our expected net winnings Then X X1 Xz X1000 where X is our net winnings in the ith play We know from earlier that 71 for each i Therefore by Theorem 201 EX EX1EXzwEX10001000 gtlt 711 9 7 m 753 So ifyou play 1000 games you expect to lose about 53 6 Homeworks Let s go back and answer our original question about the class of 20 students Recall that the rv X is the number of students who receive their own homework after shuf ing or equiva lently the number of xed points To take advantage of Theorem 201 we need to writeX as the sum of simpler rv s But sinceX counts the number of times something happens we can write it as a sum using the following trick 1 if student i gets her own hw 1X1X11X2Hrlino7 WhCl CiXi 0 otherw1se You should think about this equation for a moment Remember that all the X s are random variables What does an equation involving random variables mean What we mean is that at every sample point co we haveXco X1co X2co X20co Why is this true CS 70 Spring 2005 Notes 20 4 A 0 1valued random variable such as X is called an indicator random variable of the corresponding event in this case the event that student 139 gets her own hw For indicator rv s the expectation is particularly easy to calculate Namely 0gtltPrX 01gtltPrX 1 PrX 1 But in our case we have 1 PrXi 1 Prstudent 139 gets her own hw Now we can apply Theorem 201 to 2 to get 1 EX EX1 EX2 EX20 20 X E 1 So we see that the expected number of students who get their own homeworks in a class of size 20 is 1 But this is exactly the same answer as we got for a class of size 3 And indeed we can easily see from the above calculation that we would get EX 1 for any class size n this is because we can writeX X1Xz Xn and for eachz39 So the expected number of xed points in a random permutation of n items is always 1 regardless of 11 Amazing but true 7 Coin tosses Toss a fair coin 100 times Let the rv X be the number of Heads As in the previous example to take advantage of Theorem 201 we write X X1X2 r X1007 where X is the indicator rv of the event that the ith toss is Heads Since the coin is fair we have Pr 1 Prz39th toss is Heads Using Theorem 201 we therefore get 100 EXz1oogtlt50 11 More generally the expected number of Heads in n tosses of a fair coin is And in n tosses of a biased coin with Heads probability p it is np why 8 Balls and bins Throw m balls into n bins Let the rv X be the number of balls that land in the rst bin ThenX behaves exactly like the number of Heads in n tosses of a biased coin with Heads probability why So from example 7 we get EX In the special case m n the expected number of balls in any bin is 1 If we wanted to compute this directly from the distribution of X we d get into a messy calculation involving binomial coef cients a bit like the load balancing example in the previous lecture Here s another example on the same sample space Let the rv Y be the number of empty bins The distribution of Y is horrible to contemplate to get a feel for this you might like to write it down for m n 3 3 balls 3 bins However computing the expectation EY is a piece of cake using Theorem 201 As usual let s write YY1Y2 Yn7 3 CS 70 Spring 2005 Notes 20 5 where Y is the indicator rv of the event bin 139 is empty Again as usual the expectation of Y is easy 1 m PrY 1 Prbinz39is empty 17 7gt I l recall that we computed this probability quite easily way back in lecture 17 Applying Theorem 201 to 3 we therefore have VI 1 m EY 213m n if gt i1 7 a very simple formula very easily derived Let s see how it behaves in the special case m n same number of balls as bins In this case we get EY n1 7 Now the quantity 1 7 quot can be approximated for large enough values of n by the number 51 So we see that EY a 3 s 036811 as n a co C The bottom line is that if we throw say 1000 balls into 1000 bins the expected number of empty bins is about 368 1 More generally it is a standard fact that for any constant c 1 quot7gte5 asn7gtoo We just used this fact in the special case c 71 The approximation is actually very good even for quite small values of n 7 try it yourself Eg for n 20 we already get 1 7 0358 which is very close to 1e 0367 The approximation gets better and better for larger n CS 70 Spring 2005 Notes 20 6 These are notes on Godel s Theorem and Turtng s proof of the undectdabtltty of the halting problem taken from a longer naratz39on 1 GODEUS PROOF Subject Splean From bald mathunitriesteit Date July 19 1999 215 GST It is a hot summer night in the Adriatic way past midnight my theorem is going nowhere too much caffeine in my system and still no word from you A perfect time I think for lling in a couple of the many important points and details that my lazy colleague Turing left out of his lecture on Godel s theorem To understand this momentous result you must rst understand the man s premises Godel con sidered mathematical statements such as 1 1 277 and 1 1 3 isome of which are true iwe call them theoremsi and some are evidently false But the more interesting statements involve variables for example m 1 3 they are true or false depending on the values of the variables Certain statements involving variables happen to be true for all values they are algebraic identities like m 1 1 z m 7 z 1 and m 1 T 2 z T 22 0 177 by T 1 denote exponentiation That such a statement is true for all values of x can be considered itself a higher order statement for the last example this higher order statement is written Vz m 1 T 2 z T 22 z 1 where the Vz part is read for all z and means exactly that that the rest of the statement holds for any choice of integer value for z Such a statement is either true or false just like the simple statements 1 1 3 that involve no variables For example Vz z z T 2 is false as the part after Vz holds for a couple but not all values of x We can now answer Suleiman s question Indeed the truth of statements in Euclidean geometry along the lines of the ones we examined above using the same kinds of generalistic quanti ers for all lines77 and for all points77 can be decided by an algorithm But the tiling problem explained by Ian belongs to a higher sort of logic with quanti ers that say for all tilings77 or equivalently for all sets of points and lines77 There is no algorithm for deciding such sentences So the truth of some statements depends on the value of a variable while others claim perhaps falsely that the statement is true for all values Godel was interested in a curious kind of hybrid statement such as Vz y 7 z m The truth of this statement depends on the value of y ithis particular one is true if y is odd false otherwise That is if Az y is any arithmetic statement involving variables x and y and possibly other variables inside A each of them call it 2 neutralized by the corresponding V2 then Godel would construct from it the hybrid statement 1370 V00 Amy Notice the y in parentheses it codi es the fact that the truth of H depends on the value of y A key ingredient in Godel s idea was that all statements can be really thought of as numbers 7 numbers that encode arithmetic statements are known as Godel numbers This is no big deal just think that we have an in nite list of all possible legal statements shortest rst and each sentence is identi ed by its rank in this list Godel was interested in such an enumeration of his hybrid cs 70 Fall 2000 Soln 9 1 statements HOW V90 140907107 11119 V90 141907107 11129 V90 142907107 where the llm y s are all possible arithmetic statements involving z and y Recall now Godel s purpose in all this He wanted to show that in any mathematical system that expresses the integers and operations on them not all theorems can have proofs But what is a proof The important point here is that a proof is necessarily a string of characters Therefore lo and behold proofs in the assumed system the mathematical system that is to be proved incomplete can also be enumerated P0P1P2 So we have an enumeration of all hybrid statements and an enumeration of all proofs That much is easy Now comes the crucial idea If you substitute a number for the variable y of a hybrid statement then you get something that is either a theorem and may have a proof or a negation of a theorem in which case it does not lfl give you say H8787 inotice the beginning of a diagonalization This is the 87th hybrid statement with the value of variable y set to the statements own rank in the enumeration 877 and a proof say P290 then it should be easy to tell if P290 happens indeed to be a proof of H8787 But Godel s genius was in re ning this Not only can you tell this for any hybrid statement with its variable set to its rank Hnn and any proof Pm but there is an arithmetic statement involving the variables in and n that achieves this In other words you can express the fact that Pm is or is not a proof of as a long list of equations and inequalities involving m n multiplied and added and exponentiated together in complicated ways and possibly other variables eclipsed by V s It can be done I am omitting lots of details here it is very complicated and rather tedious in the end ithe truly clever part is not to achieve it but to reale that it is useful Thus there is an arithmetic statement Az y whose truth depends on the variables x and y and it is true only if it so happens that Pm is not a proof of the statement But this arithmetic statement Az y gives rise to a hybrid statement Vz Az y istating if you think about it for a minute that has no proof But this hybrid statement must be somewhere in our enumeration of the hybrid statements perhaps it is the k th such statement Hky where k is some xed number The diagonalization is now complete Statement Hkk since it is obtained from whose truth only depends on y by substituting the number k for y is unambiguously either true or false And as we argued above statement states that statement has no proof is precisely the statement called K by Turing ithe statement that declares itself unprovable As Turing argues then very convincingly K must be true but unprovable thus establishing Godel s incompleteness theorem 1 hope this helps If not there is a nice book that contains a more detailed explanation Codel s Proof by Ernest Nagel Another delightful book recounts the development of the eld of logic lead ing to the results by Godel and Turing The Uniuersal Computer The Road from Leibniz to Turing by Martin Davis Computers Humbled by David Harel covers computability but also complexity and NP completeness the subjects of a subsequent related lecture by Turing But the mathe matically sophisticated reader has more choices Introduction to the Theory of Computation by Michael Sipser Computational Complexity by Christos Papadimitriou and in relation to complex ity Computers and Intractability A Guide to the Theory of NP completeness by Michael Garey and David Johnson Finally it is worth noting that the P vs NP problem explained by Turing in CS 70 Fall 2000 Soln 9 2 the chapter Complexity is rst in the list of the Millennial prize mathematical problems of the Clay lnstitute http www claymath orgprizeproblemsindex htm Dott Baldovino Croce Trieste COMPUTABLITY Same here my friend same here OK then computability You see it s like this Before the computer we thought we were invincible There are no unsoliable problemsquot ithat s Hilbert again If the problem is hard you use more sophisticated techniques develop better math work longer hours talk to a smarter colleague perhaps wait for the next generation But it will be solved Now we know better But then 7 that s what people thought And there was a reason for this optimism We had not seen really hard problems There were there for sure but we had no eyes for them And then the computer came A beast constructed expressly for further facilitating and speeding up our inescapable conquest of all problems And isurpriseli it was itself the epitomy of complexity And the code that we had to write to make it useful the code was even more complex And when we saw the computer when we saw its code iand Turing saw it rsti we were looking at complexity incarnate And then suddenly we saw complexity everywhere It materialized it crystalized around us feven though it had always been there We have yet to recover from the shock Take code lt s everywhere in our computers on the Net It s in the little disks you get in junk mail in the back covers of books in little applets you download from the Net sites you visit It s easy to forget somebody must write this code When you work with code you see many times more code than you write Code written by others often years ago often by people you will never meet you will have no chance to chat with them over coffee a printout spread in front of you You are an archeologist Alexandros you must know the feeling What the hell was this for What were those people thinking Picture this A mysterious chaotic sequence of statements is spread in front of you Is it good code or bad code Slow code or fast code Does it have bugs Is it a virus will it take over your les sniff your password deplete your bank account Will it ever send a mail message from your account Will it crash on January 1 Will it ever print out something And if so will it ever stop printing Is it correct code will it do what it is supposed to do iprocess orders for example update sales gures and print mailing labels Does it have redundant parts pieces of code that will never be executed can be erased with impunity You spend your day trying to gure these things out You can run tests of course but for how long How many experiments will you run how many test inputs will you try When you work with code these are your bread and butter problems And here is my point They are all unsolvable There is no systematic way for answering them You have to be constantly on your toes one IQ point smarter than the code on your screen There is no silver bullet I can prove it for you Let s take perhaps the simplest problem of all Will this code ever stop The halting problem It can t be solved Suppose I give you a piece of code Alexandros a couple of hundred lines long How would you gure out if it ever stops 1 even give you its input Will it stop You will probably eye the code for a few minutes If it has no return instruction no stop instruction then it s a dead giveaway it will never stop But suppose that it has a few buried among the others the if thenelse s the repeatuntil s then what Will the execution ever reach those points How do you CS 70 Fall 2000 Soln 9 3 ever gure this out You will probably run the code with the given input to see if it will eventually stop If it does stop you are home free iyou have your answer But if not how long will you wait Maybe if I wait a little longer just a little it will stop How many times should you indulge How do you decide before forever How do you systematically decide if a given code will ever stop when started with a given input Well you can t And here is proof Suppose you could Suppose you have written your silver bullet the almighty code haltscode input which given some code with its input it computes away for a while and then announces its conclusion yes means that the code will eventually halt on the input no that it won t So just suppose that you have that You are now in the mercy of Cantor and his evil diagonals algorithm turingcode if haltscode code then repeat x lt 1 forever else stop Wow this is the most Aloe is in love fat the same time she can t wait to tell Timothy See This code does something very simple For any given piece of code it asks Will this code eventually stop if supplied with itself as an input If so then turingcode happily jumps into an in nite loop Otherwise it rushes to stop And now comes the unanswerable question the absurd situation that will expose the absurdity of haltscode input What will the program turing do when given itselfas an input Does turingturing stop eventually or does it compute forever Can you gure it out Alexandros I think I got it Alexandros is beaming lf turingturing ever stops then the line haltsturing turing will return yes and so turingturing will never stop it will get into the repeatforever loop Pause But if turingturing does not stop then haltsturing turing will return no and it will stop immediately So it stops if and only if it does not Exactly And this is a contradiction of course Code either stops or doesn t So we must have erred in assuming that the haltscode input program exists ithis was the only slippery part in this construction everything else is clean solid coding So There can be no code that solves the halting problem The halting problem is unsolvable But so are all the other questions about code that I mentioned Take for example the question Will this code ever print anything Well suppose that the only print statements of your program are just before your stop statements Then it will print something if and only if it will stop So the printing problem is as unsolvable as the halting problem And so on and so on for all of them You can t analyze code systematically Code is hard its secrets are unfathomable Code analysis can only be done by tedious thankless toil by discovering ad hoc tricks that will work for this program but will be worthless on the next OK starting from the halting problem you can argue that almost any question you can ask about code is unsolvable But there are unsolvable problems everywhere in science and math Even in geometry CS 70 Fall 2000 Soln 9 4 So Computational problems iproblems for which you would have liked to write codei are subdivided into two big categories Those problems that are solvable by algorithms and those that are unsolvable We have known this for a long time7 we have learned to live with unsolvability The unsolvable problems seeped in our culture7 we instinctively steer clear of them Trouble is7 there are too many other problems that fall somewhere in between They are solvable all right7 but the only code we have for them runs for way too long Exponentially long For such problems the diagnosis has to be more subtle Practically unsolvable NP complete But this is a whole new story CS 707 Fall 20007 Soln 9 CS 70 Discrete Mathematics for Spring 2008 David Wagner Note 8 Cake Cutting and Fair Division Algorithms The cakecutting problem is as follows We have a cake to be shared among n of us and we want to split it amongst themselves fairly However each person might value different portions of the cake differently I like owers you hate them I hate icing you prefer it What s worse everyone is greedy and will try to end up with as much cake if they can do so without noticeably deviating from the rules of the game Nonetheless we want some way to split the cake that everyone will agree is fair What can we do First let s try to make the problem statement more precise We assume that each person has their own measure of the value of parts of the cake If X is one of the participants and S represents a portion of the cake let m XS denote the value thatX associates to S We will assume that 0 g m XS 1 that measures are scaled so that every person values the whole cake at exactly 1 and that measures are additive so that mXSU T mXS mXT ifS7 T are two disjoint pieces of the cake Each participant knows their own measure but not necessarily the measure of anyone else we can t read other people 5 minds A cakecutting protocol speci es how each of the n participants is supposed to behave Each participant might follow the protocol or he might deviate from the protocol if the participant thinks he can get more cake by deviating We assume that no participant will behave in a way that detectably deviates from the protocol for instance no participant will just grab the whole cake and run away with it perhaps for fear of retribution However if a participant can behave in a way that appears to everyone else to follow the protocol but actually deviates from the protocol then a participant might well do so We classify a participant as honest if she follows the protocol or dishonest otherwise Of course there is no way for any participant to know which of the other participants may be honest or dishonest First we need to de ne what we mean by fair De nition A cakecutting protocol for n participants is fair forX if the following property is true If par ticipantX follows the protocol thenX is guaranteed to receive at least 1 nth of the cake be s measure no matter what happens A cakecutting protocol is fair if it is fair for every participant In general we will try to ensure that honest participants receive their just desserts but dishonest participants are not promised anything In other words a fair cakecutting protocol is supposed to ensure that each honest participant receives a piece of the cake that he thinks is worth at least 1 n by his own measure Here is a simple and classic protocol for splitting a cake between n 2 people say Alice and Bob 1 Alice cuts the cake into two pieces that she considers of equal worth by her measure 2 Bob chooses whichever piece he considers to be worth more by his measure 3 Alice receives the remaining piece This is known as the cutandchoose protocol because one participant cuts and the other chooses Theorem The cutandchoose protocol for n 2 is a fair cakecutting protocol Proof If Alice follows the protocol then both pieces are worth the same to her so each piece must be worth exactly 12 by her measure If we call the two pieces ST then mA S mAT mASU T 1 CS 70 Spring 2008 Note 8 1 and mAS mAT so mAS mAT 12 As a result it doesn t matter what Bob does Alice is guaranteed to receive a piece that she considers to be worth exactly 12 as long as she follows the protocol In other words the protocol is fair for Alice The protocol is also fair for Bob Call the two pieces S7 T We have mBS mBT mBSU T l and mBSmBT 2 0 so one of these two pieces must be worth at least 12 by Bob s measure Thus by choosing the larger of the two pieces Bob ensures that his piece will be worth at least 12 by his measure D Notice how the protocol rewards honesty as long as Alice is honest and follows the protocol she is guaran teed to receive her fair share In principle Alice could deviate from the protocol by cutting the cake into two pieces that she did not consider to be of equal worth but then she runs the risk of receiving a piece of the cake that is worth less than 12 Consequently we might say that this protocol helps to keep honest people honest by removing the temptation to cheat In contrast asking Alice to cut the cake into two equal pieces and then choose one would create two prob lems First Alice s measure might not be the same as Bob s measure so even if Alice followed our instruc tions faithfully Bob might end up with a piece that he considers to be worth less than 12 Second Alice would have every incentive to cut the cake unequally and then choose the larger of the two pieces If Bob gets upset she can always claim that the two pieces were equal by her measure Bob may suspect what really happened but Alice has plausible deniability So far this has been pretty straightforward But what about a protocol when n gt 2 Take a moment to think about how you might solve the problem when there are more than two participants Fairness for Many Participants Here is a rst attempt at a protocol for n 3 1 Alice cuts the cake into three pieces that she considers of equal worth by her measure 2 Bob chooses whichever piece he considers to be worth most by his measure 3 Carol chooses whichever of the two remaining pieces she considers to be worth more by her measure 4 Alice receives the remaining piece What do you think of this protocol Is it fair This protocol is certainly fair to Alice since if she follows the protocol she receives a piece worth 1 3 to her and to Bob since at least one of the three pieces must be worth at least 13 to him However it is not fair to Carol For instance if Alice and Bob are dishonest they could gang up to cheat Carol Alice could divide the cake into one very large piece and two tiny pieces Bob would take the very large piece and Carol would then be stuck with the tiny piece This demonstrates that the protocol is not fair to Carol and consequently that this is not a fair cakecutting protocol In this case Alice and Bob might have an incentive to cheat in this way If they agree to split their winnings evenly by cheating as described above Alice and Bob will end up with close to 12 of the cake which is more than they are guaranteed if they followed the protocol However it is worth emphasizing that the de nition of fairness does not assume that assume that all players will behave in their own interest Even if Alice and Bob had no incentive to cheat in this way from Carol s point of view the fact that they can cheat her out of her fair share is unacceptable and suf cient to condemn the protocol as not fair to Carol The de nition of fairness requires that even if everyone else conspires to try to cheat Carol out of her fair share Carol is still guaranteed her fair share CS 70 Spring 2008 Note 8 2 It s also worth pointing out that what can happen through malice can sometimes also happen by chance In the protocol given above Carol might end up with less than her fair share even if Alice and Bob faithfully follow the protocol For instance suppose that the cake happens to be made of chocolate vanilla and strawberry and Alice cuts it into an allchocolate piece an allvanilla piece and an allstrawberry piece Imagine that Carol hates vanilla and strawberry and considers them to be worth 0 by her measure If Bob happens to take the chocolate piece before Carol gets a chance at it then Carol will be stuck with a piece of the cake that is worth nothing to her That s not very fair to her This kind of thing could easily happen just by bad luck Nonetheless when analyzing cakecutting protocols it is often helpful to consider what happens if everyone else tries to gang up on you and cheat you out of your fair share If you re still guaranteed to get at least 1 nth of the cake even when everyone else is malicious and conspiring then mere bad luck can t hurt you With that preamble here is a general protocol for fair cakecutting for arbitrarily many participants 1 If n 2 use the cutandchoose protocol Otherwise 2 The rst n 7 1 participants divide the cake by recursively invoking this procedure 3 Fori l2n7 1 do 4 Participant 139 divides her share into n pieces she considers of equal worth by her measure 5 Participant n collects whichever of those n pieces he considers to be worth most by his measure Theorem This cakecutting protocol is fair for every 11 Proof The proof is by induction on n The base case n 2 was already proven to be fair so let us focus our attention on the case where n gt 2 Let Alice be one of the rst n 7 1 participants Suppose Alice follows the protocol honestly By the induction hypothesis in step 2 Alice receives a share that she considers to be worth at least 1 n 7 lth of the cake In step 4 Alice divides her share into n pieces each of which must be worth at least lnn 7 1 to her No matter which piece participant n collects in step 5 Alice is left with n 7 1 pieces each worth at least lnn 7 1 so Alice is left with a share that she considers to be worth at least ln Therefore the protocol is fair to each of the rst n 7 1 participants NeXt suppose the nth participant call him Bob follows the protocol honestly Let S denote the share that participant 139 receives after step 2 and let x mBS Since step 2 divides the entire cake we know x1 xn1 1 Also in step 5 Bob is guaranteed to collect a piece from participant i that is worth at least xin to him After the protocol is nished Bob has collected pieces that in total are worth at least x1 n xn1n x1 xn1n 111 to him Therefore the protocol is fair to the nth participant D Unfortunately the recursive protocol shown above requires 11 steps to split a cake among n participants This is an unreasonable amount of work if we have many participants It also requires unreasonably precise cutting of the cake Is there a more ef cient solution One answer might be to use a socalled moving knife protocol The idea is that someone moves a knife slowly from left to right As soon as the area to the left of the knife covers at least 1 nth of the cake by your measure you are supposed to yell Stop at the top of your lungs At that point the knifeholder cuts the cake whereever the knife was when you yelled Stop the person to yell Stop receives the piece of cake to the left of the knife and the protocol continues with the remaining n 7 1 participants It is easy to see that this is fair to everyone It is fair to the rst person to yell Stop because if he followed the protocol he receives a piece that he considers to be worth 1 n Also because the other n 7 1 participants have not yelled Stop yet if they were following the protocol honestly they must consider the remainder of the cake to be worth at least 11 7 ln and by induction they are guaranteed to receive at least 1 n 7 l of the remainder CS 70 Spring 2008 Note 8 3 The movingknife solution is elegant and ef cient However we might not be completely satis ed with it For instance if we were going to implement this in a distributed system where the participants are spread around the world then the latency of Internet connections poses a challenge By the time my Stop message reaches the knifeholder the knife may have moved on a signi cant distance and someone else closer to the knifeholder may have already claimed the piece This suggests a nice challenge nd an ef cient fair cakecutting protocol for n participants without using a moving knife In fact the movingknife solution can be translated into one that does not require a moving knife as follows Each participant marks the rst point on the cake where they would have yelled Stop if there had been a moving knife We cut the cake at the leftmost of the marks and give that piece to whoever made that mark Then we continue dividing up the rest of the cake among the remaining n 7 1 parties It can be seen that this requires approximately 112 2 operations to split a cake among n parties and it is fair for precisely the same reasons that the movingknife protocol is This revised protocol is now suitable for use in a distributed system In fact you might recognize that we have basically invented an auction Each person bids by pointing to the smallest piece that they d be willing to accept Whoever s bid is smallest wins the auction and we repeat until the entire cake has been apportioned Envy free Cake Cutting Fairness is all well and good but some might say it does not account for human nature For example if n 3 I might receive a piece that I consider to be worth 1 3 but I might notice that Alice received a piece that I consider to be worth more than 13 and be envious of her This suggests looking at the notion of envy free cakecutting protocols De nition A cakecutting protocol is envy free for X if it has the following property if X follows the protocol thenX is guaranteed to receive a piece worth at least as much by X s measure as anyone else s piece is worth by X s measure no matter what happens A cakecutting protocol is envy free if it is envy free for every participant Theorem Every envyfree protocol is also fair Proof Suppose Alice receives a piece that she considers to be worth w and the other n 7 1 participants receive pieces she considers to be worth x1 xn71 respectively We know that w x1 I xn1 1 If the protocol is envyfree w 2 x for every 139 so nw ww I w 2 wx1 I xn1 1 orin other words w 2 l n Therefore if the protocol is envyfree every participant receives a piece that she considers to be worth at least ln D Theorem The cutandchoose protocol for n 2 participants is envyfree Proof If a person receives a piece she considers to be worth at least 12 by her measure than she must consider the piece received by the other person to be worth at most 12 since those two valuations must sum to l The cutandchoose protocol ensures that both Alice and Bob receive a piece that they consider to be worth at least 12 D Unfortunately the recursive algorithm described earlier is not envyfree For instance suppose n 3 and the three parties are Alice Bob and Carol In step 2 Alice and Bob might conspire to give the whole cake to Alice Then Carol will receive 1 3 of the cake from Alice and nothing from Bob in step 5 but Alice receives 23 of the cake so Carol will be envious of Alice Exercise Is the 3party movingknife protocol envyfree As it turns out it is possible to build an envyfree cakecutting protocol for n 3 participants For the curious here is one CS 70 Spring 2008 Note 8 4 1 Alice cuts the cake into three pieces that she considers to be of equal measure 2 Bob trims the piece he considers worth the most so that after trimming the remainder is exactly worth the same by his measure as the 2ndlargest The trimmings are set aside for the end 3 Carol takes whichever of these 3 pieces excluding the trimmings she considers worth the most 4 If in step 3 Carol took the piece that Bob trimmed then a Bob takes whichever of the two remaining pieces excluding the trimmings he considers worth more Alice gets the piece that neither Carol nor Bob took b Next to divide the trimmings Bob cuts the trimmings into three pieces he considers of equal worth Carol chooses one of those three whichever she considers worth most then Alice chooses one whichever she considers worth more then Bob takes whatever is left 5 Otherwise if in step 3 Carol did not take the piece that Bob trimmed then a Bob must take the piece he trimmed in step 2 Alice gets the piece that neither Carol nor Bob took b Next to divide the trimmings Carol cuts the trimmings into three pieces she considers of equal worth Bob chooses one of those three whichever he considers worth most then Alice chooses one whichever she considers worth more then Carol takes whatever is left It is possible to prove that this protocol is envyfree but we will not do so As far as I know it is an open problem to devise an ef cient protocol for envyfree cakecutting for an arbitrary number of participants CS 70 Spring 2008 Note 8 5 CS 70 Discrete Mathematics for Spring 2008 David Wagner Note 9 Modular Arithmetic One way to think of modular arithmetic is that it limits numbers to a prede ned range 01 N E 1 and wraps around whenever you try to leave this range 7 like the hand of a clock where N 12 or the days of the week where N 7 Example Calculating the day of the week Suppose that you have mapped the sequence of days of the week Sunday Monday Tuesday Wednesday Thursday Friday Saturday to the sequence of numbers 0 1 2 3 4 56 so that Sunday is 0 Monday is 1 etc Suppose that today is Thursday 4 and you want to calculate what day of the week will be 10 days from now Intuitively the answer is the remainder of 4 10 14 when divided by 7 that is 0 ESunday In fact it makes little sense to add a number like 10 in this context you should probably nd its remainder modulo 7 namely 3 and then add this to 4 to nd 7 which is 0 What if we want to continue this in 10 day jumps After 5 such jumps we would have day 4 3 5 19 which gives 5 modulo 7 Friday This example shows that in certain circumstances it makes sense to do arithmetic within the con nes of a particular number 7 in this example that is to do arithmetic by always nding the remainder of each number modulo 7 say and repeating this for the results and so on As well as being ef cient in the sense of keeping intermediate values as small as possible this actually has several important applications including errorcorrecting codes and cryptography as we shall see later To de ne things more formally for any integer m such as 7 we say that x and y are congruent modulo m if they differ by a multiple of m or in symbols x 3y mod m ltgt m divides xEy For example 29 E 5 mod 12 because 297 5 is a multiple of 12 We can also write 22 E E2 mod 12 Equivalently x and y are congruent modulo m iff they have the same remainder modulo m Notice that congruent modulo m is an equivalence relation it partitions the integers into m equivalence classes 012m71 When computing modulo m it is often convenient to reduce any intermediate results mod m to simplify the calculation as we did in the example above This is justi ed by the following claim Theorem 91 IfaE 0 mod m andb E d mod m then ab E cd mod m andab E cd mod Proof We know that cakm and db m so cdakmb m ab k m which means that a b c d mod m The proof for multiplication is similar and left as an exercise D What this theorem tells us is that we can always reduce any arithmetic expression modulo m into a natural number smaller than m As an example consider the expresion 13 11 18 mod 7 Using the above Theorem several times we can write 131118E644 mod 7 CS 70 Spring 2008 Note 9 1 E 104 mod 7 E 3 4 mod 7 E 12 mod 7 E 5 mod 7 In summary we can always do calculations modulo m by reducing intermediate results modulo m IHVBISBS Addition and multiplication mod m is easy To add two numbers a and b modulo m we just add the numbers and then subtract m if necessary to reduce the result to a number between 0 and m E 1 Multiplication can be similarly canied out by multiplying a and b and then calculating the remainder when the result is divided by m Subtraction is equally easy This is because subtracting b modulo m is the same as adding Eb E m E b mod What about division This is a bit harder Over the reals dividing by a number x is the same as multiplying by y 1x Here y is that number such that x y 1 Of course we have to be careful when x 0 since such a y does not exist Similarly when we wish to divide by x mod m we need to nd y mod m such that x y E 1 mod m then dividing by x modulo m will be the same as multiplying by y modulo m Such a y is called the multiplicative inverse of x modulo m In our present setting of modular arithmetic can we be sure that x has an inverse mod m and if so is it unique modulo m and can we compute it As a rst example take x 8 and m 15 Then 2x E 16 E 1 mod 15 so 2 is a multiplicative inverse of8 mod 15 As a second example take x 12 and m 15 Then the sequence ax mod m a 0 12 is periodic and takes on the values 0 12 963 check this Thus 12 has no multiplicative inverse mod 15 So when does x have a multiplicative inverse modulo m The answer is iff gcdmx 1 This condition means that x and m share no common factors except 1 and is often expressed by saying that x and m are relatively prime Moreover when the inverse exists it is unique Theorem 92 Let mx be positive integers such that gcdmx 1 Then x has a multiplicative inverse modulo m and it is unique modulo m Proof Consider the sequence of m numbers 0x 2x m E 1x We claim that these are all distinct mod ulo m Since there are only m distinct values modulo m it must then be the case that ax E 1 mod m for exactly one a modulo m This a is the unique multiplicative inverse To verify the above claim suppose that ax E bx mod m for two distinct values a b in the range 0 g a b g m E 1 Then we would have a E bx E 0 mod m or equivalently a E bx km for some integer k possibly zero or negative But since x and m are relatively prime it follows that a E b must be an integer multiple of m This is not possible since a b are distinct nonnegative integers less than m D Actually it turns out that gcdmx 1 is also a necessary condition for the existence of an inverse ie if gcdmx gt 1 then x has no multiplicative inverse modulo m You might like to try to prove this using a similar idea to that in the above proof Since we know that multiplicative inverses are unique when gcdmx 1 we shall write the inverse of x as x 1 mod m But how do we compute x l given x and m For this we take a somewhat roundabout route First we shall consider the problem of computing the greatest common divisor of two integers a and b gcdab CS 70 Spring 2008 Note 9 2 Computing the Greatest Common Divisor The greatest common divisor of two natural numbers x and y denoted gcdx7 y is the largest natural number that divides them both Recall 0 divides no number and is divided by all How does one compute the gcd By Euclid s algorithm perhaps the rst algorithm ever invented algorithm gcdXy if y 0 then return X else return gcd y X mod y Note This algorithm assumes that x 2 y 2 0 andx gt 0 Before proving that this algorithm correctly computes the greatest common divisor it will be helpful to prove a few lemmas Lemma 91 Ifx 2y 2 0 analx gt 0 gcdxy gcdx7yy Proof If al divides both x and y then it divides x 7 y and y If al divides x 7 y and y then it divides x and y D Lemma 92 Ifx 2 y 2 0 analx gt 0 gcdxy gcdx mod yy Proof Apply the prior lemma n times where n Lxyj D Theorem 93 Euclid s algorithm above correctly computes the gcal ofx analy in time 0n where n is the total number ofbits in the input xy Proof Correctness is proved by strong induction on y the smaller of the two input numbers For each y 2 0 let Py denote the proposition that the algorithm correctly computes gcdx7 y for all values of x such that x 2 y and x gt 0 Certainly P0 holds since gcdx7 0 x and the algorithm correctly computes this in the if clause For the inductive step we may assume that Pz holds for all z lt y the inductive hypothesis our task is to prove By the inductive hypothesis the recursive call gcd y X mod y correctly returns gcdyx mod y just take 2 x mod y and notice that 0 g z lt y Now the lemma assures us that gcdxy gcdx mod yy gcdyx mod y hence the elseclause of the algorithm will return the correct value gcdx7 y This completes our veri cation of Py and hence the induction proof Now for the On bound on the running time It is obvious that the arguments of the recursive calls become smaller and smaller because y g x and x mod y lt y The question is how fast We shall show that in the computation of gcdx7 y after two recursive calls the rst larger argument is smaller than x by at least a factor of two assuming x gt 0 There are two cases 1 y g x 2 Then the rst argument in the neXt recursive call y is already smaller than x by a factor of 2 and thus in the neXt recursive call it will be even smaller 2 x 2 y gt x 2 Then in two recursive calls the rst argument will be x mod y which is smaller than x 2 So in both cases the rst argument decreases by a factor of at least two every two recursive calls Thus after at most 2n recursive calls where n is the number of bits in x the recursion will stop note that the rst argument is always a natural number D Note that the second part of the above proof only shows that the numb er of recursive calls in the computation is On We can make the same claim for the running time if we assume that each call only requires constant time Since each call involves one integer comparison and one mod operation it is reasonable to claim that CS 70 Spring 2008 Note 9 3 its running time is constant In a more realistic model of computation however we should really make the time for these operations depend on the size of the numbers involved thus the comparison would require On elementary bit operations and the mod which is really a division would require 0n2 operations for a total of 0n2 operations in each recursive call Here n is the maximum number of bits in x or y which is just the number of bits in x Thus in such a model the running time of Euclid s algorithm is really 0113 Back to Multiplicative inverses Let s now return to the question of computing the multiplicative inverse of x modulo m For any pair of numbers x7 y suppose we could not only compute d gcdx7 y but also nd integers ab such that daxby 1 Note that this is not a modular equation and the integers a b could be zero or negative For example we can write 1 gcd3512 71 35 3 12 so here a 71 and b 3 are possible values for ab If we could do this then we d be able to compute inverses as follows If gcdmx 1 apply the above procedure to the numbers mx this returns integers a b such that lambx But this means that bx 1 mod m so b is a multiplicative inverse of x modulo m Reducing b modulo m gives us the unique inverse we are looking for In the above example we see that 3 is the multiplicative inverse of 12 mod 35 So we have reduced the problem of computing inverses to that of nding integers a b that satisfy equa tion 1 Now since this problem is a generalization of the basic gcd it is perhaps not too surprising that we can solve it with a fairly simple extension of Euclid s algorithm The following algorithm extended gcd takes as input a pair of natural numbers x 2 y as in Euclid s algorithm and returns a triple of integers d a b such that d gcdxy and d ax by algorithm extended gcdxy if y 0 then returnx l 0 else d a b extended gcdy X mod y return d b a X div y b Note that this algorithm has the same form as the basic gcd algorithm we saw earlier the only difference is that we now carry around in addition the required values a b You should handtum the algorithm on the input x7 y 357 12 from our earlier example and check that it delivers correct values for a b Let s now look at why the algorithm works In the base case y 0 we return the gcd value d x as before together with values a 1 and b 0 and it s easy to see that in case the returned values satisfy ax by d since 1 x 0 y x d Ify gt 0 we rst recursively compute values d a b such that d gcdyx mod y and daybxmody 2 Just as in our analysis of the vanilla algorithm we know that this d will be equal to gcdx7 y So the rst component of the triple returned by the algorithm is correct CS 70 Spring 2008 Note 9 4 What about the other two components Let s call themA and B What should their values be Well from the speci cation of the algorithm they must be integers that satisfy d Ax By 3 To gure out whatA and B should be we need to rearrange equation 2 as follows daybxmody ayb xi lxyly bx i lxylby In the second line here we have used the fact that x mod y x 7 Lxyj y 7 check this Comparing this last equation with equation 3 we see that we need to takeA b and B a7 Lxyjb This is exactly what the algorithm does so we have concluded our proof of correctness Since the eXtended gcd algorithm has exactly the same recursive structure as the vanilla version its running time will be the same up to constant factors re ecting the increased time per recursive call So once again the running time on nbit numbers will be 0n arithmetic operations and 0n3 bit operations Combining this with our earlier discussion of inverses we see that for any xm with gcdmx l we can compute x 1 mod m in the same time bounds CS 70 Spring 2008 Note 9 5 Computer Science 70 Discrete Mathematics The Chinese Remainder Theorem The purpose of this note is to justify in detail our formal computation that 1005025105 E 27 mod 47 Our main tool will be Euler s theorem which we recall here Theorem Euler s Theorem Let a be relatively prime to N Then awm E1 mod N where Lp denotes the Euler totient functionl You proved this result which is a straightforward generalization of Fermat s Theorem in HW 4 We will need one other fact about modular arithmetic Theorem Chinese Remainder Theorem If m and n are relatively prime positive integers the system of congruences w E a mod m w E 1 mod n has a unique solution modulo Proof We will prove uniqueness rst Suppose am and an are both solutions to the above system of congruences Then am E a E an mod m wo E b E ail mod n so in particular m divides avg E ail and n divides wo E all Since m and n are relatively prime this implies that mn divides avg E ail check that you know why this is true so am E ail mod To show existence we will construct a solution avg explicitly Since gcdm n 1 m has an inverse w modulo n and n has an inverse y modulo m Let 30 any bmw Then reducing this modulo m we have wo E any E a mod m since ny E 1 mod m and similarly for the reduction of am modulo n Thus am is the desired solution and this proves the theorem 1Recall that N is the number of positive integers n g N that are relatively prime to N 1 2 Remark The Chinese Remainder Theorem easily generalizes to the case in which we have k linear congruences with the moduli of the congruences pair wise relatively prime As an exercise formulate precisely this generalization and prove your result We are now in a position to compute rigorously the value of 5025105 100 mod 47 which we do in steps 1 We reduce the base modulo 47 so we re left with the computation of 5025105 6 mod 47 2 Subproblem We can reduce the exponent modulo 46 by Fermat s theorem since 13 47 is prime so we want to compute 5 5 502510 E42510 mod 46 While we d like to compute this by reducing the exponent 25105 mod 46 22 we can t exactly do this since Euler s theorem doesn t applyi46 and 4 are not relatively prime Instead we solve the system of linear congruences given by 5105 w E 42 mod 23 5 w E 42510 mod 2 3 Subproblem To compute 5 425 mod 23 we can apply Fermat s theorem to reduce 25105 modulo 22 and to compute this we can apply Euler s theorem to reduce 105 modulo Lp22 11712 71 10 But 105 E 0 mod 10 so 25105 El mod 22 so 5 425 E4 mod 23 4 Since 105 4 E 425 mod 2 trivially we know that 4 is a solution to the system of linear con gruences Since 425105 is also a solution we can conclude by the uniqueness statement of the Chinese Remainder Theorem that 5105 42 E4 mod 46 3 5 Thus back at the highest level we re left with the computation of 64 mod 47 which one easily nds is 27 Since we didn t discuss it in class you weren t expected to know the Chinese Remainder Theorem for the midterm continually applying Euler s theorem without regard to the technicality in step 2 above would have given you the same answer and this is what we had wanted you to do CS 70 Discrete Mathematics for Spring 2005 ClancyWagner Notes 2 This lecture covers induction which is the most common technique for proving universally quanti ed sen tences over the natural numbers and other discrete sets of objects lists trees tilings graphs programs etc We need induction or something like it because any attempt at proof by enumeration of possible worlds is doomed to failureiwith in nitely many objects there are in nitely many possible worlds that can be de ned The principle of induction The principle of induction is an axiom of the natural numbers Recall from Lecture Notes 1 that the natural numbers satisfy Peano s axioms where we have written n 1 instead of sn for clarity 0 is a natural number If n is a natural number n l is a natural number These axioms don t quite de ne the natural numbers because they include no statement of the kind and by the way there are no other natural numbers This makes it impossible to use these axioms alone to prove that any property holds for all natural numbers n The principle of induction essentially lls this gap Inforrnally it says the following If you can prove that some property holds for 0 and you can prove that the property holds for n 1 if it holds for n then you have proved that the property holds for all the natural numbers To state this principle formally let Pn be an arbitrary proposition about the natural number n For exam ple Pn might be 2quot gt 11 The principle of induction is as follows Axiom 21 Induction For any property P ifP0 and VnE N Pn gt Pn 1 then Vn EN Pn This says that ifP0 holds and P0 gt Pl and Pl gt P2 and so on then Pn must be true for all n This seems pretty reasonable Later we will see that the axiom has an alternative form that seems even more reasonable inductive proofs The standard rst example is to verify the wellknown formula for the sum of the rst n positive integers VI Theorem 21 VnEN 2i nn 12 i1 Note 21 139 means 1 2 n but is more precise When n 0 the summation has no terms so is 0 when n 1 it has just the term i 1 so the sum is 1 In many but not all cases of proof by induction the property P used in the induction is exactly the one we want to prove That is the case here Pn is the proposition that 21 139 nn l2 CS 70 Spring 2005 Notes 2 1 BASE CASE lNDUCTlVE STEP lNDUCTlVE HYPOTHES S To construct an inductive proof rst we need to establish the base case P0 then we need to prove that Pn 1 follows from Pn The latter proof is called the inductive step and usually involves all the work The key idea of induction though is that this step is easier than proving the whole universal proposition from scratch because you get to assume that Pn is true when proving Pn 1 This assumption is called the inductive hypothesis Proof The proof is by induction over the natural numbers Base case prove P0 P0 is the proposition 291 i 00 l 2 By the de nition of summation this is equivalent to 0 0 which is true Inductive step prove Pn gt Pn 1 for all VIE N n l The inductive hypothesis is 2i nn l2 11 n1 2 To prove 2 i nln22 i1 3 Reexpressing the summation for n l in terms of the summation for n for which we have the formula we have n1 n 2 139 i n l by the de nition of summation i1 i1 nn l2 n 1 using the inductive hypothesis nn122n12n1n22 VI Hence by the induction principle V11 6 N 2i nn l2 D i1 This example shows the format of an inductive proof which you should follow religiously It also exhibits the technique common to all inductive proofs the proposition Pn l is reformulated into a part that comes directly from Pn for which we already have the answer and an extra bit that is then combined with the answer from Pn to give the answer for Pn 1 Example proofs Theorem 22 Vite N7 113 7 n is divisible by 3 It will be helpful to de ne divisible by more precisely We write ab a divides b or b is divisible by a the de nition is De nition 21 Divisibility For all integers a and b ab if and only if for some integer 1 b aq As in the previous example we take the de nition of P straight from the theorem Pn is the proposition that 3 n3 7 11 Proof The proof is by induction over the natural numbers Base case prove P0 P0 is the proposition that 303 7 0 or 30 which is true from the de nition of divisibility with q 0 CS 70 Spring 2005 Notes 2 2 Inductive step prove Pn gt Pn 1 for all n6 N 1 The inductive hypothesis is 3n3 7 n or n3 2 To prove 3n 13 7 n We do this by showing that n 13 7 n 1 3r for some integer r 7 n 31 for some integer q 3 Reexpressing the quantity for n 1 in terms of the quantity for n for which we know a simple formula we have n 13 7 n 1 n3 3n2 3n 17 n 1 expanding out the cubic term n3 7 n 3n2 3n rearranging to isolate the known quantity 3q3n2n3qnzn 4 Hence since 1 and n are integers we have 3n 13 7 n Hence by the induction principle Vn E N 3n3 7 n D Again the trick is to reduce Pn 1 to Pn and a little extra fact here the little extra fact is that 33n2 3n Sometimes this step can be carried out by simple manipulation to pull Pn out of P n 1 sometimes you really have to understand what s going on at a deep level The next example proves an inequality between two functions of n such inequalities are useful in computer science when showing that one algorithm is more ef cient than another Notice that the base case is P2 rather than P0 This is an obvious variant1 of the standard principle of induction we can begin with any xed integer to show that all subsequent integers satisfy some property If we want to prove Pn for all integers including negative ones we must do two inductions7one upwards from say 0 and one downwards from 0 Theorem 23 VnEN ngt1gt n lt 11 1 Proof The proof is by induction over the natural numbers greater than 1 Base case prove P2 P2 is the proposition that 2 lt 22 or 2 lt 4 which is true Inductive step prove Pn gt Pn 1 for all natural numbers n gt 1 1 The inductive hypothesis is n lt nquot 2 To prove n1 lt n 1quot1gt 3 Reexpressing the quantity for n 1 in terms of the quantity for n for which we know a simple inequality we have n 1 n 1 k n by the de nition offactorial n 1 11 1 using the inductive hypothesis andeya agt0Axlty gt axltay lt nl nlrl usinngya xgt0Aagt 0Axlty gt xaltya n 1gtn1 Hence by the induction principle VnEN n gt 1 gt n lt nquot D 1There is a way to avoid this new Variant We can letPn be n gt 1 gt n lt n quot and prove the base caseP 0 trivially because the premise 0 gt 1 is false When we prove the inductive step of course we will need to proveP0 gt P1 andPl gt P2 simply by provingPl andP2 separately and then prove Pn gt Pn 1 for every n gt 1 The work done is exactly the same but the proof looks messier CS 70 Spring 2005 Notes 2 3 TlLNGS Not a proof Theorem 24 All Macs are the same colour Proof We rephrase as VnEN if n gt 0 then every set of n iMacs is monochromatic The proof is by induction over the number of iMacs in a set Base case prove Pl Pl is the proposition that every set of l iMacs is monochromatic This is obviously true Inductive step prove Pn gt Pn l for all natural numbers n gt 0 The inductive hypothesis states that every set of n iMacs is monochromatic Equot To prove every set of n l iMacs is monochromatic W For each set Si1 7in1 of n 1 iMacs consider the nelement subsets S1i1in and S2 iz 7in1 These sets have n 71 elements in common and their union is S 5 By the induction hypothesis S1 is monochromatic Hence i1 is the same colour as in V39 By the induction hypothesis S2 is monochromatic Hence in is the same colour as in 9 Hence all elements of the set S are the same colour ie every set of n l iMacs is monochro matic Hence by the induction principle all iMacs are the same colour D Absurd as the conclusion may seem this proof is not an easy one to diagnose because the inductive step is correct for a typical case where say n 3 It really is true that if every set of 3 elements is monochromatic then every set of 4 elements is monochromatic and so on for all larger 11 We must look to the root We know that Pl is true but P2 is false so the error must come in the inductive step when n 1 In that case S has two elements and the nelement subsets are the singletons i1 and i2 Step 4 is correct since i1 and in are the same object The error comes in step 5 although we say correctly that S2iz7 in1 this does not mean that in is an element of S2 More intuitively the inductive step relies on S1 and S2 having a nonempty intersection so that colour can be propagated from S1 to S2 When S has 2 elements this is not the case Strengthening the inductive hypothesis In all the previous examples we have taken the property Pn directly from the statement of the theorem to be proved This does not always work sometimes the inductive hypothesis fails to provide suf cient juice to connect one property to the next Let s consider an example The study of tilings is a mathematical pastime with serious implications for circuit design solidstate physics and other areas A tiling is a complete and exact covering of a region usually planar with multiple copies of some smaller shape One of the bestknown results is that an 8 X 8 region with two opposite comer squares removed cannot be tiled by 2 X l dominoes In our case a binaryobsessed computer science department wants to build its new building around a court yard of size 2quot X 2quot for some n An inept state contractor has supplied the department with Lshaped tiles to pave the courtyard Figure 1 An alert student in CS 70 proves that Vn 322quot 7 1 so any tiling is going to leave one hole No matter says the everalert department chair We ll leave one hole at the center for a attering statue of the yettobefound building donor little knowing that this would be Pokemon Toys Inc CS 70 Spring 2005 Notes 2 4 a b Figure l a An Lshaped tile b An Ltiling of a 4 X 4 region leaving one hole in a center square L L a b Figure 2 a The inductive step for the rst proof attempt a region of size 2quot1 gtlt 2quot1 with one central hole can be divided into four regions of size 2quot X 2quot Whose four central corners can be covered with one hole and one Ltile b The inductive step for the second proof attempt a region of size 2quot1 gtlt 2quot1 with one hole anywhere can be divided into four regions of size 2quot X 2quot one of the four regions contains the hole and the three central comers of the other regions can be covered with one Ltile Theorem 25 VnE N every region ofsize 2quot X 2quot with one central hole has an exact L tiling Proof Attempt l The proof is by induction over the natural numbers Base case prove P0 P0 is the proposition that a l X 1 region with one central hole has an exact Ltiling This is true requiring 0 tiles Inductive step prove Pn gt Pn 1 for all n6 N The inductive hypothesis states that every region of size 2quot X 2quot with one central hole has an exact Ltiling Equot To prove every region of size 2quot1 gtlt 2quot1 with one central hole has an exact Ltiling W The 2quot1 gtlt 2quot1 region can be divided into four regions of size 2quot X 2quot Whose four central comers can be covered with one hole and one Ltile see Figure 2a 3 Each of the four remaining regions is of size 2quot X 2quot with one hole Therefore by the inductive hypothesis it has an exact Ltiling CS 70 Spring 2005 Notes 2 5 5 If a set of disjoint regions has an exact tiling their union has an exact tiling Note this requires a separate induction Therefore every region of size 2quot1 gtlt 2quot1 with one central hole has an exact Ltiling Oops Our use of the inductive hypothesis in step 4 is awed The inductive hypothesis guarantees an Ltiling for regions with a central hole not a corner hole B When an impasse of this kind occurs you should consider strengthening the theorem you are trying to prove This is rather counterintuitiveiif you fail to prove a theorem can it make sense to prove a harder one Proving a stronger theorem has the advantage of strengthening the inductive hypothesis Pn which may enable a proof for Pn 1 But notice that it also strengthens Pn l which can be a disadvantage Sometimes it works out sometimes it doesn t As yet there is no recipe for success beyond Insight or Practice For this example the obvious strengthening is to drop the restriction to central holes Theorem 26 Every region ofsize 2quot X 2quot with one hole has an exact L tiling This is a stronger theorem because the hole is now allowed to be anywhere rather than just in the middle the old theorem is a special case If we knew this fact P n for a particular n we would certainly be able to complete the inductive step for the old Pn l in the above proof attempt because now we can tile regions with comers missing This illustrates the advantage of strengthening the theorem Unfortunately we are no longer interested in proving the old Pn li Every region of size 2quot1 gtlt 2quot1 with one central hole has an exact Ltiling Instead we must prove the stronger P n li Every region of size 2quot1 gtlt 2quot1 with one hole anywhere has an exact Ltiling Fortunately we can do this given P n The proof is illustrated in Figure 2b its detailed completion is left as an exercise There are at least two more interesting aspects of this example First the inductive proof translates very naturally into a recursive algorithm for constructing an Ltiling Second unlike previous proofs in these notes the proof is actually informal The structure of the inductive argument is perfectly OK but the detailed claims are supported by appeal to a picture rather than to general axioms This is because we have not supplied any axioms for twodimensional shapes tilings dividing regions etc For simple cases we can rely on human intuition on these topics but when it comes to tiling lldimensional regions with 9dimensional holes using lOdimensional tiles as in string theory or robotic pathplanning one must fall back on an axiomatic basis CS 70 Spring 2005 Notes 2 6 CS 70 Discrete Mathematics for Spring 2008 David Wagner Note 7 Stable Marriage 7 An Application of Proof Techniques to Algorithmic Analysis Consider a dating agency that must match up n men and n women Each man has an ordered preference list of the ri women and each woman has a similar list of the ri men ties are not allowed Is there a good algorithm that the agency can use to determine a good pairing Exam ple Consider for example ri 3 men represented by numbers 1 2 and 3 and 3 women A B and C and the following preference lists For instance the preference lists above mean that womanA is man 1 s top choice woman B is his second choice and so on What properties should a good pairing have One possible criterion for a good pairing is one in which the number of rst ranked choices is maximized Another possibility is to minimize the number of last ranked choices Or perhaps minimizing the sum of the ranks of the choices which may be thought of as maximizing the average happiness In this lecture we will focus on a very basic criterion stability A pairing is unstable if there is a man and a woman who prefer each other to their current partners We will call such a pair a rogue couple So a pairing of n men and n women is stable if it has no rogue couples An unstable pairing from the above example is 1C 2B 3A The reason is that l and B form a rogue couple since 1 would rather be with B than C his current partner and since B would rather be with 1 than 2 her current partner This is trouble Before long 1 and B are going to spending many late nights doing CS70 problem sets together Obviously the existence of rogue couples is not a good thing if you are a matchmaker since they will lead to instability or customer dissatisfaction That is why we focus on stable pairings An example ofa stable pairing is 2A1B3C Note that lA is not a rogue couple It is true that man 1 would rather be with womanA than his current partner Unfortunately for him she would rather be with her current partner than with him Note also that both 3 and C are paired with their least favorite choice in this matching Nonetheless it is a stable pairing since there are no rogue couples The problem facing us is to nd a stable pairing given the preference lists for all n men and all n women CS 70 Spring 2008 Note 7 1 Does a Stable Pairing Always Exist exlst7 ly follows 1 n t Surely th5 To demonstrate ths let us eonsroler a slrghtly fallacy m the reasomng Vlsually we have the following srtuauon A c A D For example the pamng A3 cm eontarns the rogue eouple 3 and c Usrng the reasomng above we mrght oleerole to par 3 and 5 together gyrng us the pamng 3CAD But thrs pamng ls also t s any proof that there must be a stable pamng m the olaung problem must use the fact that there are two genolers m an essenual way In fact we shall show that when we have n men anoln women a stable panng always ernsts Thls factls somewhat surpnsrng but true The Tratiitional Marriage Algorithm We wlll stuoly what ls someumes ealleol the Tradltlonal Mamage Algonthm39 IMA sorcalled beeause rt ls baseol on a 195039s moolel of olatrng where the men propose to the women anolthewomen aeeept or reject propos s p Tr dm n l M m l uthm stuoly rts many rnterestrng propemes The Tradltlonal Mamage Algonthm works llke thrs F m anin Every Arternnnn Eaeh woman says Maybe eome baektomorrowquot to the man she llkes best among the men who have proposeol to her she now has hlm on a stxmg and No 1 wrll never marry youlquot to all the rest F W F min sueeessrye day on thrs olay eaeh woman mames the man she has on a smng termrnate7 tw t 2olays cs 7n spnngznnz Note 7 2 Well for eaeh day eneept the 1ast at 1east one woman 15 erossed off some man39s hst Srnee there are 1 men days Imprnvunent Lemma Kwoman Whas man Mon a stnng on the kth day then on every subsequent day she has someone on the stnng whom she hkes at 1east as mueh as M Prnnf Suppose that on day for some e k Whas some man M1 on a smng where she hkes M1 at1east as mueh as M Possrb1y M M Srnee she has M on a smng at means that she to1o1 M1 maybe on day 2 on day H 1 M wr11eome back and propose to W agam srnee he was told maybequot the preyrous 1 1 t t day Let who propose to her on day e1 She wr11te11M maybequot on day H 1 so on day e1 she W111 have Mquot on a smng Possrb1y Mquot M1 Note that srnee M1 was one ofthe proposers on day e 1 thrs means that she musthke M at1east as mueh as she hkes M and as we stated before she l1kes M at 1east as mueh as she does M W F A 1 Mquot asM L A r V rtmust be true for all n 2 It a R F r r dw m proof see 1f you ean based on the Improvement Lemma Lemma The Tradmonal Mamage A1gonthm termrnates wrth a pamng Prnnf He 1 b 1 b ofthese women e eatt has someone on her smng Thus when the a1gonthm termrnates 1 women have 1 men on the smng not mcludmg M So there must be at 1east n1 men Contradmuon So eaeh man 15 parred up wrth hrs own partner whreh means that all 1 women have a partner as wen u for eonvenrenee ones who were to1o1 maybequot cs 7n spnngznnz Note 7 z Thus the pairing which the algorithm outputs is 1A 23 3C and this is a stable pairing Theorem The pairing produced by the Traditional Marriage Algorithm is always stable Proof We will show that no manM can be involved in a rogue couple Consider any couple M W in the pairing and suppose thatM prefers some woman W to W We will argue that W prefers her partner to M so that M W cannot be a rogue couple Since W occurs before W in M s list he must have proposed to her before he proposed to W Therefore according to the algorithm W must have rejected him for somebody she prefers By the improvement lemma W likes her nal partner at least as much and therefore prefers her nal partner to M Thus no manM can be involved in a rogue couple and the pairing is stable D Optimality Consider the situation in which there are 4 men and 4 women with the following preference lists For these preference lists there are exactly two stable pairings S 1A 2D 3C 43 and T 1A 2C 3D 43 The fact that there is more than one stable pairing brings up an interesting question What is the best possible partner for each person For instance who is the best possible partner who man 2 could hope to end up with The trivial answer is his rst choice ie womanA but that is just not a realistic possibility for him Pairing man 2 with womanA would simply not be stable since he is so low on her preference list And indeed there is no stable pairing in which 2 is paired with A Examining the two stable pairings we can see that the best possible realistic outcome for man 2 is to be matched to woman D Let us make some de nitions to better express these ideas we say the optimal woman for a man is the highest woman on his list whom he is paired with in some stable pairing In other words the optimal woman is the best that a man can do under the condition of stability In the above example woman D is the optimal woman for man 2 So the best that each man can hope for is to be paired with his optimal woman But can all the men achieve this optimality simultaneously In other words is there a stable pairing such that each man is paired with his optimal woman If such a pairing exists we will call it a male optimal pairing Turning to the example above S is a male optimal pairing since A is 1 s optimal woman D is 2 s optimal woman C is 3 s optimal woman and 3 is 4 s optimal woman Similarly we can de ne a female optimal pairing which is the pairing in which each woman is paired with her optimal man Exercise Check that T is a female optimal pairing We can also go in the opposite direction and de ne the pessimal woman for a man to be the lowest ranked woman whom he is ever paired with in some stable pairing This leads naturally to the notion of a male pessimal pairing 7 can you de ne it and also a female pessimal pairing Now a natural question to ask is Who is better off in the Traditional Marriage Algorithm men or women Think about this before you read on CS 70 Spring 2008 Note 7 4 Theorem The pairing output by the Traditional Marriage Algorithm is male optimal Proof Suppose for the sake of contradiction that the pairing output by the TMA is not male optimal This means there must eXist an earliest day let s say day k in which some man was rejected by his optimal wife Call that man M There might be multiple men who were rejected by their optimal wives on day k in that case we choose one of those men arbitrarily Let W be M s optimal wife Since M was rejected by W on day k on that day W must have accepted another man let s call him M who she likes better than M Because no man was rejected by his optimal wife before day k and because M was not rejected on day k we conclude that M has not yet been rejected by his optimal wife on day k Therefore there are only two possibilities l W is M s optimal wife or 2 on day k M has not yet proposed to his optimal wife and hence likes W better than his optimal wife Since W is M s optimal wife this means there must eXist some stable pairing call it T where they are paired together In T M must have been paired off with someone else call her W In other words T looks like this T MW7 M7 W7 Since T is stable there are only two possibilities a W isM s optimal wife or b M likes his optimal wife better than W All in all we have four cases We will show that each of these cases is impossible or leads to a contradiction Case la is impossible W and W are two different women so they can t both be M s optimal wife In case lb M likes W his optimal wife better than W In case 2a M likes W better than W his optimal wife In case lb M likes W better than his optimal wife and his optimal wife better than W so M likes W better than W In every possible case M likes W better than W And as we mentioned earlier W likes M better than M But this means that M W form a rogue couple in T M likes W better than his wife in T and W likes M better than her husband in T The eXistence of a rogue couple in T contradicts the stability of T Contradiction Thus our original assumptionithat the TMApairing is not maleoptimalimust have been incorrect D What proof techniques did we use to prove this theorem We used the wellordering principle How do we see it as a regular induction proof This is a bit subtle to gure out See if you can do so before reading on the proof is really showing by induction on k the following statement for every k no man gets rejected by his optimal woman on the kth day Exercise Can you complete the induction So men appear to fare very well by following the Traditional Marriage Algorithm How about the women The following theorem reveals the sad truth Theorem If a pairing is male optimal then it is also female pessimal Proof Let T MW7 be the male optimal pairing Consider any stable pairing where W is paired with someone else say S MW7 MW 7 Since T is male optimal we know that M prefers W his mate in T to his mate in S Since S is stable we know that M W is not a rogue couple so W must prefer her mate in S namely M to M This means that every other stable pairing must match W up to some other male who she likes at least as much as her mate in T In other words T pairs W up with her pessimal man Since W was arbitrary we see that T pairs every female with her pessimal man Therefore the male optimal pairing is female pessimal D All this seems a bit unfair to the women Are there any lessons to be learnt from this Make the rst move CS 70 Spring 2008 Note 7 5 The Residency Match Perhaps the most wellknown application of the stable marriage algorithm is the residency match program which pairs medical school graduates and residency slots internships at teaching hospitals Graduates and hospitals submit their ordered preference lists and the stable pairing produced by a computer matches students with residency programs The road to the residency match program was long and twisted Medical residency programs were rst introduced about a century ago Since interns offered a source of cheap labor for hospitals soon the number of residency slots exceeded the number of medical graduates resulting in erce competition Hospitals tried to outdo each other by making their residency offers earlier and earlier By the mid40s offers for residency were being made by the beginning of junior year of medical school and some hospitals were contemplating even earlier offers 7 to sophomores The American Medical Association nally stepped in and prohibited medical schools from releasing student transcripts and reference letters until their senior year This sparked a new problem with hospitals now making short fuse offers to make sure that if their offer was rejected they could still nd alternate interns to ll the slot Once again the competition between hospitals led to an unacceptable situation with students being given only a few hours to decide whether they would accept an offer Finally in the early 50s this unsustainable situation led to the centralized system called the National Res idency Matching Program NRMP in which the hospitals ranked the residents and the residents ranked the hospitals The NRMP then produced a pairing between the applicants and the hospitals though at rst this pairing was not stable It was not until 1952 that the NRMP switched to the Traditional Marriage Algorithm resulting in a stable pairing Until recently the algorithm was run with the hospitals doing the proposing and so the pairings produced were hospital optimal Only recently were the roles reversed such that the medical students were proposing to the hospitals In the 1990 s there were other improvements made to the algorithm which the NRMP used For example the pairing takes into account preferences for married students for positions at the same or nearby hospitals Unsurprisingly the Traditional Marriage Algorithm is also reportedly used by a large dating agency But it is apparently also used by Akamai a large web hosting company Akamai receives a great many web requests and needs to direct each web request to one of a pool of Akamai web servers Web requests are best served by nearby servers and servers that aren t currently busy are better suited to handle web requests than servers that are Apparently Akamai uses the Traditional Marriage Algorithm to match web requests to servers ef ciently where the web requests play the role of the men and the web servers are the girls Further reading optional Though it was in use 10 years earlier the Traditional Marriage Algorithm was rst properly analyzed by Gale and Shapley in a famous paper dating back to 1962 that still stands as one of the great achievements in the analysis of algorithms The full reference is D Gale and LS Shapley College Admissions and the Stability of Marriage American Mathematical Monthly 69 1962 pp 9714 Stable marriage and its numerous variants remains an active topic of research in computer science Although it is by now almost twenty years old the following very readable book covers many of the interesting developments since Gale and Shapley s algorithm D Gus eld and RW Irving The Stable Marriage Problem Structure and Algorithms MIT Press 1989 CS 70 Spring 2008 Note 7 6


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Steve Martinelli UC Los Angeles

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

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Bentley McCaw University of Florida

"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!"

Parker Thompson 500 Startups

"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."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.