Popular in Course
verified elite notetaker
Popular in Nursing and Health Sciences
This 167 page Class Notes was uploaded by Dr. Kurtis Nolan on Sunday September 6, 2015. The Class Notes belongs to N 1 at University of Texas at Austin taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/181627/n-1-university-of-texas-at-austin in Nursing and Health Sciences at University of Texas at Austin.
Reviews for FIRST
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/06/15
Let39s Look at Some Problems int alpha beta alpha 3 beta 2 5 10 l Lexical analysis Scan the program and break it up into variable names numbers etc 2 Parsing Create a tree that corresponds to the sequence of operations that should be executed eg 1 0 25 3 Optimization Realize that we can skip the first assignment since the value is never used and that we can precompute the arithmetic expression since it contains only constants 4 Termination Decide whether the program is guaranteed to halt 5 Interpretation Figure out what if anything useful it does A Framework for Analyzing Problems We need a single framework in which we can analyze a very diverse set of problems The framework we will use is Language Recognition A language is a possibly in nite set of nite length strings over a nite alphabet Languages 12 0123456789 L W e 2 W represents an odd integer W e 2 the last character of W is 1357 0r 9 0U1U2U3U4U5U6U7U8U9 1U3U5U7U9 2 Z L W e 2 W has matched parentheses the set of strings accepted by the grammar S gtS S gtSS S gt8 Languages 3 L w W is a sentence in English Examples Mary hit the ball Colorless green ideas sleep furiously The Window needs fixed 4 L w W is a C program that halts on all inputs Encoding Output in the Input String 5 Encoding multiplication as a single input string L w ofthe form ltintegergtxltintegergtltintegergt Where ltintegergt is any well formed integer and the third integer is the product of the rst two 12X9108 1212 12X8108 6 Encoding prime decomposition L w ofthe form ltintegerlgtltinteger2gtltinteger3gt Where integers 2 r1 represent the prime decomposition of integer 1 1535 22 More Languages 7 Sortng as a language recognition task L 2 W1 W2 Eln 21 W1 is of the form intl intz intn wz is of the form intl intz intn and W2 contains the same objects as W1 and W2 is sorted Examples l5396l3569 e L l5396l234567 9 L 8 Database queryng as a language recognition task L d q a d is an encoding of a database q is a string representing a query and a is the correct result of applying q to 1 Example name age phone John 23 5671234 Mary 24 2349876 select name age23 John E L The Traditional Problems and their Language Formulations are Equivalent By equivalent we mean If we have a machine to solve one we can use it to build a machine to do the other using just the starting machine and other functions that can be built using a machine of equal or lesser power Consider the multiplication example L w ofthe form ltintegergtxltintegergtltintegergt where ltintegergt is any well formed integer and the third integer is the product of the rst two Given a multiplication machine we can build the language recognition machine Given the language recognition machine we can build a multiplication machine A Framework for Describing Languages Clearly if we are going to work with languages each one must have a nite description Finite Languages Easy Just list the elements of the language L June July August Infinite Languages Need a nite description Grammars let us use recursion to do this Grammars 1 1 The Language of Matched Parentheses S gtS S gtSS S gte 2 The Language of Odd Integers S gtO S gtOS S gtIS S gt2S S gt3S S gt4S S gtSS S gt6S S gt7S S gt8S S gt9S O gt1 O gt3 O gt5 O gt7 O gt9 Grammars 2 S gtO S gtAO A gtAD A gtD D gtO D gtE O gt1 O gt3 O gt5 O gt7 O gt9 E gtO E gt2 E gt4 E gt6 E gt8 Grammars 3 3 The Language of Simple Arithmetic Expressions S gt lteXpgt lteXpgt gt ltnumbergt lteXpgt gt lteXpgt lteXpgt gt lteXpgt lteXpgt gt lteXpgt lt0pgt lteXpgt lt0pgt gt ltnumbergt gt ltdigitgt ltnumbergt gt ltdigitgt ltnumbergt ltdigitgt gtO123456789 Grammars as Generators and Acceptors Top Down Parsing 4 3 Bottom Up Parsing The Language Hierarchy Recursively Enumerable Languages Recursive Languages ContextFree Languages Regular Languages Regular Grammars In a regular grammar all rules must be of the form ltone nontermina1gt gt ltone termina1gt or a 0139 ltone nontermina1gt gt ltone termina1gtltone nonterminalgt So the following rules are okay S gt8 S gta S gtaS But these are not S gt ab S gtSS aS gtb Regular Expressions and Languages Regular expressions are formed from Q and the characters in the target alphabet plus the operations of o Concatenation 043 means 0c followed by B 0 Or Set Union ocuB means 0c Or Union 3 o Kleene oc means 0 or more occurrences of 0c concatenated together 0 At Least 1 of means 1 or more occurrences of 0c concatenated together o 0 used to group the other operators Examples 1 Odd integers 0U1U2U3U4U5U6U7U8U91U3U5U7U9 2 Identi ers AZAZ U09 3 Matched Parentheses Context Free Grammars 1 The Language of Matched Parentheses S gtS S gtSS S gt8 2 The Language of Simple Arithmetic Expressions S gt lteXpgt lteXpgt gt ltnumbergt lteXpgt gt lteXpgt lteXpgt gt lteXpgt lteXpgt gt lteXpgt lt0pgt lteXpgt lt0pgt gt ltnumbergt gt ltdigitgt ltnumbergt gt ltdigitgt ltnumbergt ltdigitgt gtOl123456789 Not All Languages are ContextFree English S gtNP VP NP gttheNP1NP1 NPl gtADJ NP1N N gtb0y boys VP gtVV NP V gtrun runs What about boys runs A much simpler example anbnc n 2 1 Unrestricted Grammars Example A grammar to generate all strings of the form anbnc r1 2 l S gt aBSc S gt ch Ba gt aB BC gt be Bb gt bb The Language Hierarchy Recursively Enumerable Languages Recursive Languages ContextFree Languages Regular Languages A Machine Hierarchy Turing Machines Finite State Machines 1 An FSM to accept odd integers Finite State Machines 2 An FSM to accept identifiers 39 blank delimir 0r digit letter or digit delimiter or blank anything An FSM to accept the balanced parentheses language Pushdown Automata A PDA to accept strings with balanced parentheses W o Examplei 00 Stack Pushdown Automaton 2 A PDA to accept strings of the form WWR aa W a aa A Nondeterministic PDA A PDA to accept strings of the form WWR PDA 3 A PDA to accept strings of the form anbnc11 Turing Machines A Turing Machine to accept strings of the form a b cquot dR gayR bfR a fL b beR cfL lt f df9 fd toletatatbtblctctalel A Two Tape Turing Machine A Turing Machine to accept WWR ltgtlelalblalallahba949 ll A Two Tape Turing Machine to do the same thing ltgt9 la lblala lalalblale 9 ltgt9 la lblala lalalblale 9 l Simulating k Tapes with One A multitrack tape l QDOGD 9 099 a O OltgtOltgt oo wm OU OU 05330333 OU OCD Can be encoded on a single tape with an alphabet consisting of symbols corresponding to Oab9 X 01 X Oab9 X O1 Example 2nd square 90a1 Simulating a Turing Machine with a PDA with Two Stacks ltgtlabaaalalblal I ll olwlviwlwi wlvlwlml The Universal Turing Machine Encoding States Symbols and Transitions Suppose the input machine M has 5 states 4 tape symbols and a transition of the form saqb which can be read as in state 5 reading an a go to state q and write b We encode this transition as q000a00q010a01 A series of transitions that describe an entire machine will look like q000a00q010a01q010a00q000a00 The Universal Turing Machine a a b aOOaOOaOl q000 Church39s Thesis ChurchTuring Thesis An algorithm is a formal procedure that halts The Thesis Anything that can be computed by any algorithm can be computed by a Turing machine Another way to state it All quotreasonablequot formal models of computation are equivalent to the Turing machine This isn39t a formal statement so we can39t prove it But many different computational models have been proposed and they all turn out to be equivalent Example unrestricted grammars A Machine Hierarchy Turing Machines Languages and Machines Recursively Enumerable Languages Recursive Languages ContextFree Languages Regular Languages F SMs Turing Machines Where Does a Particular Problem Go Showing What it is generally by construction of o A grammar or o A machine Showing What it isn39t generally by contradiction using 0 Counting Example anb11 0 Closure properties 0 Diagonalization 0 Reduction Closure Properties Regular Lanugages are Closed Under I Union I Concatenation I Kleene closure I Complementation I Reversal I Intersection Context Free Languages are Closed Under I Union I Concatenation I Kleene Closure I Reversal I Intersection with regular languages Etc Using Closure Properties Example L anbmcp r1 m or m 7 p is not deterministic contextfree Two theorems we39ll prove later Theorem 371 The class of deterministic context free languages is closed under complement Theorem 352 The intersection of a contextfree language with a regular language is a contextfree language If L were a deterministic CFL then the complement of L L39 would be a deterministic CFL But L39 m abc anbncn which we know is not contextfree much less deterministic contextfree Thus a contradiction Diagonalization The power set of the integers is not countable Imagine that there were some enumeration 1 2 3 4 5 Set 1 1 Set 2 1 1 Set 3 1 1 Set 4 1 Set 5 1 1 1 1 1 But then we could create a new set INewSet I I I I1I I But this new set must necessarily be different from all the other sets in the supposedly complete enumeration Yet it should be included Thus a contradiction More on Cantor Of course if we39re going to enumerate we probably want to do it very systematically eg 1 2 3 4 5 6 7 Set 1 1 Set 2 1 Set 3 1 1 Set 4 1 Set 5 1 1 Set 6 1 1 Set 7 1 1 1 Read the rows as bit vectors but read them backwards So Set 4 is 100 Notice that this is the binary encoding of 4 This enumeration will generate all nite sets of integers and in fact the set of all nite sets of integers is countable But when will it generate the set that contains all the integers except 1 The Unsolvability of the Halting Problem Suppose we could implement HALTSMX M string representing a Turing Machine X string representing the input for M If MX halts then True else False Then we could de ne TROUBLEX X string If HALTSXX then loop forever else halt So now what happens if we invoke TROUBLETROUBLE which invokes HALTSTROUBLETROUBLE If HALTS says that TROUBLE halts on itself then TROUBLE loops IF HALTS says that TROUBLE loops then TROUBLE halts Viewing the Halting Problem as Diagonalization First we need an enumeration of the set of all Turing Machines We39ll just use lexicographic order of the encodings we used as inputs to the Universal Turing Machine So now what we claim is that HALTS can compute the following table where 1 means the machine halts on the input ll 12 I3 TROUBLE 15 Machine 1 1 Machine 2 l 1 Machine 3 TROUBLE l 1 Machine 5 l l l l But we39ve defined TROUBLE so that it will actually behave as ITROUBLE I 1 1 I1 I Or maybe HALT said that TROUBLETROUBLE would halt But then TROUBLE would loop Decidability Recursiyely Enumerable Languages Recursive Languages ContextFree Languages Regular Languages Can always say yes or no Can enu 39 0 ll 7 an say yes by enumerating and checkin Let39s Revisit Some Problems int alpha beta alpha 3 beta 2 5 10 l Lexical analysis Scan the program and break it up into variable names numbers etc 2 Parsing Create a tree that corresponds to the sequence of operations that should be executed eg 1 0 25 3 Optimization Realize that we can skip the first assignment since the value is never used and that we can precompute the arithmetic expression since it contains only constants 4 Termination Decide whether the program is guaranteed to halt 5 Interpretation Figure out what if anything useful it does So What39s Left 0 Formalize and Prove Things 0 Regular Languages and Finite State Machines 0 FSMs o Nondeterminism 0 State minimization 0 Implementation 0 Equivalence of regular expressions and FSMs 0 Properties of Regular Languages 0 ContextFree Languages and PDAs o Equivalence of CFGs and nondeterministic PDAs 0 Properties of contextfree languages 0 Parsing and determinism o Turing Machines and Computability o Recursive and recursively enumerable languages 0 Extensions of Turing Machines 0 Undecidable problems for Turing Machines and unrestricted grammars LECTURE 2 INTRODUCTORY SIGNAL PROCESSING IDEAS In this lecture well look at some basic properties of nite energy digital signals in other words sequences at in 2X for some discrete set X which almost always will be the set Z of all integers and so we will write 2 instead of the more formal 2Z if needed we could restrict attention to sequences in which only finitely many of the 7 are non zero but that7s usually not necessary from a strictly mathematical point of view From a practical point of view the values of the 7 would almost certainly be real but its actually more illuminating to allow complex valued sequences and so that7s what we shall do From a mathematical point of view what will be crucial is the fact that translation 11 a n m is defined on Z for all integers m but to appreciate fully the mathematical and signal processing ideas you need to keep track of how and where the space 2 is being used On some occasions it is a space of finite energy signals while on others it is a space of coe cz39ents of elements of an inner product space with respect to some orthonormal family The interplay between mathematics and signal processing ideas will be a recurring theme in this and subsequent lectures 21 Examples decompositions l The simplest such signal is the unit impulse 1 710 60106n 6 0 n7 0 26 6 50 to use the notation of the previous lecture Similarly each of the 501 is a finite energy digital signal in which only one entry is non zero 2 Each of 80W ltE2n 62711 gt 82301 6271 i Sewn is a finite energy signal such that Eg0 E 5lt gt 1 3 There are also oscillatory signals fix a real number 50 and define Ego by 6 0 52 n o For no value of 50 does Ego have finite energy and hence does not belong to E however Nonethelessif we fix integers k N 0 S k lt N and define 6w by 6wn wn w 627m39kN Then w is an Nth root of unity since wN 62 l for each choice of k Again the digital signal 6w cannot have finite energy but it has the important property that it is N perz odz c so it belongs to 2ZN 1 To get started lets look at a particularly simple signal a 0 54 79 0 550gt4elt1gt 75 953 having just 4 non zero entries calculations show that Ea 171 It admits a decompo sition a 0 NM 9 880 1 1 0 4 4110 into what we might call its coarse details obtained by averaging pairs of consecutive terms and its ne details obtained by differencing7 pairs of consecutive terms There are 8 non zero terms in this decomposition but each value is repeated twice so we should be able to express this decomposition by 4 terms To achieve this observe that we can write 9 9 9 16 7 7 7 0 7 1 022880 st g0 and 1 1 1 2 0 7 if 71 1 0 70771 7 727 27 7 7 7 7 sothat 9 16 1 2 7 077 170771 a V550 Visa Visa Visa is a more compact way of representing the coarse 1 fine detail decomposition of a more compact because we need only 4 coef cients But is there some clever7 way of expressing how these 4 coef cients are obtained Well simple calculations show that 9 16 7 0 7 1 a so mo while 1 2 7 0 7 7 1 i a i a 2 lt s0 s0 Consequently a asolt0gtgteolt0gtltmeolt1gtgteolt1gtltm lt0gtgt ltOgtlta lt1gtgt lt1gt coarse details fine details Thus we see how the orthonormal families introduced in the previous lecture provide one decomposition of a signal into its coarse and fine details note that a change in the orthonormal families will change the decomposition of course Whats the point We obtain 25 compression of a taking a a500800a801501a 1 1 with only 0292 loss of energy and 50 compression taking a w a 500 500 a 501 501 with only 1461 loss of energy In this lecture the objective will be to see how such decompositions can also be achieved using ltering After that the process of choosing various filters can begin 22 Delay convolution Various linear operators on 2 will be needed Engineers make frequent use of the Delay operator S a xn1n mathematicians would call this a translation operator on the additive group Z of integers Since ESac Z ln71l2 Z 95an Ea S is energy preserving The most important operator of all however is convolution or ltering as engineers call it Recall first that the convolution h gtk x of two sequences is defined by in operator terms hm Z hmsma To check that convolution is well defined on finite energy signals observe that by the triangle inequality E12hgtmr E12Z thmac m 7 Z lhmlE12Smx hm E12 4 since ESac Consequently the convolution h gtk it of a nite energy signal it will itself have finite energy provided 7 lt oo ie when the coef cients of h are absolutely convergent in particular the convolution it 6 h gtk it will map finite energy signals to finite energy ones if only finitely many h 31 0 Now the convolution operator it 6 h gtk it will have an adjoint on 2 But what form will this adjoint take Well given sequences at and y y n we see that hgtkacy Z hnmxmgty7 Z hnmy7gtacm achgtky m where the last convolution is de ned by hy Z hnimyna if h n 23 DiscreteTime Fourier Transform Given a sequence at xnn its Discrete Time Fourier Transform DTFT it a E is defined by Z M 6 2quot in signal analysis one usually writes X 5 instead of if and we shall often follow this convention The sum makes good sense if only finitely many 7 31 0 In this case 555 can be interpreted as the inner product 9660 X of it with the oscillatory signal eg defined in the previous section except that we have to be careful because eg does not have finite energy in addition because each exponential function e Z Ving has period 1 X has period 1 De nition The Discrete Time Fourier transform X of a nite energy signal it will be called the Frequency Response function of ac It is often useful to think of these period 1 functions X as functions on 7 Since eZWing foo lt n lt 00 is orthonorrnal in L2 it follows that 12 2 mo Xlt5gt d5 712 12 71 6727mm 7 n 12 2ds Z w Consequently it a X is energy preserving as a mapping from 2 into L2 One property of the DTFT is that 2 7171 672nm 672wi X ie the Discrete time Fourier transform mops delay into modulation Which is a signal processing way of talking about pointWise multiplication by the oscillatory function e Z Vig But a more crucial property is the following Theorem The DTFT mops quot into I 39 t 39 quotIquot t39 more precisely 71135 eas Hlt5gtXlt gt for all real 5 Proof by definition 5 Z hnqn 3cm e ZWing Z hnim 7 672wim 672winim Which after simplification becomes hnim 572Wiltn7mgt gt 2 rm 5727fim completing the proof D Corollary The Frequency Response function of the adjoint hquot hnn is given by We lt5 115 2 new Proof by definition We Z Z 11 62mg Z mum m n completing the proof D The adjoint of the DTFT de nes a linear mapping from L2 into 2 As we shall see in the next lecture this is almost the same as the Fourier coef cient mapping By Parseval7s theorem applied to the DTFT x y 112 Maw15 112 X ltZ yne2mggtd5 12 12 12 I Z Xlt5gt62sty7 Z w n 12 n for all nite energy sequences at y From this it follows that 12 I m X lt5 62mg d5 12 thereby recovering x from its Frequency Response function In fact if we get clever7 here and write 11 ac Zn j X552m n d5 an 12 we can actually regard this as yet another way of representing a signal this time in terms of its Frequency Response function When a periodic signal is studied using Fourier analysis techniques is the most important way of representing this signal 24 z transform The forward z transform Xz of a signal at is defined by Z xnz z E C As 2 eZWig on the unit circle in the complex plane X627ri 2 71 6727mm in other words the z transform of x can be regarded as the extension of the Discrete Fourier transform of x from the unit circle to the whole complex plane C Perhaps not surprisingly engineers make a lot of use of complex analysis poles zeros Residue theorem etc in signal analysis as does Daubechies at a crucial stage in her construction of wavelets Basic to all of sub band coding are two sample rate changes in other words they are involved in changing resolution They have a particularly informative description as operators on 2 as well as in terms of Discrete Time Fourier transforms 7 25 Sampling rate changes I Down sampling or sub sampling a signal at produces a new signal 12W 2nm by discarding all odd indexed terms from x and re indeXing clearly Eltlti2m 2 mm 3 Z W2 Ea Notice that L 2 L 2y irrespective of the values of their odd indexed terms 27 2127 thus different sequences may coincide after downsampling On the other hand in Fourier terms XltsgtXltsgt 3 Memo maxmm 71 eiwin 171n 2 2 627mg Consequently lt1 2gtxltsgt Xltsgt X65 a Notice that each of the functions X65 X65 has period 2 but When we add them we end up With a period 1 function As an illustration consider the signal at Whose Frequency Response function is the period 1 function Xlt5gt 135H 0 5 X 1 X its graph is 8 Plotting the graphs of all three of X X l 945 on the same axes we thus obtain X X NiH X5 X5 13155 The figure makes clear that the graph of X65 is simply the graph of X in frequency by 1 signal processing language calls X65 an alias of X65 5 shifted 1 5 26 Sampling rate changes II Ugo sampling is the converse of down sampling Given a signal y y n up sampling produces a new signal 1271 24717 T 2y Unjh v2n1 0 by inserting zeros between consecutive terms of y and relabelling ln mathematical terms up sampling is the adjoint of down sampling indeed on sequences at and y 2a y Z 271147 7 2ya 71 6 2 77 More is true in fact since Em 2gtygt Z w iv2n12 Z W Eu 77 77 it is clearly energy preserving On the other hand in terms of the DTFS Time Z gnaw ms 9 which is now a period function so up sampling decreases periodicity more precisely it halves it Finally we come to the notion that dominates the theory of wavelets whatever point of view is adopted 27 Filtering The term lter7 suggests removal7 or selection7 and this is precisely what a lter does to a signal as will be made precise shortly think of passing water through a lter to purify it or to make a cup of coffee We adopt a theoretical de nition A discrete lter is a linear time invariant operator acting on 2 in other words it is a linear operator H mapping nite energy signals to nite energy signals and satisfying HSx SHac with respect to the delay operator S Any such operator is given by convolution H at hgtkac hlicnln with a given sequence hnn the sequence of lter coe icients Another way of writing this is H 2 hi 5 Ha 2 hi 5 i i a form which has the advantage of making the time invariance of H very clear since Sam 52 hls x Z hlSlHac hls syc Hose l l I When only nitely many of the hm 31 0 it is usual to say that H is an FIR Finite Impulse Response lter by contrast with the case of an HR ln nite Impulse Response lter where in nitely many of the hm 31 0 A lter is said to be causal when hl 0 i lt 0 the point being that in terms of convolution Z hl nil i 2 0 so H107 depends only on 7 and earlier terms mm m lt rt in the signal when H is causal Most of the lters H we shall study are FIR lters so there is no question that H is well de ned and we don7t care if the lters are causal But how does a lter actually lter7 a signal Well the DTFT maps convolution to pointwise multiplication so it 7196 hm 175 H X 10 where as before 115 Z mamquot z is the Frequency Response function of the filter coef cients of H But then in view of representation H 12 I W Z Hlt5gtXltsgte2m dselt gt n 712 in other words the action of H is to select or reject frequencies in a signal Filters come in many avors7 depending on how these frequencies are selected or rejected a ideal takes only the values 0 l b low pass 5 gt a gt 0 for some 0 lt a lt c high pass 5 lt a gt HQ 0 for some 0 lt a lt Typical but unrealistic examples are high pass l ow pass Thus a low pass filter keeps only low7 frequencies in some band about the origin while a high pass filter keeps only high7 frequencies in some band not including the origin No FIR filters can be low or high pass in this sense defined above however Indeed if H is a FIR filter with filter coef cients ho hl hL1 for some L say then hl hL1 H h 7 7 7 2 0 2 2L71 2L71 for some polynornial P So HQ has at most finitely many zeros hence cannot vanish on any interval The best that HQ can do is vanish at a point so we shall adopt the following definition 11 De nition An FIR lterH will be said to try hard to be a low pass lter when H0 31 0 and 0 by contrast H will be said to try hard to be a high pass lter when 110 0 and 13 7e 0 A key step in Daubechies construction of wavelets is to associate a high pass7 FIR filter H to any low pass7 FIR filter For suppose H has filter coef cients h l and Frequency Response function we 2 hi 110 7e 0 Heb 0 Now de ne H to be the FIR filter having filter coef cients h 71 bl One of the problems for this lecture asks you to show that the corresponding Frequency Response function HQ is given by me Z ENIEC W 7672 er a in particular therefore H0 7e 0 Hi 7e 0 Hi 0 m0 0 so H tries hard to be a high pass lter when H tries hard to be a low pass filter Examples Let7s look at three examples to make this clearer Notice that in these exam ples we are allowing the number of filter coef cients to increase from 2 to 3 and then to 4 There must be some pattern to thisll l The Haar filters h andli are causal FIR lters de ned by 7 05 0 h 711 h 7 711 0 n7 0l 0 n7 0l I realize l7m using the same notation for different things you have to work out the precise meaning from contextll Shortly everything will settle down and h will mean just one thing Simple calculations show that their respective Frequency Response functions H and HQ are given by H xie m39g cos7r5 le mf sin7r5 12 As often happens With attempts to graph a Fourier transform however the presence of complex values forces us to graph absolute values of the particular Fourier transform With that in mind we obtain for the graph of Thus gt 0 in a neighborhood of 5 0 While 0 This is about the best a polynomial can do in behaving like a low pass filter the only question and an absolutely key one for the Daubechies filters is how many zeros does H5 have at 5 i Does it have zeros up to order 1 or 2 or some large finite integer value In the Haar case the order of the zero of H5 at 5 i is one On the other hand the graph of is so gt 0 in a neighborhood of 5 i While 0 0 Again this is the best a polynomial can do in behaving like a high pass filter the only question being the order of the zero at 5 0 In the Haar case the order of the zero of H5 at 5 0 is one 2 Tent filter it is easy and important to increase the zeros of a low pass filter at 5 i For let 9 be the filter having filter coef cients 5 0727 9n nil 0 otherwise lts frequency response function G 6727 cos713952 now has a double zero at 5 i and the associated filter 6 275 g i n i 0 77 7 7 0 otherwise has Frequency response function 65 sims Clearly g is trying hard to be a high pass lter having a double zero at the origin 3 Daubechies db2 filter even at this early stage its impossible to resist introducing the famous Daubechies db2 filter coef cients we do resist for the moment saying where they come from however There are 4 coef cients and they are defined by 71 h 73 h 737 h iiixi 0 7 1 7 2 7 3 with corresponding Frequency response function H 6737 cos 92 cos W5 ixgsin 71f To check this expression for H its probably easiest to start with the given expression and then use trig identities to write H as a finite sum 20 hne ZWing Clearly db2 tries hard to be a low pass filter Notice that the presence of the cos W 2 term ensures that H has a zero of order 2 at 5 i This is the reason why it is often referred to as the db2 filter the Haar could well be called the dbl filter Others refer to the db2 filter as the D4 filter because it has 4 coef cients We have followed Matlab in the choice of notation because you will be making good use of its Wavelet toolbox 28 Filtering together with updown sampling Finally let7s put these crucial operations of filtering and updown sampling together Given an FIR filter H consider the operators 1 l2o7 gtZ gawk HoT2zxgtlehngl z l on a sequence What7s perhaps not clear is why we use i 2 o 71 instead of l 2 0H to see why note that HoT2 T2OH l2oHquot 14 thus the first operator is just the adjoint of the second More crucial perhaps is the question of just what the effect of these operators is on a signal The S o 8 example from chapter 1 will provide the answer In terms of Frequency Response functions 120 HM lt5 Hlt gtXltsgt 1165 gtXlt s while 710 T 2W 5 H X2 These results though useful later shed little light on the coarsefine decomposition we started out with Patience Let7s look first at the effect of these operators on sequences themselves Example Consider the case of the Haar filters 7 05 710 hn 711 hn 7 711 0 n7 01 0 n7 01 Now fix sequences a ann c cub and recall the sequences g0 n Evin 1 1 n 7 62 62711 01 7 62 62711 so so 5 defined in lecture 1 as well as being discussed earlier in this lecture Since the filter coef cients are real we can omit complex conjugates in and compute using the convolution formulas in 1 j 2 o Hquot averaging operator 1 120 WWI Z lta2n 02n1 11 50W 2 j 2 0 flquot difference operator j 20 ga Z lgn 7 127 801 aa 3 H o T 2 spreading operator 1 7 2m cm n 3 E clhn2l 1 HOT2C E 07 gram z We 11 2m 1 n 4 77 0 T 2 spread and oscillate 1 7 2m cma n 5 2 cl inky 1 Ho T 2c Z an 501 z i cm n 2m l n Whats the point Combining l and 3 we see that HOT2O12O 71 Z a WORN which is just the orthonormal series expansion of a with respect to the family g0 n while combining 2 and 4 we see that e T 2 o 1 2o ma Z a WW n which is the orthonormal series expansion with respect to the second family n But together we know that the two families form a complete orthonormal family in 2 Hence we have obtained a splitting a Z 1 WOW Z a n of a which was seen earlier to split a into coarse7 and fine7 details The coarse details thus come from ltering with a filter trying hard to be low pass while the fine details come from filtering with an associated filter trying hard to be high pass This is exactly what sub band coding is all about We need to try this with different filters Summary So why all this emphasis on down sampling and up sampling Well we are going to use two lters one low pass to single out low frequency terms coarse details and the other high pass to single out the high frequencies fine details in a signal the Haar H and 77 for instance But a convolution h gtk x contains just as many terms as the original sequence at so if we use two of them we will end up with twice7 as many terms as we had before filtering started We may have separated out the frequencies bands in a signal but doubling the number of terms is hardly impressive compression Thus the role of down sampling is to ensure that we still have the same number of terms after filtering with both low pass and high pass filters As down sampling introduces aliasing however we7ve then got to up sample and filter again to eliminate the aliasing and hence reconstruct the original signal For digital signals all this is made precise in the notion of lter bank introduced in lecture 5 which then carries over to produce the decomposition of analogue signals into coarse and fine details As always the big problem is how to design the appropriate filters That7s the miracle achieved by the Daubechies FIR filters 16 Problems I The simplest FIR filter is the Lazy Filter I x a IQ at so called because it does nothing to a signal its filter coef cents are given by l n 0 in 0 n 31 0 In other words IQ is simply the convolution IQ Mac 50gtmc of x With the unit impulse 6 Notice that I fills in7 the missing first example in the series of lters given in 27 because it has only one non zero filter coef cient There really must be a pattern to these filters check problem 10iv alsoH i Show that the Frequency Response function 5 of I is given by 5 l for all 5 Why does this make good sense What is the adjoint Iquot of I Does I succeeding in trying hard to be low pass or highpass ii Determine the associated FIR filter What is its Frequency Response function 15 What is its adjoint f iii Determine L 2 o Iac Io T 2 for a sequence an iv Determine i 2ofx f0 T 2ac for a sequence x v Determine the coarse fine detail decomposition IoT2oi2oI IoT2ol2oI of a sequence x 2 Show that the adjoint 5 of the delay operator S is the advancing operator 5 Z n1m translating the sequence in the opposite direction to S 3 Let x be the sequence Whose Frequency Response function is the period 1 extension of the function X5 l13l5lla O l l By using representation in 23 find the sequence Hint get rid of the outer absolute value by using the fact that X is even 26 X75 X then get rid of the inner absolute value by splitting the new integral into two parts 4 As a further attempt to explain the appearance of the adjoints 71 and 77quot in the coarsefine decomposition of signals show that HOT212OH omr l2o quot for any FIR filter H In particular therefore H0T20120H HOT2OHOT2 oT2gtolti2o gtx omwmomm Which are exactly the same as the synthesis analysis Inappings Slfl 5051 associated in lecture 1 With an orthonormal farnily 1577 in a general inner product space 5 Use problem 4 With H and 7 the Haar filters to establish the results Hor2gtolt12o Hgta Z 150 80 n e T 2 o 1 20 W Z a 71555 n for the respective orthonorrnal farnilies g0 n n stated in 28 6 Show that l 2T 2 at 26 up sarnpling followed by down sarnpling always preserves a signal 7 Let H be the FIR filter having filter coef cients hi 41 11H associated with an FIR filter H Show that Frequency Response function of H is given by Ems Mme a Show that the FIR associated with the Haar lter in which n 0 h71 11 l 0 n 7 0 1 is exactly the lter H having filter coef cients n 0 II 7 n l 0 n 31 0 l in other words notation used for the two Haar filters is consistent with the definition of H being associated with H 8 The companion dig filter in the db2 case for instance is le 737 73 7 1 h7 h7 7 7 2 4 1 4amp7 0 4amp71 its not causal I know but that7s not importantl i Show that the Frequency response function for the db2 filter is H5 6 37 g cos W52cos W5 i Sln7139 ii Then use problem 7 to show that the Frequency Response function for dB is given by 35 e sin 7T52 cos W5 7 isin W5 the db2 filter coef cients are real rernernberl 19 9 Use sorne graphing facility to draW the graph of and for the Daubechies db2 filter 10 Show that the mapping H o T 2 is energy preserving on 2 for a given FIR filter H if and only if i lH l2lH l2 2 i Deduce that if Ho T 2 is energy preserving on 2 then so is H o T 2 ii Deduce that H o T 2 is energy preserving on 2 When H is the Haar filter and the db2 filter iii Does your proof of ii for the Haar and db2 filters suggest how one might construct other lters H for Which condition holds iv Use parts and ii to show that the families g0 n and ZULU are orthonor Inal in 2 results established directly in lecture 1 Then use parts and ii to construct new orthonorrnal families in 2 from the db2 and db2 filters CALCULUS SUMMARY A quick reference on Exponents Logarithms Differentiation Integration Power Series Exponents bxgt0 bxbyifandonlyifxy b by bw b y b b by b a e quot Logarithms Natural Logarithmic Function fx logz x In x The natural number 2 m 271828182846 To get this number on the calculator press 1 INV lnx 1oggx is written lnx e1xi 1011x1 In x 00 lne x 1nxy1nx1ny lnxy ylnx Logarithms to other bases read quotel en exquot 1nxb ifandonlyif ebx lim lnx 00 Hoe e alnb 1 x 1n1nx lny y y 10ga x if and only if ay x loga xy loga x loga y loga xy yloga x loga i loga x 7 loga y y logbx loga x 7 logba A calculator can be used to evaluate an expression such as 10g214 by virtue of the fact that it is equivalent to 1n14In2 RULES OF DIFFERENTIATION where u is a function of x The derivative of a constant is 0 The power rule the derivative of xquot is we The general power rule The constant multiple rule The sum and difference rule in n71r dru nu u 7cucu39 7uivu39iv39 The General Power rule is a special case of the Chain rule The product rule The quotient rule The chain rule The absolute value rule Exponential functions The natural number e The natural log 171n u Logarithms to other bases Trigonometric formulas d s1n cos dx u u u d tanuu39sec2 u dx d z 7 cot 7 csc dx u u u d Ehrcsm u 7 iarctan u i u dx 7 1 u2 u d dxarcsec u7 Lib sinhuu coshu u I17u2 7uvuv39u39v d uj vu39 uv39 T 7 I V V2 fu Mfu39u 1 371nx x j ulnx lnxu oOg x lnax j loga umu d 7 cos 7 Sln dx u u u r r d 7secu u secutanu dx d 7csc u 711 cscu cotu dx 1 7 iarccot u 7 dx 1u2 u coshuu sinhu d iarccos u 7 dx xl7uZ d 7arccsc u 7 dx uNuZ71 Example of the general power rule with trigonometric functions 56in3 x 5sinx3 3sinx2 cosx 35in2 xcosx Tom Penick tomtomzapcom wwwteicontrolscomnotes 6112001 RULES OF INTEGRATION n1 x The basic formula Ixquot dx 7 C 71 1 Constants IdeC Idxxc jk dxkxC jk x dxkjfx dx The sum and difference rule Immigocn dx l x dxilgoc dx 1 Fractional functions I dx lnlxl C x 1 r I dulnlulC jiwc1nlulc u u 1 Ia dx jaxC Ina Exponential functions The natural number e Ie dx e C IA 1 IA X X Iedxie C Ixedxx 1e C u Ixeaxdx iax 1C a2 n 12r 2an12 135 n l WP for even 71 2 a a for odd 7 no VI HXZ Ixe dx 0 Composite function where u is a function of x jfuu39 dx FuC n1 u The general power rule Iuquotu39dx C n1 Integration by parts try letting dv be the most complicated portion of the integrand that fits an integration formula Inch 2 uv J vdu The definite integral where x is the derivative of Fx ffxdx Fb Fa Fx Second degree polynomials for pX Ax 2 Bx C lfpxdx bapa4pabj pb Trigonometric formulas 1 1 J smudx7 cosuC Icosudx 39smuC u u secudu lnlsecu tan ul C Jsecutanudu secuC I J seczudutanuC Icscudu 7ln cscucotu C l csczudu7cotuC J cscucotudu7cscuC Itanudu ilnlcosul C Icotudu lnlsinul C du u du 1 u J7arcsmiC I iarctaniC 11277Z a a u a a J du 1 lulC 77arcseci muziaZ 1 a 1 1 J sinzudu7ueisin2uC 2 4 2 1 1 Ices uduusm2uC 2 4 1 Isin3 udu 732 sin2 ucosu C 10053 udu2 cos2 usinu C Definite Integrals Natural Number 2 rato earo 2 6 dx 0c xe dx 0c 0 0 2 rato 3 n rato n1 xe nix 20 xe dx nxx 0 0 Probability Integrals For the form In I xquote39 zdx 0 z aaz 11 zi 2 Ears2 2 2a 4 3 2 614 4 61 I 2 as for odd n In n 12 2an12 for even n I 135n 1 11 n 2n21an2 Complex Trigonometric Identities cos 9 ew e39je 39 9 79 sm9j17e e j 69 0059 jsin9 Tom Penick tomtomzapcom wwwteicontrolscomnotes 6112001 ME 383SLubrication Wear 8 Bearing Techn MD Bryant January 17 2006 Surfaces If God created Solids the Devil created Surfaces o Impression surfaces at amp simple 0 Reality surfaces extremely complex 0 Surface properties depend on gt topography gt method amp history of surface formation gt surface amp bulk composition gt environment 1 ME 383SLubrication Wear amp Bearing Techn MD Bryant January 17 2006 Surface formation example 0 NaCl FCC structure gt Bulk properties depend on crystal s atoms gt Surface properties can depend on cleavage gt Cleavage plane influences surface properties Short dashed plane exposes White atoms Long dashed plane exposes blue atoms Inclined plane exposes White amp blue atoms ME 383SLubrication Wear amp Bearing Techn MD Bryant January 17 2006 Surface disrupts crystal structure gt higher energy gt Unshared electrons gt Mechanical deformations 0 Bulk large grains single crystals consistent with crystal structure amp lower energy levels 0 Smaller grains surface from intense deformations amp higher energy levels 1100 Mm o Bielby amorphous layer 100A from machining work hardened quenched alloy mixtures 0 Layer of compounds 100A oxides sulfides etc o Adsorbed layer via van der Waals forces hydrocarbons water atmospheric impurities etc 0 Dust particles 1 um ME 383SLubrication Wear amp Bearing Techn MD Bryant January 17 2006 dust particle adsorbed deposited layer oxide sul de etc layer 1 Bielby amorphous layer i sma er rains 1 nearllsurgface Y inclusions amp 09 A vords bulk larger grains o Surfaces depend on history how surface was made 0 Layers may or not be important depending on size amp phenomena gt Can t measure effect of thin films on mechanical deformations gt Same layer can insulate contact amp impede electric conduction ME 383SLubrication Wear amp Bearing Techn MD Bryant January 17 2006 Surface Topography o All surfaces rough no smooth or at 0 Surfaces topography peaks asperities amp valleys furrows Size shape and distribution determined by surface production machined forged plated etched etc o On a typical 1 cm2 surface very many asperities 0 Smooth on large length scale is rough on smaller length scale 0 Characterization of surface texture gt Long wavelength 10 um 10 mm undulations o Called surface waviness 0 Man made scratches machining marks tool amp die shapes etc o Fourier series representations gt Shorter wavelengths lt 10mm 0 Nature made bumps 2 random structure 0 Statistically characterized ME 383SLubrication Wear it Bearing Techn MD Bryant January 17 2006 SURFACE TOPOGRAPHY 0 All surfaces are rough 0 Surface features hills asperities valleys furrows 0 Surface pro le trace surface height Z s 100 mm X s 88 cm Y s 254 cm 0 Surface height descriptions Surface waviness sinusoidal structure Fourier series Surface roughness random Gaussian distribution model Fractal models ME ZBZSLubncahm Wzaramp Eesmg Tzchn M D Bryant January 17 zone 7 SURFACE TOPOGRAPHY DESCRIPTIONS 201m 3 Smusoxdal models w nu Surfacehexghtszxy WW KW w Hugh 4 z e 300nm sm2rgtlt120 mum 20 Sl MOrt x 10 smuomx Surface wavmess Zwave long Wavelengths macroscoplc feafures manrmade often zwm e 1005m2rgtlt120 cus4ngtlt Surface roughness Zmugh 2mm short Wavelength rmcrosco 1c feafures determmxshc or random very short random m wmmmwwwmwmww Zmugh20 5m AWMO sm100ngtlt SURFACE WAVINESS EXAMPLE Fwnersenes ampumdes a E 3 s c Q a x g 2 surfacehexghtZXYs 100 m E XsLxBBcrmYsLy254Cm m asYQ a SWWz n harmomc number m waxmess pm le Founer senes Wavmess pro le ZX Y 2 Arm h m m p mn Sm mLZX m Sm th armomc amphtudes hases of harmomccomponents SURFACE ROUGHNESS EXAMPLE EUEEUDE IEMEW SEM photo electroplated gold on copper waviness and roughness apparent 10 Measure Surface Topography Bumps Via gt Profilometer similar to phonograph tone arm Stylus rides surface 2 trace signal gt Optical interference techniques that utilize path differences gt Electron microscope photographs gt Atomic force microscope microprofilometer for nano measurements 11 SURFACE PROFILE MEASUREMENTS 39I surface X Profilometer 0 stylus travels surface 0 motions Zx trace profile S V39US 0 stylus 2 filter surface big small bumps stylus cannot sense wwwtaylorhobsoncom ME 383SLubricati0n Wear amp Bearing Techn MD Bryant January 17 2006 Optical methods bumps create optical path difference light rays polarized surface gtx 0 scan surface gt three dimensional image 0 profile extracted 12 ME 383SLubrication Wear amp Bearing Techn MD Bryant Optical Interferometric Microscope January 17 2006 13 ME 383SLubrication Wear it Bearing Techn MD Bryant January 17 2006 14 Atomic Force Microscope Microprofilometer Cantilever beam rides surface Stylus nanometer curvature Laser interferometer detects beam de ections Subnanometer range 0000 0 AFM image of graphite atoms AFM image of contact bump ME 383SLubrication Wear amp Bearing Techn MD Bryant SURFACE TOPOGRAPHY PARAMETERS January 17 2006 15 Instrument reference plane Zo ZX I reference plane I 44Llt x 1 S 1 L d o Locating zeroline Z0 n Zi L xz x i1 Zl Zl Z0 20 DC component 2 AC component ME 383SLubrication Wear amp Bearing Techn MD Bryant January 17 2006 Historical Quantities 0 Centerline Average CLA 1 1 L Ra Z 2 dx quotgm LAM measures roughness excursion from zeroline 0 Root Mean Square RMS also measures EXCUI39SlOIl 0 Not unique different profiles same Ra Rq 0 Other measures Maximum peak to valley min 2 Rt 2 max 2 heights heights 1 11 Average Rt over segments R2 E 2 Rd i1 16 ME 383SLubrication Wear amp Bearing Techn MD Bryant January 17 2006 STATISTICAL QUANTITIES 0 Surface height distributions ZX Zi gtiLlllt 0 Surface height 2 treated as random variable FZ frequency of occurrence X 0 Some surfaces almost Gaussian l e E 23 2 1 FZ M 0 Expected values of functions with distributions E gz f gz Fz dz 0 Moments gz 2r related to historical it other quantities E Zr fz Fzdz 17 ME 383SLubrication Wear it Bearing Techn MD Bryant January 17 2006 18 o Ra 1st moment Ra CLA fzFzdz 2szzdz oo 0 o Rq 2r101 moment Rq RMS E 22 a fZ2FZdz o Skewedness 5 3r01 moment r 3 ME 383SLubrication Wear amp Bearing Techn MD Bryant January 17 2006 0 Autocorrelation function L2 Ra 133 fzxzx ldx L2 1 N 1 120 gmzomx 1 0 Power spectral density function PSD 2 00 Psom fRlcoswzdz O Fourier transform of autocorrelation function 0 Frequency domain information on profile 19 ME 383SLubrication Wear amp Bearing Techn MD Bryant FRACTAL MODELS January 17 2006 0 Surface roughness characterization 0 Describes natural quotrandomquot processes 0 Poor model manmade surfaces 0 Roughness characterized Via spatial frequency a 0 Surface profile z zx o Fourier transform 20 fzxejmdx 0 Power spectral density PSD Z0J2 0 Plot log PSD versus log a 0 Similar to Bode plot PSD of Atomic Force Microscope images of polycrystalline Si with 3nm RMS roughness Bora Plesha Flater Street amp Carpick Multiscale roughness of MEMS surfaces 2004 ASME Local curve equation C 39 PSD a lt gt W 0 Fractal dimension D characterizes surface roughness 0 Valid over several orders of magnitude 0 Describes bump on bump quotrandomquot processes 20 M427K Handout PDEYs Two Point Boundary Value Problems Salman Butt April 25 2006 HIGH LEVEL VIEW This chapter s progression can be a bit confusing but here is our plan We want to discuss solutions to partial differential equations PDE s Our method will be to change a given PDE into a set of ODE s subject to initial value and boundary value conditions via a technique called sepa ration of variables We have handled initial value problems but we have yet to discuss boundary value problems 7 this is the topic of today s class Now our proposed solution to the PDE will be a sum often in nite of solutions to the ODE s These sums will often involve cos and sin terms so we will also discuss these series known as Fourier series 7 this will be discussed tomorrow in lecture and probably in discussion section on Thursday Once we have all this background covered we will be ready to actually solve some PDE s Two POINT BOUNDARY VALUE PROBLEMS Recall that our previous second order differential equations often came with two initial condi tions 24 WW 6175 905 We 2407 2050 246 Often especially via experimentation instead of initial value conditions how would you determine y t0 anyway you often have the value ofy or y at two di erent points That is instead ofyt0 and 3050 you have ya and 343 for some points 043 Such conditions are called boundary conditions and a differential equation with two such boundary conditions is called a twopoint boundary value problem 24 py qy 9W Ma yo MB yr We will look for a solution to the above differential equation in the interval 04 lt z lt 3 Now homo geneous boundary value problems are slightly different from homogeneous initial value problems Speci cally homogeneous BVP s are of the form Otherwise we say the EV is nonhomogeneous Linear BVP s behave like linear systems slight changes in the boundary conditions can change the solutions drastically this is not really the case with lVP s This is not the only similarity between these two types of problems as we shall see Recall some facts about the linear system A E where A is an n x 71 matrix I is a given 71 x 1 vector and f is the unknown 71 x 1 vector we want to determine If A is nonsingular the system has a unique solution for any I But if A is singular then the system has either no solutions or in nitely many solutions depending on the given Next consider the homogeneous system got by taking 1 O a We know one obvious solution to this homogeneous system z 0 the trivial solution If A is nonsingular then this is the only solution but if A is singular then there are in nitely many non trivial solutions We can state these results as follows 1 Consider the following examples 2 2y 0 y017y7r 0 y y 07240 17y7r a BVP s behave like linear systems and we know the solutions to a nonhomogeneous linear system depend on the homogeneous system so consider the homogeneous BVP y py 6190 07 9a 07 MB 0 Analogous to linear systems this equation has the trivial solution y 0 But does it have other solutions In fact the same relationship holds between nonhomogeneous and homogeneous BVP s and nonhomogeneous and homogeneous linear systems That is 1 Let s look at the corresponding homogeneous equations to our examples above So far we have seen a strong relationship between linear systems and BVP s Does the notion of eigenvalues and eigenvectors also carry over to BVP s I wouldn t be talking about this if it wasn t the case right Recall the equation This equation always has the solution f 0 despite what A may be But for certain values of A 7 the eigenvalues 7 there are also nonzero solutions 7 the corresponding eigenvectors Let s look at the analogous homogeneous BVP This is just the general case of our above examples where A 2 and A 1 Extending the terminology from linear systems we say A is an eigenvalue of our BVP if there exists nontrivial solutions to the BVP and the solution itself is called an eigenfunction Under this terminology A 2 is and A 1 is Let s try to nd other eigenvalues and eigenfunctions of this BVP We will examine the cases A lt O A gt O and A 0 separately since the solution to the EV is different in every one of these cases Case 1 A gt 0 We will use a simple trick so we avoid excessive use of radicals and set A 2 This is just a homogeneous second order diffeq so let s look at the characteristic polynomial The roots of this polynomial are simply r and we have the general solution WMAWLOG that u gt 0 Let s look at the boundary conditions So these conditions tells us that 01 and Remember that we want nontrivial solutions to this BVP so we want to make sure 62 7 0 1e we want the sin term to be zero When is sin mr 0 Precisely when u Recalling that A 2 we nd our eigenvalues are The eigenfunctions are merely multiples of sin mm for n 1 23 The eigenfunctions are de termined only up to the multiplicative constant 02 just as in the case for eigenvectors The book often sets this constant to be 1 So in our case the eigenfunctions are Case 2 A lt 0 As before we use a simple trick A 7122 and write our BVP Considering the characteristic equation we nd the roots are r so the solution is of the form Note that we could have used the standard solution y 015 025 but we chose this solution for convenience when we apply the boundary conditions Considering these conditions we nd 01 0 and Since 1 7 0 and recalling the de nition of sinh we see that sinh mr 7 0 so we know 62 is forced to be 0 Thus the only solution to this BVP is the trivial solution y 0 Hence we know that there are no negative eigenvalues of this BVP Case 3 A 0 Our BVP in this case just becomes What function integrated twice gives you 0 Well just a polynomial of degree one Examining the boundary conditions we see that we forced to conclude 01 02 0 Hence A 0 is not an eigenvalue Putting all this together we see that the full list of real eigenvalues is An n2 for n 1 2 3 with corresponding eigenfunctions sin nz up to constant multiples There are no com plex eigenvalues though we have not addressed this point this is Problem 23 on p 576 of the text These problems have real application beyond being an analogy between linear systems and BVP s This BVP with a slight change to the boundary conditions is the heat equation for a solid rod a problem we will probably be considering next week CS 395T Computational Complexity of Machine Learning Lecture 14 March 8 2005 Lecturer Adam Klivans Scribe Alex Sherstov The Harmonic Sieve This lecture presents a polynomialtime algorithm based on boosting for learning DNF formulas to arbitrary precision The algorithm is due to Jackson 141 Preliminaries Let f T1 V T2 V V T5 be a Boolean function in DNF on n variables One of T1 T2 i i T5 must be true on at least 13 of the satisfying assignments to f denote some such term by T The analysis below treats f and T as Boolean functions from 71 1 to 711 we denote by f0gt1 and T0gt1 their counterparts from 71 1 to 01 Let D be an arbitrary distribution over 711 We start by relating and g f0gt1 gm 1 grlf 71 1grlf 1 7 7 I 7 01 I 01 W1 W lgt1glf l 2f gt1 71 Thus Em 1 31 D7 3 f l 2 l 141 Second we represent T0gt1 as its Fourier expansioni Let V E 11zglllzn be the subset of variables featured in T0gt1l Without loss of generality assume T does not feature negatizms of variables 17 x x 71w 01 7 7 XA T 7 H 2 7 Z glVl er AgV g 71 ATXAi 142 The presence of any negated variables in T will affect only the signs of the terms in the above summationl Since the analysis below does not depend on these signs no loss of generality is incurred 141 Lecture 14 March 8 2005 142 142 Weakly Learning DNF S This section will show that any DNF f with 8 terms has an 913 correlation with some parity function X Combined with the KM algorithm for identifying large Fourier coef cients with queries this result will yield a weak learner for polynomialsize DNF si Using 141 we obtain gh E W 2 143 On the other hand 142 yields E f Tm h f a lt1gt gtltAH a h f lt71gt A XAH h Uh f lt71gt XA H h hvmh M Combing 143 and 144 yields the following inequality g f TN 3 Q HIE 39 l Consider two cases 0 Case 1 EDU 2 7123 l The parity function XA above has a large correlation with f hf hLW1gt2sH D X i 23 2303 7231 0 Case 2 EDU lt 7123 1 The parity function X0 1 has a large correlation with f m fll 7 mm gt 1 D M 7 D 23 1 In either case above there exists some parity function XA with correlation at least 123 1 with f over distribution Di In other words PrDf XA 2 12 123 1 Thus identifying the parity function XA amounts to learning f over distribution D with advantage 123 l 918 Lecture 14 March 8 2005 143 143 Boosting Boosting is a technique for learning a concept class to arbitrary precision given only a weak learneri More speci cally a boosting algorithm receives 1 a weak learner with advantage 7 over an arbitrary distribution 2 an accuracy requirement 6 3 a success probability parameter 6 4 access to the target function f and with probability 1 7 6 produces a hypothesis h with Pry Z 1 7 6 Boosting works in stages At stage 1 the algorithm uses the weak learner to produce hypothesis hl with accuracy PrgENUh1z 2 1271 At stage i the algorithm constructs a distribution Di that puts more weight on examples labeled incorrectly by h1 h2 i i i Ill1 and uses the weak learner to obtain a hypothesis hi with accuracy PrgENDI hi 2 12 71 At the end the algorithm outputs some combining function of the hypotheses h1 h2 i i i h eg a majority classi er There are boosting algorithms that terminate within 1 09 log stages and weight no example more 1 than mi 144 Putting It All Together A complication in using boosting to learn DNF formulas to arbitrary precision is the requirement that the weak learner operate over an arbitrary distribution Di In particular the KM algorithm identi es large Fourier coef cients with respect to the uniform distribution iiei lEgENUU XAH 2 9 Observe that EwNleIXAIl ZDIfIXAI 2i ETDWVWMAW ExNU12 DIfIXAIlA Thus identifying XA with EDD XA 2 19 is tantamount to identifying a Fourier coef cient of 91 with absolute value 19 or more The distributions Di constructed in a boosting algorithm are known so any query to y can be answered via a query to An analysis of KM for nonBoolean functions such as 9 yields a running time polynomial in 16 161t9 and Loogi In our case 19 281 and Loog S 2 12n6 1 16 the latter bound follows because there are boosting algorithms that enforce S 12n6 for all ii As a result DNF formulas can be learned to arbitrary precision via a boosting algorithm that uses KM as a weak learneri The time 39 t of this 39 t 39 is r 1 39 1 in the DNF size 8 as well as the usual parameters 16 and 161 Embedded Microcomputer Systems Lecture 71 15 Digital Filters Chapter 15 objectives are to Introduce basic principles involved in digital ltering De ne the Z Transform and use it to analyze lters Develop digital lter implementations Introduce DFT and some applications 151 Basic Principles xct is a continuous analog signal fS is the sample rate xn xcnT with 00 lt n lt 00 1 There are two types of approximations associated with the sampling process nite precision of the ADC nite sampling frequency frequency f s Figure 1230 To prevent aliasing there should be no measurable signal above 051 A causal digital lter calculates yn from yn l yn Z and xn xn 1 xn 2 not future data e g yn1 xn1 etc A linear lter is constructed from a linear equation A nonlinear lter is constructed from a nonlinear equation One nonlinear lter is the median A nite impulse response lter FIR relates yn only in terms of xn xn 1 xn 2 x111 Kin 3 yn 2 4 An infinite impulse response lter IIR relates yn in terms of both xn xn 1 and yn 1 yn Z yn l 130Xnl 130X12118 2 970yn 2 The de nition of the ZTransform 00 n XZ ZX00 E Z X001 6 oo by Jonathan W Valvano Embedded Microcomputer Systems Lecture 72 Consider the Laplace Transform continuous Xt discrete Xn time domain time domain Inverse Z frequency frequency domain XS domain Xz Figure 151 A transform is used to study a signal in the frequenc domain Analo g t Kit System y Inverse Laplace Transform Xs Hs YsHS Xs Xz Hz YzHzXz Figure 152 A transform can also be used to study a system in the frequency domain The gain lHs at s j 21If for all frequencies f The phase angleHs at s j 21cf The gain and phase of a digital system is specified in its transform Hz YzXz from DC to fs One can use the definition of the ZTransform to prove that Zxn m quot1 Zxn quot1 Xz 7 For example if Xz is the ZTransform of Xn then z2Xz is the ZTransform of Xn Z Y z HzEXz 8 To find the response of the lter let z be a compleX number on the unit circle z a e Jznffs for 0 3 K fs 9 or z c0s21ffs j Sill21ffs 10 Let Hf a bj where a and b are real numbers by Jonathan W Valvano Embedded Microcomputer Systems Lecture 73 The gain of the lter is the complex magnitude of Hz as f varies from 0 to fs I GainEHf la2b2 12 I The phase response of the lter is the angle of Hz as f varies from 0 to fs b Phase 5 angleHf tan391 13 i 152 Simple Digital Filter Examples Although this lter appears to be simple we can use it to implement a lowQ 60 Hz notch x111 Kin 3 yn 2 4 Again we take the ZTransform of both sides of Equation 4 X 3 xg Yz z 3 z 24 Next we rewrite the equation in the form of HzYzXz Y z 1 z393 Hz E X46 T 25 We then can use Equations 9 through 13 to determine the gain and phase response of this lter 1 ejfmffs 1 c0s6nffs j sin6nffs H 2 2 Gain a Hf 05 x 1c0s6nffs2 sin6nffs2 fs360Hz channel specifies ADC channel unsigned short x4y x0 is xn current sample x1 is xn 1 sample 1360 sec ago x2 is xn 2 sample 2360 sec ago x3 is xn 3 sample 3360 sec ago define CSF 0x20 period 1500000360 interrupt 13 void TOCShandlervoid TELGl 0C5 ack CSF 39139C5 39139C5416397 fs360Hz x3 x2 shift MACQ data x2 x1 x1 XEOJ x0 ADClnchannel new data Y x0x3gtgt1 PutFifoy void ritualvoid asm sei 39I39IOS CSF TSCRl 0x80 TSCR2 0x04 39I39IE CSF make atomic enable CSF Enable TCNT 667ns TOI disarm Arm output compare 5 by Jonathan W Valvano Embedded Microcomputer Systems Lecture 74 x0x1x2x30 TFLG1OC5 Initially clear C5 39139C5 39I39CN39I39416397 asm cli Program 153 Real time data acquisition with a simple digitalfilter Equation 4 3 01 O n1Xn2 yn xnxnl2 yn xnxnl xn 2 xn3xn4xn56 Gain 02 03 05 frequency ffs Figure 153 Gain versus frequency response for four simple digital lters 154 High Q 60 Hz Digital Notch Filter There are two objectives for this example show an example of a digital notch lter demonstrate the use of xedpoint math 60 Hz noise is a signi cant problem in most data acquisition systems The 60 Hz noise reduction can be accomplished 1 Reducing the noise source eg shut off large motors 2 Shielding the transducer cables and instrument 3 Implement a 60 Hz analog notch lter 4 Implement a 60 Hz digital notch lter analog condition digital condition conseqllence zero near sj 2nf line zero near zel 5 low gain near the zero pole near sj Zitfline pole near zeimfs high gain near the pole zeros in conjugate pairs zeros in conjugate pairs the output yt is real poles in conjugate pairs poles in conjugate pairs the output yt is real poles in left half plane poles inside unit circle stable system poles in right half plane poles outside unit circle unstable system pole near a zero pole near a zero high Q response Table 151 Analogies between the analog and digital lters by Jonathan W Valvano Embedded Microcomputer Systems Lecture 75 It is the 60 Hz digital notch lter that will be implemented in this example The signal is sampled at fs480 Hz We wish to place the zeros gain0 at 60 Hz thus 60 9i27t fs i 714 41 7I2 Figure 159 Pole zero plot of a 60 Hz digital notch filter The zeros are located on the unit circle at 60 Hz z1 cos9 j sin9 z2 cos9 j sin9 42 To implement a at pass band away from 60 Hz the poles are placed next to the zeros just inside the unit circle Let 1 de ne the closeness ofthe poles where 0 lt G lt1 pl 0 pfazz 43 ford 075 The transfer function is k 2 1 z z z z H 1 1 2 45 Z Ela pi z pz p2 which can be put in standard form ie with terms 1 z39l z392 1 2 cos9z1 2 2 Hz 1 20c cos9z1 oc222 46 or 1 V 2z1 z 2 l ixl2z1iz2 4 l 6 The digital lter can be derived by taking the inverse Ztransform of the Hz equation yn XIl 2cos9Xn1 Xn2 20ccos9ynl x2yn2 Hz 47 yn Xn l4l421Xn1Xn2l06066ynl 05625yn 2 we rewrite using xedpoint math by Jonathan W Valvano Embedded Microcomputer Systems Lecture 76 yn 128Xn181Xn1128Xn2136yn1 72yn2128 Another consideration for this type of lter is the fact that the gain in the pass bands is greater than one The rst method is to use the Hz transfer equation and set 21 1 J 1 H1 2 1 4J 16 Z 11673 Z 128110 We can adjust the digital lter so that the DC gain is exactly 1 by prescaling the input terms by 1 10 1 28 yn 110Xn 156Xn1110Xn2136yn1 72yn2128 copypa5te lterimo d est10c define fs 480 unsigned char x3 unsigned char y3 unsigned char Filterunsigned char data y2 y1 y1 yEOJ shift MACQ x2 x1 x1 XEOJ x0 data new data Y0 110x0x2 156x1136y172y264128 return y 0 f0Hz Gain100 f 10 Hz Gain 098 f 20 Hz Gain 095 f 30 Hz Gain 089 f 40 Hz Gain 074 f 50 Hz Gain 047 f 51 Hz Gain 045 f 52 Hz Gain 039 f 53 Hz Gain 035 f 54 Hz Gain 030 f 55 Hz Gain 026 f 56 Hz Gain 021 f57 Hz Gain 017 f58 Hz Gain 011 f 59 Hz Gain 007 f 60 Hz Gain 003 f 61 Hz Gain 009 f62 Hz Gain 013 f63 Hz Gain 019 f 64 Hz Gain 021 f 65 Hz Gain 029 f 66 Hz Gain 032 f 67 Hz Gain 036 f 68 Hz Gain 042 f 69 Hz Gain 046 f 70 Hz Gain 050 by Jonathan W Valvano Embedded Microcomputer Systems Lecture 77 f 80 Hz Gain 068 f 90 Hz Gain 090 f 100 Hz Gain 098 Digital Filter 100 075 E 8 050 025 000 I l I l l 0 30 60 90 120 Frequency HZ The Q of a digital notch lter is de ned to be fc Q sA f 59 where fc is the center or notch frequency and Af frequency range where is gain is below 0707 of the DC gain This is a low Q 6040 15 In general if fS is 2 k fc Hz where k is any integer k22 then the following is a fc notch filter x111 xgn k yn 2 34 Similarly if fS is kfc Hz where k is any integer k22 then the following rejects fc and its harmonics 2fc 3fc 1 yn Z xni 35 09 x n x nk 08 n M yn1 k I 07 398 3 06 H g 05 L v mv 04 3 20 03 D 02 01 0 I I I I I I I I I r 0 5 10 15 20 25 30 35 40 45 50 Frequency Hz Figure 151 7 Gain versus frequency plot of four low pass lters by Jonathan W Valvano Embedded Microcomputer Systems Lecture 78 The Discrete Fourier Transform The DFT of a block of N time samples anaoalaz aN1 is a set ofN frequency bins AmA0A1A2 AN1 where N1 mn Am 2 anWN m012N1 n0 j27t N WN E e While the DFT deals only with samples and bins with no concept of seconds and Hz when looking at ADC samples spaced at intervals T in sec Frequency bin m represents components at mfsN in Hz 0 The DFT resolution in Hzbin is the reciprocal of the total time spent gathering time samples ie lNT realtype xr realtype yi int n int i realtype magnitude nr rr ii nr realtype n number of points if 1 magnitude sqrtxr0xr0yi0yi0nr by Jonathan W Valvano Embedded Microcomputer Systems Lecture 79 else rr fabsxri fabsxrn i ii fabsyii fabsyin i magnitude sqrtrrrriiiinr dBFS 200log10magnitude25 full scale is 25 volts Apphca ons Measure SN ratio Identify noise lVrms lOOkHz Sinewave DFT o N 1000 4m IAmI d BFS 2oo 3oo WI39J39 400 o 100 200 300 400 500 Frequency kHz by Jonathan W Valvano Embedded Microcomputer Systems Lecture 710 Windowing Spectral leakage can be Virtually eliminated by windowing time samples prior to the DFT Windows taper smoothly down to zero at the beginning and the end of the observation window Time samples are multiplied by window coef cients on a samplebysample basis Windowing sinewaves places the window spectrum at the sinewave frequency Convolution in frequency by Jonathan W Valvano Lecture 3 Two FIXED POINT THEOREMS 1 of 4 Course M393C equilibrium theory Term Spring 2007 Instructor Gordan Zitkovic Lecture 3 Two FIXED POINT THEOREMS This lecture is based on selected parts of Bor03i 31 Sperner7s Lemma Spernerls lemma is due to Sperner see Spe29i The proof given here is due to HiWi Kuhn see Kuh68i Let A I E R 21 I 1 stand for the unit simplex in Rni The points in A the Euclidean coordinates on A are also called the barycentric coordinatesi For m E N let Sm denote the set of all z E A such that mzi E N U 0 for all i liun where z 11 i i i zn The points in Sm divide the simplex A into mn 1 subsimplices the set of which will be denoted by amt Also each n 7 ldimensional face of A admits a similar decomposition into mn Q n 7 ldimensional simplicesi Let us denote the set of all these by 80 i Clearly each 6 E dom is an n 7 ldimensional face of a unique 6 E amt The set of all n 7 ldimensional faces of all 6 6 am some of which will not be on the bounday of A will be denoted by 80ml Thus 80 is a subset of 80m consisting of those n 7 ldimensional faces that lie on the boundary of At A labeling is a function A Sm 7gt 12Hrni A labeling is called proper if Mr E Pr for all z E Sm where Pz 1 i i i n xi y 0 A subsimplex 6 6 am is said to be completely labeled if M6 12Hin where M6 z z E Theorem 31 Spernerls Lemma Suppose that A is a proper labeling on Sm Then there exists an odd number of completely labeled subsimplex 6 6 am Proof lnduction on the dimension n E N of the simplex Ar When n l the statement is trivially true If n 2 when A is a line segment the claim is clear Suppose that is holds for all h lt n for some n gt 1 and let us prove that it also holds for n Pick a proper labeling A and de ne the following sets C 6 6 am 6 is completely labeled A6 am M6 l2iun7l B 6 E dom 6 which bear all labels in the set 12Hin 7 1 E 6 6 80m 6 which bear all labels in the set 12Hin 7 1 The goal is of course to show that lCl is odd We start by constructing a graph F in the following manner draw a picture for the case n 3 the set of nodes vertices of F is A U B U C and the set of edges is El Clearly there are only two possibilities for each 6 E E a is either a common face of two subsimplices in which case it connects two nodes in A U C or b it is a boundary face and then it connects its carrying subsimplex in A U C with 6 6 Bi A degree of a vertex 6 E A U B U C is de ned as the number of edges it is an endpoint oft Recall that the number of vertices with odd degrees is necessarily even why The degree of the vertices in A is always 2 and the degree of those in C is always 1 For those in B the degree is also always 1 as they are connected to unique subsimplices thay are faces of Therefore the parity of the number of vertices in C matches the parity of the number of vertices in El However the number of vertices in B is odd by the induction hypothesis and therefore so is the number of vertices in C Corollary 32 There exists at least one completely labeled subsimplex for any proper labeling A Last Updated February 5 2007 Lecture 3 Two FIXED POINT THEOREMS 2 of 4 32 Brouwer7s xedpoint theorem Brouwerls xedpoint theorem is of course due to Brouwer see BrolZDi As before let A denote the unit simplex in Rni Theorem 33 Any continuous function f z A A A has a xed point Proof For m E N let the subdivision Sm be de ned as above For each x E Sm let f1 x f2x be the barycentric coordinates of and let x1i xn be the coordinates of x Since i1 l x 7 Z1x1 l for each x E Sm there exists some index Ax such that f x S xMxy Furthermore Ax can and will always be chosen among those indices i such that xi 0 why The mapping A Sm A 12Hin is a labeling in the sense of the previous section Therefore by Corollary 32 Spernerls Lemma for each m E N there exists a fully labeled subsimplex 6m of A Let the full set of vertices of 6k be denoted by xkgt1 xkgt where we choose the numbers so that the label Axkgtj of x1 is j We know that y S x2 where y E A i E 12i ni Thanks to compactness of A a convergent subsequence Ikl 1ng with limit x E A can be extracted from Ik lhcevt Continuity of f and the fact that the diameter of 6k shrinks to 0 imply that x160 A x and y wm A y fx for all j E 12i n as l A 00 By the de ning property of the labeling A the following holds for all ij 12Hin so m M 7 oo xZ liymxi Sllyrlnyi iyii Both x and y are barycentric coordinates of points in A so ELI ELI 1 It follows that x y fx so x is a xed point of B Let AB be two subsets of Rni A map f z A A B is called a homeomorphism if it is continuous invertible and its inverse f 1 z B A A is continuous as well If there is a homeomorphism from A to B then the sets A and B are said to be homeomorphic Proposition 34 Let A be a subset of R homeomorphic to the unit simplex A Then each continuous function g z A A A has a xed point Proof Let f be a homeomorphism from A to A De ne the mapping h z A A A by hx Clearly h is a continuous function mapping A into itself so it admits a xed point x Then with y f 1 x has the property that 99 gltr1ltzgtgt f 1hz Hz y Example 35 Any convex closed and bounded subset of R is homeomorphic to A see Problem 32 33 A theorem of Knaster Kuratowski and Mazurkiewicz First proved in KKMZQ this theorem is perhaps even more useful than Brower7si Truth be told it is not exactly a xedpoint theorem but it de nitely feels like one Theorem 36 Knaster Kuratowski and Mazurkiewicz Let F1 F2 Fn be closed subsets of the unit simplex A E R Let x1 x be the vertices of A and suppose that for any I Q 12 n we have convxi i61 UFi i6 where coan denotes the convex hull of B ie the smallest convex set containing B Then Fta u i1 Last Updated February 5 2007 Lecture 3 Two FIXED POINT THEOREMS 3 of 4 Proof Remember that Pz 6 12 n zl 7 0 For I E A the set Pz is the set of vertices of the smallestdimensional face of A that 1 lies in In fact I E conv z i E Therefore for each I E A there exists Az such that Az E Pz and z 6 FM Pic m E N an et Sm be a subdivision of A as in the section on Sperner7s Lemma The mapping 1 gt gt Az de ned above can be used as a proper labeling As in the proof of Brouwerls theorem we can nd a sequence of shrinking subsimplices 6kkeN the vertices 1amp1 1km have labels 1 n and converge all towards some z E A We know that Ik i E Fi for all h and by closedness of Fi we have z E Fi for al i6 12n Let A and B be sets and let 23 be the set of all subsets of B A mapping F A A 23 is called a correspondence from A to B and this fact is usually denoted by F A a B or F A B De nition 37 Let A be a subset of R A correspondence F A a A is called a KKMmap if Fz is closed for all z E A and j conv 1 zj Q U Fzi i1 for any nite set 1112 zj Q A The following theorem is a re nement of the theorem of Knaster Kuratowski and Mazurkiewicz and is due to K Fan see Fan61 Theorem 38 Let F A Q R A R be a KKMmap and suppose that Fz is compact for some I E R Then Fa y 0 16Rquot Proof The family FzE6R has the nite intersection property ie the intersection of any of its nite subfamilies is nonempty That is a consequence of Theorem 36 how exactly Take 10 E R such that Fzo is compact and de ne the family Cz eA by Cz Fz Fzo Clearly Cz eA is a family of closed subsets of a compact set Fzo satisfying the nite intersection property Therefore the intersection of the whole family is nonempty and eAGQ gceAFz 34 Problems Problem 31 Let A 2 B be subsets of R B is said to be a retract of A if there exists a continuous mapping 7 z A A B such that Tz z for z E B 1 Let B be a retract of A Show that each continuous mapping f z B A B has a xed point 2 Let 5391 I E R2 z z S 1 be the unit ball in R2 and let 851 I E R2 z z 1 be its boundary Show that 851 is not a retract of 51 3 harder and optional Prove the above statement for a general dimension n 2 2 Problem 32 Show that any convex closed and bounded subset of R is homeomorphic to A Problem 33 Use Bower7s xedpoint theorem to deduce the inwardpointing vector eld theorem from Lecture 2 Problem 34 Show by means of a counterexample that the assumption that Fz is compact for at least one I E R is necessary for the conclusion of Theorem 38 to hold REFERENCES BorOS Kim C Border Fized point theorems with applications to economics and game theoi y Cambridge University Press 003 BrolZ L E J Brouwer Uber Abbildung UO IL Mannigfaltigkeiten Math Ann 71 1912 no 4 598 Fan61 Ky Fan A generalization of Tychono s zed point theoiem Math Ann 142 19601961 3057310 Last Updated February 5 2007 The University of Texas at Austin Search Trees Btree Department of Computer Sciences Professor Vijaya Ramachandran Lecture 21 CS357 ALGORITHMS Spring 2007 1 Search Trees Recall that a binary search tree T is a rooted ordered binary tree with each node holding a key from a totally ordered set in a manner that satis es the following binary search tree property for each node x in T o kegz 2 keyy for every node y in the subtree rooted at the left child of m o kegz keyy for every node y in the subtree rooted at the right child of x We will use pz to denote parent of m leftz to denote the left child of z and rightz to denote the right child of x If any of these nodes are missing that will be denoted by NIL For convenience we will assume that all keys stored in the key are distinct Inorder Walk We can print out the keys in binary search tree T in sorted order in linear time by performing an inorder walk on T Let h be the height of binary search tree T Each of the following operations can be performed on T in 0h time SEARCHz k determines if there is an element in the subtree rooted at z with key value k MAXIMUMz nds the element with maximum key value in the subtree rooted at z MINIMUMz nds the element with minimum key value in the subtree rooted at m SUCCESSORz is given a pointer to an element x in T and returns a pointer to the smallest element in T with value greater than key value of m Similarly we have an operation PREDECESSORT z lNSERTz k inserts a new node with key value k in the subtree rooted at m This operation is performed by searching for key value k and then adding a new leaf at the position at which the search terminates DELETET z is given a pointer to z and removes z from T and suitably adjusts its parent and child pointers if x has two children then it moves the successor of z into the location vacated by z 2 Balanced Search Trees In order to support all dictionary operations ef ciently it is necessary to keep the height of a search tree small There are several schemes based on binary search trees known for this including AVL trees red black trees described in your textbook and splay trees that have good amortized bounds Another scheme which is the one we will study next moves away from a binary search tree to a search tree where internal nodes have larger degree 3 BTree A B tree is a generalization of a binary search tree Here each node stores a large number of keys and each node that is not a leaf has a large number of children 7 many more than two The B tree was developed to perform ef ciently in the external memory setting in which the cost of the computation is dominated by the cost of transferring blocks from disk to main memory rather than the total number of operations performed Typically the number of keys stored at a node in a B tree is close to the block or page size A B tree has a parameter 25 associated with it A B tree T with parameter t is a rooted tree structured as follows 1 Every node x has a eld which satis es 2571 g g 2257 1 denoting the number of keys stored at m If x is the root then satis es 1 g 2t 7 1 if the tree is nonempty The keys at z are ordered as keg1M keg2 keg M 2 Every internal node additionally has the following attributes o 1 pointers to children 0z 1 g i g 1 o For each i if k denotes any key stored at a node in the subtree rooted at c then k1 S keylla l S S keyiellg l S kz S keyilml S S keynmlv l S knz1 3 All leaves have the same depth h which is equal to the height of T lft 2 we obtain the 2 3 4 tree In practice if is typically in the thousands corresponding to the block size used for transfers from disk to main memory Theorem 31 The height1 of a B tree on 71 keys is at most logtn Proof Since the degree of the root has different constraints from other internal nodes7 let us rst consider the subtrees rooted at the children of the root Let To be the subtree rooted at a child 0 of the root The subtree Tc has height h 7 17 and each internal node has at least if children Hence if no is the number of nodes in To then hil h t 71 MZE 47 Each node in To has at least if 7 1 keys7 hence if kc is the number of keys stored at nodes in To we have 717 71 2571 again The root has at least one key and at least two children7 hence the total number of keys 71 must satisfy n212k0212th712th71 Hence th n 12 ie h g 09 71 4 Dictionary operations The root of the B tree is always stored in main memory We implement SEARCHT k by starting at the root and then proceeding down to the appropriate child by comparing k to the keys stored at the current node The number of pages ie blocks accessed is at most one per level and hence is no more than h and the time taken to perform the search is Otlogt n if we use linear search at each node The INSERT operation uses the following operation We implement INSERTT k by performing SEARCHT k until we reach a position between two keys at a leafl that shows that k is not in T If nl lt 2t 7 1 ie ifl is not full then we insert k in that position and increase 71H by 1 and we are done If 71H is 2t 7 1 when SEARCHT k terminates at l we would violate the B tree property if we inserted k at Z In this case we apply the operation SPLIT that moves the median key km at l to the parent ofl and splits 1 into two nodes ll and lg with ll containing the keys at node 1 that are smaller than km and lg containing the keys at node 1 that are larger than km Ifl was the ith child of 191 before the INSERT operation then the invocation is SPLITpziz The call to SPLITpmiz may cause pz to become full In that case we repeatedly apply SPLIT to the parent of the current node until we reach a parent that is not full or we reach the root If the root becomes full we split the root and create a new root with two children This is the process through which the height of a B tree increases As with SEARCH the INSERT operation takes 0h disk accesses and Otlogt n time The DELETE operation is similar to INSERT but somewhat more complicated It has the same disk access and time bounds as SEARCH and INSERT 318m Krische Lecture 39 M 112408 1H NMR Spectroscopy In the prior lecture we learned the fundamentals of NMR spectroscopy including how to predict the number of equivalent H s and the ratio of nonequivalent hydrogens in a molecule We also saw that nonequivalent hydrogens appear at different chemical shifts as a function of their structural environment Every hydrogen in an organic molecule is surrounded by a cloud of electrons which exerts its own magnetic eld that opposes the applied eld Therefore different hydrogens in different local environments absorb energy of slightly different frequency The net effect is that electron rich hydrogens appear stronger In the case of hydrogens attached to sp3hybridized carbons the induced magnetic eld of the electrons reinforces the nuclear magnetic moment Therefore erich H s appear at higher eld while epoor H s appear at lower eld Memorize some representative values In the case of hydrogens attached to spzhybridized carbons the induced magnetic eld of the 1 bonding electrons opposes the nuclear magnetic moment Additionally there is an electron withdrawing effect associated with the increased Gcharacter of this orbital Thus vinylic and aryl hydrogens appear at low eld 4555 ppm and 68 ppm respectively Alkynes are a special case The induced magnetic eld of the cylindrical picloud reinforces the nuclear magnetic moment However the increased scharacter of the sphybrid orbital is highly electron withdrawing These factors cancel out and acetylenic hydrogens appear at around 23ppm Signal Splitting For two adjacent and nonequivalent hydrogens the apparent magnetic moment of Hydrogen A will align with or oppose the apparent magnetic moment of Hydrogen B and vice versa Therefore in the case where there is only Hydrogen B the signal corresponding to Hydrogen A will be split into Ha Hb and Ha Hb ie a doublet If there are two Hydrogen B s four possible combinations arise two of which are degenerate in energy Ha Hb1Hb2 Ha Hb1Hb2 Ha Hb1Hb2 Ha Hb1Hb2 Since the middle two combinations are degenerate the signal for Ha is split into a triplet In general for a given hydrogen the NMR spectrum will consist of N1 lines where N number of equivalenthydrogens This is the N1 rule The extent to which Hydrogen A and Hydrogen B in uence one another is called the coupling constant The coupling constant J is the distance between the adjacent lines comprising the doublet triplet quartetmultiplet The coupling constant should not be confused with the distance between signals represented by nonequivalent hydrogens Notation of 1H NMR spectra chemical shift is indicated by the symbol delta s singlet d doublet t triplet q quartet etc Therefore delta 249 d 3H a doublet at 249 ppm that integrates to 3 hydrogens likely to be a methyl group with a single neighboring hydrogen Given this information we were able to predict the 1H NMR spectrum of ethyl iodide and several other compounds mature 2 Edward A Lee H John Reekie Department of EECS U C Berkeley Pipelining seqliential i u pipelined Typic l DSP Fetch Decode Read Execute interlocking 0 hardware instruction scheduling Pipeline operation and programming style Read Execute Decode Fetch Lvsw 39I iine stalionmy pipeline model 0 Programmer controls each cycle 0 Motorola DSP56001 MAC X0Y0A XR0X0 YR4Y0 O ld j m 4 m 1 1 U 0 Data stationary pipeline model 0 Programmer speci es data operations TMS320C3040 mpyf ar0 1 ar1ir0 r0 FL 7 Interlocking pipeline E 0 Programmer is protected from pipeline effects Pipeline hazards R Decode Fetch F 0 A control hazard occurs when a branch instruction is decoded Flush the pipeline 0 or Delayed branch expose pipeline 0 A data hazard occurs because an operand cannot be read yet 0 Assume programmer did it deliberately 0 or Interlock hardware inserts bubble LAC 064h SAMIM AR2 Avoiding control hazards hardware looping ead Execute R Decode Fetch A key factor in the numeric perfor F D R mance of DSPs i sth e provision of special hardware to perform looping RPT COUNT TBLR A repeat instruction repeats one or a block of following instructions The pipeline is lled with th repeated instruction or block of instructions 0 Cost one pipeline ush only Each tap requires 0 fetching one data samp e 0 fetching one operand multiplying accumulating shifting one sample in the delay line lmplles of the architecture 0 at least 3 memory accesses per instruction 0 auto increment or decrement addressing modes DSP speci c addressing features modulo Data shifting addressing Time Buffer cuntents Next sample 39 implements circular buffers and delay lines 0 bit reversed addressing 0 used to Modulo addressing implement the Time radix 2 FFT Buffer contents nN SHIFTER SHIFTER 5 FIR Filter in TMS320C50 Coefficients Memory locations COEFFP Program mem address Newest data sample LASTAP Oldest data sample Point to oldest sample MACD COEFFP APAC SACH Y l Singlecycle loop Cleamup Initialize Practice problems You should know the basic antiderivatives ll fzndz n1 11 0 nfil 2i fidzlnlzlC H etc Of course this list is NOT COMPLETE Do not forget to add an arbitrary constant to get most general antiderivativesi Also remember that the antiderivative integral of a sum or difference of functions is the sum or difference of the antiderivatives integrals of the functions Caution Similar statements are NOT true for the product or ratio of functions Find antiderivatives a 1714 2W2 dz 1 b 3 71 dz 2 c 7 2 dx 3 d 721 dz 4 e 10141 sin 15 cos I5 2 dz lt5 Solve problem 3 on page 4 in the integration notesi Find areas of the regions l7 H and llli sin I5 Find areas of the regions l7 H and III in Figure 1 Find areas of the regions l7 H and III in Figure 2 Let the speed be vt l 7 t37 for 0 S t S 2 Find the displacement and mileage traveled during this time problem 5 on page 7 in the integration notesi i You start moving at t 0 Let vt t3 7 472 3t7 for any t 2 0 Find the displacement and mileage traveled from t 0 to a tl b t2 c t3 d t4 e Write the formula for displacement at any time Figure 1 Figure 2 Lecture 4 NMR Spectroscopy NMR spectrometer NMR speclrum Radiu l rcquenc plm39lrnlnngnm nr superconducting mngnel The Splitting Problem What is Going On Signal Splitting Huh Why What is going on here What a mess Signal splitting splitting of an NMR signal into a set of peaks by the influence of neighboring nonequivalent hydrogens This splitting business is actually rich in informationit is a wonderful thing Let s go back to basics What we are doing is trying to find the energy to effect a spin ip We know that this depends on the effective magnetic field which we see as difference in frequency Energy difference between alluwed nuclear spin states far 11 nuclei Spin JZ aligned against the applied eld 10286 aniline Cnergy Spin 1i aligned with the applied eld 37 705 T Bu Tesla 1 Recall Conditions for Resonance The NET field is the sum of all incident magnetic fields including those from The Giant Magnet applied field Diamagnetic Shielding Field electrons Coupling spin fields of adjacent nuclei As we will see this comes about because nearby spins act as baby bar magnets and if they are close enough they modulate the effective field of the spin you are measuring Other Effects credit card strips earth s field etc Origins of Signal Splitting When the chemical shift of one nucleus is influenced by the spin of another the two are said to be coupled Consider nonequivalent hydrogens H6 and Hb on adjacent carbons the chemical shift of Ha is influenced by whether the spin of Hb is aligned with or against the applied field H a H b Y C C X Origins of Signal Splitting Bo Magnetic eld of H b subtracts from the applied eld Hb signal appears at a higher applied eld Magnetic eld of H b adds to the applied eld H a Signal appears at a lower applied eld 4quotquot Vi fr 51L pmquot quot v quot Diwali wwwiimay The signal of Ha is split into two peaks of equal area a doublet Peak when H Peak when H adds to BD subtracts from Bo I I Origins of signal splitting no neighbors one spin Relative Intensity of Peaks singlet 1 double 1 1 triplet 1 2 1 Quartet 1 3 3 l quintete 1 4 6 4 1 sextete 15101051 Pascal s triangle The binomial coef cients The N1 Rule The 1HNMR signal of a hydrogen or set of equivalent hydrogens is split into N 1 peaks by a set of N equivalent neighboring hydrogens All neighboring hydrogens in the analysis must have the same chemical shift magnetically equivalent If this condition is not met a graphical tree or second order analysis must be used to predict the splitting pattern In other words things get messy u H quota Signal from the p oton of H in ence of 3 Magnetic momems of H spiil ihe signa from M 39 ks of equal In doublet U Two magne c orienla ons coth Jab m p a Inlensny a 11 Applied field no JL elm PII I signal in the absence I W at prawns 1th I llh H 1111 I TX C C C fix E xxxquot I I I I E Prawns at 11 E 5 spllit the signal possible magnetic i 5 131132 o entatinns of lac Jim J maq P prawns 01 H51 1 j 1 1 EDI Applied field HQ 39H39 Hi Ha 1 I E 1 signal In the EDSEHGE H1 ff 0f prawns Hg Hb f r I x a x u I K x z I i 1 x I f I Prawns m Hi I 39 I I split the signal L L I I inti a 13311 FE Jab Jag J b H quartet I passihla magnetic quotquot quotquot Driematinns 0f 2 prawns of Hb quot39 I q I 1 4 BD Ethyl Fragment jab Jabll Jabl Jab l Jab Signal fur Hb Signal for Ha Common Splitting Patterns CH3 X H3 H3 C E39 X CH3 CH3CH2 X CH3 H IC X CH3 3H singlet Methyl 9H singlet tbutyl 2H quartet and 3H doublet ethyl 6H doublet and 1H septet isopropyl M Splitting Patterns n1 n1 2 J H IlH H v J 2 3 333334333 3L 3 3 L H CH3 CH3 r L 3 3 LL 3334333 m3 3 3 L I3H3 CH3 r JJL 3 3 J CHs E r quLu Origins of Signal Splitting Bo Magnetic eld of H b subtracts from the applied eld Hb signal appears at a higher applied eld Magnetic eld of H b adds to the applied eld H a Signal appears at a lower applied eld 4quotquot Vi fr 51L pmquot quot v quot Diwali wwwiimay This will become more clear as we work through some examples But first another concept to introduce Index of Hydrogen Deficiency Used to be called the unsaturation number Valuable characteristic of structure Provides you with number of double bonds or rings in a compound Easy with CHO formulas onlybe careful with N Simplest saturated normal alkanes have H CH2nH CnHZn2 To determine IHD compare the number of hydrogens in an unknown compound with the number in the reference compound which is the corresponding acyclic saturated hydrocarbon the molecular formula of the reference hydrocarbon is CnH2n2 Index of H Deficiency H H 2 No correction is necessary for the addition of atoms of Group Vl elements 0 S to the reference hydrocarbon They sort of insert what about carbonyls reference molecule IDH For each atom of a Group Vll element F Cl Br I added to the reference hydrocarbon subtract one H halogen replaces H one for one For each atom of a Group V element N P added to the reference hydrocarbon add one hydrogen These make 3 bonds rather than two Unsaturation Number or HDI x O 0 Should be CnH2112 C5H12 but it is C5H8 Missing H4 So index is 422 HDI Unsaturation Number i 0 0O l H30 CH3 CnH2n2 Z C12H26 99 99 O O HIS2 9 Do these as homework Please 3 rings 6 pi bonds We are Now Ready for Our First Unknown What is this stuff 7 51190 10 9 s 7 t 5 A 3 2 1 0 ppm Chemical Shift 8 So what is behind Answer behind this curtain this zcu ainaa Let s Compare and Contrast 39I Let s Compare and Contrast umfI o H H I an CH C C CH J CH 500 500 400 300 200 100 How about an Aldehyde ml l mu And a Carboxylic Acid j m m4 For Fun Think of Possible Structures that Could Match this Spectrum 2 N LU Ldl 03 J Ch U1 L IN N I some that work H3 Tr H lt can you think of CH2 CHscHZOCW T CHs CHscHZOCHZ C CHs others HzT ltOur Answer Br CH Can you predict the Spectrum eww Draw the chart paper Assign chemical shifts use tables Assign splitting nl rule deal with integral relative numbers quotQuartet Can You Predict the Spectrum 1 Assign number of signals equivalent hydrogens 2 Assign Chemical Shifts use tables 3 Assign Splitting n1 rule 4 Deal with the integrals Relative numbers Our Old Unknown It Should be Easy Now Oh no a new unknown MS Indicates C6H10 Predict a Structure That Matches the Spectrum 11109 TMS The University of Texas at Austin Lecture 6 Department of Computer Sciences Professor Vijaya Ramachandran Randomized Quicksort CS357 ALGORITHMS7 Spring 2007 Randomized Partition and Randomized Quicksort RANDOMIZED PARTITION is a simple modi cation of PARTITION which was de ned earlier in which a random element in the subarray being considered is moved to the last position in the subarray hence this element becomes the pivot7 and then PARTITION is invoked RAND PARTITIONM p r 239 RANDOMpr interchange AM and AM return PARTITIONApr Correctness of RAND PARTITION is immediate once we assume correctness of PARTITION7 since AM is guaranteed to be an element in the subarray Alger The running time remains linear in the size of subarray We now use RAND PARTITION in the randomized version of Quicksort given below RAND QUICKSORTM p r Input An array A1n of elements from a totally ordered set p and r are integers with 1 S p S r S 71 Output The elements in sub array Apr are rearranged in sorted order the elements in array A outside of subarray Alpfl are unchanged So initial call is to ifp lt r then q RAND PARTITIONApr RAND QUICKSORTApq 71 RAND QUICKSORTULq 17 0 Correctness of RAND QUICKSORT7 assuming correctness of RAND PARTITION 0 Expected running time of RAND QUICKSORT Expected Running Time of RAND QUICKSORT Let X be the number of comparisons between pairs of elements in array A made by RAND QUICKSORT on an input array A of size 717 where we assume that all elements in the input ar ray are distinct We will show that ElX n log Since the total number of operations executed by RAND QUICKSORT is within a constant factor of the number of comparisons performed by it7 this will bound the expected running time as n log We use a slick7 analysis from the textook to evaluate EX For the purpose of analysis7 let the elements in array A in increasing order of value be 21lt22ltquot39lt2n For 1 S 239 ltj S n7 let Zij zl7 7 277 ie7 Zij is the set of elements in array A with ranks between 239 and j7 both inclusive For each of the above pairs of values 2397j we de ne an indicator random variable Xij for the event that 21 is compared to 277 ie7 Xij 1 if 21 is compared to 27 and 0 otherwise Observation RAND QUICKSORT compares each pair of elements 21 27 at most once Why 7 This is because 0 every comparison between elements in A occurs within some call to RAND PARTITION in every comparison7 one of the two elements being compared is the pivot element in a call to RAND PARTITION the pivot element is compared to each of the remaining elements in the subarray exactly once and after this call to RAND PARTITION terminates7 the pivot element is in its nal position7 and is never examined again Given the above observation7 it follows that 11 l1 Hence we have n71 n n71 n ElX Z Xij Z Z ElXZ by linearity of expectations i1 ji1 i1 ji1 So the main remaining task is to compute EXj for 1 S i lt j S n ie we need to compute PrXj 1 Let W be the event that some element in Zij is chosen as a pivot Until the event W occurs all elements in Z will lie in the same subproblem for RAND QUICKSORT since either all of them will compare low with respect to the current pivot or all of them will compare high with respect to that pivot lf event W occurs then after that call to RAND PARTITION is completed 2 and 2 will not be in the same subproblem for RAND PARTITION and hence will have no chance of being compared Thus the only opportunity for z and z to be compared occurs during the call to RAND PARTITION when event W occurs But from what we saw earlier while arguing correctness of the Observation every comparison made during this call to RAND PARTITION will have the pivot element as one of the two elements being compared Thus if z and z are to be compared one of them must be the pivot element when event W occurs Thus Xij 1 if and only if eitheiquot z 07quot z is the rst element in the set Zij that is chosen as a pivot element Since each call to RANDOM return a unformly random element in the subarray on which it is called the probability that z or z is the rst element in Z that is chosen as the pivot is 2lZMl 2j ii 1 ie 2 E X f l 7 j 7 i 1 We can now evaluate ElX we have used h j 7 i in the following equation to obtain n71 n 2 n71 nii Ele gjglm lt2n7119nlogn y Page 3 Inverse Eigenvalue Problems in Wireless Communications Inderjit S Dhillon Robert W Heath Jr M ty s Sustik Joel A Tropp The University of Texas at Austin C Thomas Strohmer The University of California at Davis Introduction 56 Matrix construction problems arise in theory of wireless communication gt5 Many papers have appeared in IEEE Trans on Information Theory 1w We view these constructions as inverse eigenvalue probems Provides new insights 50 Suggests new tools for solution gt5 Offers new and interesting inverse eigenvalue problems References Rupf Massey 1994 VishwanathAnantharam 1999 Ulukus Yates 2001 Rose 2001 ViswanathAnantharam 2002 AnigsteinAnantharam 2003 Inverse Eigenvalue Problems in Wireless Communications CodeDivision Multiple Access CDMA B U A CDMA system allows many users to share a wireless channel Channel is modeled as a vector space of dimension d Each of N users receives a unitnorm signature vector 3k N gt d Each user39s information is encoded in a complex number bk In each transmission interval a user sends bk 8k Each user may have a different power level wk Base station receives superposition 251 bk k 3k l v where v is additive noise The base station must extract a bk from the ddimensional noisy 6566666 6 observation Reference Viterbi 1995 Inverse Eigenvalue Problems in Wireless Communications Example gt0 Intuition the signature vectors should be well separated for the system to perform well 51 0 0 E 6 02 3 1 1 1 Inverse Eigenvalue Problems in Wireless Communications Optimal CDMA Signatures LB gt0 For clarity suppose the noise is a white Gaussian random process 5 Form the weighted signature matrix X 4111131 4111232 qUJNSN 51gt One performance measure is total weighted squared correlation TWSC Twscm HXXH m w llt8j7 81 gt6 Minimizing TWSC is often equivalent to finding X for which XXZdwkld and diagXXw1wN 55 Thus X is roworthogonal with specified column norms References Rupf Massey 1994 VishwanathAnantharam 1999 2002 Inverse Eigenvalue Problems in Wireless Communications 5 Connection with Tight Frames 5 An Jrtight frame is a collection of N vectors in Cd such that N Z llty7kgtl2 06 for all y in Cd k1 51gt Jrtight frames generalize orthonormal systems 5 Designing tight frames with specified norms E Designing optimal CDMA signatures under white noise 5 Tight frames also arise in signal processing harmonic analysis physics Inverse Eigenvalue Problems in Wireless Communications Spectral Properties of Tight Frames but The frame synthesis matrix is defined as X dzef m1 acN 51gt Observe that the tight frame condition can be written yXXy or for all y in Cd 239 y gt0 Four equivalent definitions of a tight frame 55 The rows of X are orthogonal gt5 The d singular values of X are identical 50 The d nonzero eigenvalues of XX are identical 5 The Gram matrix XX is a scaled rankd orthogonal projector Inverse Eigenvalue Problems in Wireless Communications