Math 55 - Spring 04 - Lecture notes # 1 - Jan 20 (Tuesday)Name, class, URL (www.cs.berkeley.edu/~demmel/ma55) on boardHead TA Mike West speaks on bureaucracyAdvertise CS 70 (T Th 2-3:30) as an "honors" alternative to Ma55All material on web page and at Copy Central NorthsideRead Course Outline on web page for course rules and grading policiesYou are responsible for reading this and knowing the rules!Class outline:Basics (Chap 1) - common language for rest of courselogic (basis of proofs,logical operations in programs (CS61)hardware design (CS150))sets and functions (same proof of 3 results:(1) can show that can’t write a program toimplement every possible function,because there are more functions than programs;(2) can show it is impossible to towrite a debugger that finds "infinite loops"in other programs (CS 172))(3) there are more real numbers than rational numbers(even though there are infinitely many of bothUsed in most of math curriculumInteger algorithms (Chap 2)Big-O notation (measure approximately how fast a function f(n)increases as n increases)Using Big-O to analyze speed of algorithms (used in CS61, CS170)Prime numbers, GCD (Greatest common divisors),"modular arithmetic" (a mod b), Chinese remainder theoremApplications: generating random numbersinteger with "bignums"cryptography (eg RSA used in Netscape)(Ma 113, CS 170)More proof techniques (Chap 3)induction (knowing when a theorem, or program, is correct)(CS 17x, most of math curriculum)Probability theory and counting (Chaps 4, 5, Lenstra’s notes)analyzing, designing algorithms (CS 170, CS 162, CS 188...)1(sometimes an algorithm that uses "random numbers" isfaster than one that does not)how many ways to pair up n students into teams of 2 or 3 or ...how to gamble in Renoalgorithms that use random numbersEX suppose you build a web search engine(or web page to sell books or ...)you buy 100 PCs and put them in a roomwhen a request comes in, you pick a PC at random, and send itto that PCwhat is the average waiting time to service a request?Read Chapter 1 of book, homework due Wednesday Jan 28at the beginning of sectionDo problemssec 1.1: 6, 16(a,c,e,g), 40, 42, 48, 601.2: 4a, 8(a,b), 10 (for 8a and 8b), 20, 38 (assume results of 36, 37)1.3: 8, 14, 26(a,c,e), 56(a,b)1.4: 4, 8(a,c,e), 28(a,c,e,g,i)1.5: 6, 8(a,c,e), 22, 52Begin course:DEF: Proposition is a statement that must be eithertrue (T) or false (F)EG: 2+2 = 4 (Y)2+2 = 3 (Y)Is 2+2=4? (N)Let x = 3. (N)x+1 = 2 (N, unless we know the value of x)Every even number > 2 is the sum of two primes. (Y)Notation: propositions denoted p,q,r ...DEF: not p , p or q (disjunction), p and q (conjunction),p xor q (exclusive or)Truth tablesDEF: a compound proposition is formed by simple propositionsconnected by logical operators and parentheses;EG: (p and q) or (r and s)programming example belowDEF: p -> q, "if p, then q", "p implies q", "p sufficient for q","q necessary for p"; p -> q same as not(p) or q;EG: if it is sunny, then we go to the beach2p = it is sunny, q = we go to the beach(T unless it is sunny (p) and we don’t go (not q))Truth tableASK&WAIT EG: if (today is Friday), then (2+3 = 6);on which days is this true?p = (today is Friday), q = (2+3=6)T every day except FridayASK&WAIT EG: if (1+1=3) then (2+2=4)Note that p and q need not have anything to do with one anotherin order to form the expression p -> qDEF: The converse of p -> q is q -> p; they need not be trueat the same timeASK&WAIT EG: If I am exactly 18 years old then I am allowed to vote;converse isif I am allowed to vote, then I am exactly 18 years oldnote that converse not necessarily true if original isDEF: The contrapositive of p -> q is not q -> not p;these are the sameASK&WAIT EG: If I am exactly 18 years old then I am allowed to vote;converse isif I am not allowed to vote, thenI am not exactly 18 years oldcontrapositive is trueTruth table proof of prop <=> contrapositiveDEF: p <-> q "p if and only q", "p->q and q->p", biconditionalApplication to programming (C or C++ syntax)if (compound proposition, or logical expression) then do something...if ((n>0) && (m<k)) then do something ...(n>0) and (m<k) are propositions whose value (T or F)can be evaluated when you get to this line in the program,and && means "and", || means "or", etc.in computer 1 represents true and 0 false (representation detailsin CS61C, CS150)Application to Web searchIn www.google.com you can type into the Advanced Search form:With all the words: guanoand With at least one of the words: geometry tickleSame as "find all web pages W for which the proposition is true"3(W contains guano) and((W contains geometry) or (W contains tickle))ASK&WAIT: what web pages do you get?EX: Geometry Learning center page on disease histoplasmosis,caused by fungus growing in bat guano,contains guano and geometry, not tickleEX: Magazine article about "tickle down economics"of Christmas toys and a town in Floridathat smells like alligator guanocontains guano and tickle, not geometryEX: poem in on-line poetry magazine Lynxcontains all 3Now let’s try google withWith all the words: guanoand With at least one of the words: geometry tickleand Without the words theASK&WAIT: Same as "find all web pages W for which the proposition is true"(W contains guano) and((W contains geometry) or (W contains tickle)) and(not(W contains the))ASK&WAIT: what web pages do you get?EX: "G" page of an Esperanto dictionarycontains guano, geometry, not tickle or the................Next Goal: simplifying compound propositions or replacingan expression depending on p, q, r, ... combined with"and", "or", etc. with another "equivalent" and "simpler"one that has the same truth/false value for all values ofp, q, r, ... (just like when you learned algebra in high school;algebra with variables that can only have values True and Falseis called "Boolean Algebra")What is "equivalence"?DEF: p <-> q means (p -> q) and (q -> p); true if p and q areboth true or both false (show truth table)DEF: propositions p and q are called logically equivalent ifp <-> q is always true (a tautology); write p <=> q;EG: p <=> not(not(p))EG: p or not(p) <=> True (p or not(p) a "tautology")EG: p and not(p) <=> False (p and not(p) a "contradiction")4When is q "simpler" than p? Roughly, if q is a "smaller"compound expression, with fewer operations like and, or etcMotivation:1) Proofs: if the compound prop. p equivalent to True(p a tautology), then you have proved a theorem2) In programming, simple expressions (in "if"