Lecture 23 November 14 2006 t i m e of bits Fall 2006 Carnegie Mellon University CS 15 251 On Time Versus Input Size John Lafferty Great Theoretical Ideas In Computer Science Recall From Last Time State transition instructions A finite alphabet A set of accepting states A start state Finite set of states qi a a b x 1 qj Q Q qi a q j F qi1 qi2 K qir qo Q qo q1 q2 K qk Finite Automaton b b a b a a b ABA accepts only the strings with an equal number of ab s and ba s b a a Remember ABA i e a bunch of a s followed by an equal number of b s No finite automaton accepts this language n n a b ab aabb aaabbb K Consider the language But a valid M must reject ajbi and accept aibi M will do the same thing on aibi and ajbi i j k s t Si Sj but i j For each 0 i k let Si be the state M is in after reading ai Proof Assume that it is Then M with k states that accepts it Theorem anbn is not regular But be careful Automata can indeed do some kinds of implicit counting Finite automata can t count MORAL 2 Allow more than one transition from a state matching the same input symbol 1 Allow epsilon transitions where a state transition is made but no input symbol is read Two differences Nondeterministic Finite State Automata a b a a b L all strings containing aba or aa a b Running an NFA Parallel Programming convenient to work with But they can be much more compact and equivalent DFA No because any NFA can be written as an Does this give us any more power NFA DFA a a a a b ab a b aba a b abab b a b Invariant Machine is in state s when s is the longest suffix of the input so far that forms a prefix of ababb e b L all strings containing ababb as a consecutive substring a b a b b a b Nondeterministic machine Equivalent to regular expression a b ababb a b a b L all strings containing ababb as a consecutive substring Important to note A A U B s s A or s B A B s s ab for a A b B A s1 s2 L sk si A k 0 The class of regular languages is closed under union concatenation and Regular Operatons on Languages Closed under Union A U B s s A or s B Regular Operatons Proof by Picture Closed under concatenation A B s s ab for a A b B Regular Operatons Proof by Picture Closed under A s1 s2 L sk si A k 0 Regular Operatons Proof by Picture reasoning more transparent DFAs sequential evaluation NFAs parallel evaluation NFA can be more compact and interpretable Uniqueness of state in DFA can make set of languages Two slightly different descriptions of same NFA vs DFA Summary and we don t mean New Topic The Big O How to add 2 n bit numbers How to add 2 n bit numbers How to add 2 n bit numbers How to add 2 n bit numbers How to add 2 n bit numbers Grade school addition How to add 2 n bit numbers T n amount of time grade school addition uses to add two n bit numbers What do you mean by time Time complexity of grade school addition We want to define time in a way that transcends implementation details and allows us to make assertions about grade school addition in a very general yet useful way Our Goal A given algorithm will take different amounts of time on the same inputs depending on such factors as Processor speed Instruction set Disk speed Brand of compiler Roadblock We can only speak of the time taken by any particular implementation as opposed to the time taken by the method in the abstract But you agree that T n does depend on the implementation Hold on The goal was to measure the time T n taken by the method of grade school addition without depending on the implementation details Here is how it works There is a very nice sense in which we can analyze grade school addition without having to worry about implementation details Your objections are serious Bonzo but they are not insurmountable Total time to add two n bit numbers using grade school addition cn c time for each of n columns Pick any particular computer M and define c to be the time it takes to perform on that computer On any reasonable computer adding 3 bits and writing down the two bit answer can be done in constant time Total time to add two n bit numbers using grade school addition c n c time for each of n columns On another computer M the time to perform may be c M c n M hine c a M of bits in the numbers ne i h ac M The fact that we get a line is invariant under changes of implementations Different machines result in different slopes but time grows linearly as input size increases t i m e n c Grade School Addition is a linear time algorithm Thus we arrive at an implementation independent insight I see We can define away the details of the world that we do not wish to currently study in order to recognize the similarities between seemingly different things Abstraction Abstract away the inessential features of a problem or solution This process of abstracting away details and determining the rate of resource usage in terms of the problem size n is one of the fundamental ideas in computer science Exactly Bonzo What is the growth rate of Timen We often ask Define TIMEn the worst case amount of time used on inputs of size n For any algorithm define Input Size of bits to specify its inputs Time vs Input Size n2 X How to multiply 2 n bit numbers n2 The total time is bounded by cn2 abstracting away the implementation details I get it X How to multiply 2 n bit numbers of bits in the numbers No matter how dramatic the difference in the constants the quadratic curve will eventually dominate the linear curve t i m e Grade School Addition Linear time Grade School Multiplication Quadratic time http www cs belllabs com cm cs pearls sortanim html Graphic Demonstration of Running Times How much time does it take to square the number n using grade school multiplication Ok so t i m e c log n 2 time to square the number n of bits in numbers Grade School Multiplication Quadratic time t i m e Input size is measured in bits unless we say otherwise of bits used to describe input Time Versus Input Size T n Start at a and increment by 1 b times Nursery School Addition Input Two n bit numbers a and b Output a …
View Full Document
Unlocking...