DOC PREVIEW
Berkeley MATH 55 - Lecture Notes

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Math 55 - Spring 2004 - Lecture notes # 12 - Mar 2 (Tuesday)Keep Reading Sections 3.1 - 3.5 (not 3.6)(we will not cover 3.5 in detail, since it appearselsewhere in EECS curriculum, but just do a fewexamples; you don’t have to know sorting algorithms)Homework, due Mar 10(1) Let f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) for n >= 2.Let r1 = (1+sqrt(5))/2, r2 = (1-sqrt(5))/2.Prove by induction that f(n) = (r1^n - r2^n)/sqrt(5)(2) Let cost(n) be the number of additions needed to computef(n) by the following recursive algorithm:func f(n)if n=0 return(1)else if n=1 return(1)else return(f(n-1)+f(n-2))Use induction to prove that cost(n) = f(n)-1, which meansthat the cost of the recursive algorithm grows very fast,O(r1^n), i.e. about O(1.62^n)(3) Suppose g(1) = 7, g(2) = 8, and g(n)=2*g(n-1)-2*g(n-2) for n>2.Derive a closed form formula for g(n).(4) 3.3-16, 18, 50, 60, 62(5) 3.4- 8, 14, 38, 48, 50, 62Goals for today: Continue induction proofsRecursive functionsEX: So far we have been doing induction on numbers, showing P(n)is true if P(k) is true for numbers k smaller than n. But wecan also do induction on other structures besides numbers, suchas data structures that come up in programs. We illustrate witha structure called a tree, which is a special case of a graph.DEF A graph G = (V,E) consists of a nonempty set V of vertices,and a set E of edges connecting them. More formally, if a inV and b in V are vertices, then (a,b) in E means that thereis an edge connecting a,bEX: G = (V,E), V = {a,b,c,d}, E = {(a,b),(b,c),(c,d),(d,a),(a,c)}1DEF a path from node a to node c is a set of edges connectedend to end starting at a and ending at cEX: G as before, path from a to d consists of edges (a,c),(c,d)Graph GabcabcddA path from a to dEX: Other common graphs, questions people ask about themV = {cities}, E = {roads connecting them};what are shortest paths from one city to another?V = {computers}, E = {networks connecting them},what is available bandwidth for any two computers to communicate?V = {web pages}, E = {Whether one points to another}what is best answer to a web search?V = {people}, E = {Whether one person has met another}what is likely path of spread of disease?ASK&WAIT: Other examples?DEF A tree is a graph with exactly one path between any two nodes.A rooted tree is a tree with a distinguished node called arootASK&WAIT: Is G a tree?Tree 1 Tree 2RootASK&WAIT: Where is the root of Tree 2 above?Fact: if I remove the root from a tree T, and its k connecting edges,I am left with k unconnected subtrees T1,...,Tk (ie there is nopath from any node in Ti to any node in Tj)2Tree 1root and connecting edges removed root and connecting edges removedTree 2ASK&WAIT: what are k connected subtrees in figure above?Proof: let r1,...,rk be the nodes connected to the root.I need to show 2 things: that each Ti is unconnected toany other, and each Ti is a tree.I use proof by contradiction: suppose nodea in Ti and node b in Tj were connected; I will find acontradiction. Since a is connected to r and b is connectedto r in T, there must be two paths from a to r in T(the one directly from a to r and the one via b);this contradicts the fact that T is a tree.Now suppose that Ti is not a tree; I will find anothercontradiction. Ti not a tree means there are two nodesc and d in Ti with either 0 or >1 paths connecting them.If there are >1 paths connecting them in Ti, the samepaths exist in T, so T must not be a tree. If there areno paths connecting them in Ti, then there are inparticular no paths connecting them both to ri, and henceno paths in T connecting both to root; contradicting thefact that T was a tree.Thm: Let T be any tree. Let E be the number of edges ofT and N be the number of nodes. Then E = N-1.Proof: We do two slightly different proofs.First we do induction on trees,or more precisely the height H of a tree,the length of the longest path from the root to a leaf.Base case: height H = 0 means that the tree consists of theroot by itself (N=1) and no edges (E=0). Clearly E = N-1.Induction step: Assume the result is true for trees up toa certain height H, and consider a tree T of height H+1.By the lemma, if we remove the root r we get k unconnectedsubtrees T1,...,Tk, whose roots are the vertices thatwere directly connected to r. The heights of these treesis at most H, so by the induction hypothesis3#nodes(Ti) = #edges(Ti) + 1Thus#nodes(T) = SUM_{i=1}^k #nodes(Ti) + 1... the "+1" is to count the root r= SUM_{i=1}^k (#edges(Ti)+1) + 1... by induction hypothesis= SUM_{i=1}^k #edges(Ti) + k + 1= #edges(T) + 1... since the edges in T include theedges in T1,...,Tk and the k edgesconnecting T1,...,Tk to rIn the second proof, we do induction on N, the number of nodesin the tree.Base case: N=1 means there is one node, and no edges, soE=0 as desired. (This is the same base case as before.)Induction step: Assume the result is true for trees ofup to N nodes, and consider a tree with N+1 nodes.Remove any node r from T and its k adjacent edges, leavingtrees T1,...,Tk. The number of nodes in any Ti is at most N,since we removed r, so the induction hypothesis applies, and#nodes(Ti)-1=#edges(Ti). Also,#nodes(T) = sum_{i=1}^k #nodes(Ti) + 1... the "+1" is to count the node r= sum_{i=1}^k (#edges(Ti) +1) +1... by induction hypothesis= sum_{i=1}^k #edges(Ti) +k+1= #edges(E) + 1 as desired.... since the edges in T include theedges in T1,...,Tk and the k edgesconnecting T1,...,Tk to rHere is a Bogus proof: Why is it bogus?"Thm": All Berkeley students have the same color eyes.proof: We will use induction on n to prove that that if Sis a set of n Berkeley students, then all studentsin S have the same color eyes.Base case (n=1): then any set S={student} consistingof one student has the property that all studentsin S have the same color eyesInduction step: Assume the result is true for n.Let S be any set of n+1 students:4S = {s(1),s(2),...,s(n+1)}= S1 U S2 whereS1 = {s(1),s(2),...,s(n)} andS2 = {s(2),s(3),...,s(n+1)}By induction all students in S1 have the same eye color,since S1 has n members. Similarly all students in S2 havethe same eye color. In particular, they all have the sameeye color as s(2), say, since s(2) is in S1 and in S2.So all students in S have the same eye color.A function f(n) where n is a nonnegative integer is defined recursively if1) we give the value of f(0)2) we give a rule for computing f(n) from f(n-1), when n >= 1EX: f(0) = 1, f(n) = n*f(n-1)ASK&WAIT: what is a closed form formula for f(n)? proof by


View Full Document

Berkeley MATH 55 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?