CSC263H1 Lecture Notes - Lecture 2: Sample Space, Big O Notation, Upper And Lower Bounds

61 views2 pages

maroonhyena426

27 Oct 2015

School

Department

Course

Professor

For unlimited access to Class Notes, a Class+ subscription is required.

Document Summary

For algorithm a, t(x) represents the number of steps executed by a on input x. Worst case running time of a on inputs of size n is denoted ta(n). T (n) = max{t(x) : x is an input of size n} Linkedsearch(l, k): z = l. head while z != none and z. key != k: z = z. next return z. L. length (# of elements in l) n. T (n) = an + b for constants a, b t (n) (n) We have 2: z != none, z. key != key. For algorithm a, consider sn = sample space of all inputs of size n. to de ne average , we require a probability distribution over sn speci ying the likelihood of each input. Let tn(x) = num of steps executed by a on input x in sn. note: tn is a random variable (assigns numerical value to each element of probability space).

Related Questions

9. Finally, you should write a program MontrealMaps which will suggest a path to go along the metro to get from one place to another. The only required method for MontrealMaps is a main method but of course you are allowed to write others. Your program should do the following. For any library methods that you use, make sure that you are properly importing things and handling any exceptions they may throw. (10 points) • Using an appropriate library method, you should create a Subway System object. If this method fails to initialize, you should print the message Error, not enough funding. • Use a Scanner and print statements to read the current x and y position of the user. • Use a Scanner and print statements to read the x and y position that the user wants to go to. . Find the nearest Metro Station to both the start position of the user and his final destination. • If the 2 metro stations have the same name (i.e. are the same metro station) then print It is fastest to walk there. • Otherwise, call the method findPath from the previous part to find a path from these 2 metro stations. . If the method returns null, then print Sorry, there is no path on the metro, you'll have to walk • Otherwise, print the path using the metro using the method printPath defined in the MapUtilities class in the appendix. SUMMARY OF JAVA STANDARD LIBRARY METHODS POR SELECTED CLASSES • String package java.lang) Methods - public boolean gist and e rs is stingeancoject - puble boolean grease Sering another ca t ering String paint i th Stre C h eshilly before the Stripe with striert w Single weiter water N ENE fusha -publish tohy Casting de . File( p age java.io) Methods r eate - publie Yiling path : C • Scanner (package java.ut 1) Method -ple S ule - double Double Sc - le bon when : S Scanner tal de fethede h able othebean - puble String Best Mus eethe u s tepal -pulle haalean haxtLine: Check the hea ther in left PrintStream( p age java.io) Methods pul vaid pri Pribonaat - puli wid pride d oble vile. - pille vaid print Print vei. -pulle vaid printject o: Prints Object -puli vaid printString : Prints String .. - vaid primi The theme line by writing the li n e tie id print in bool bl. Prise n value the - public void platinabled Prints double ved and then the line - public void printit Prints Ent value and then tomis the - Pull vaid pri l l be t he minime publie wild prin t ing with String in the terminates the line • ArrayLiat package java.util) Methods - public boolean Arraybettype was a new ArrayList

CSC263H1 Lecture Notes - Lecture 2: Sample Space, Big O Notation, Upper And Lower Bounds

Document Summary

Get access

Related Documents

CSC263H1 Lecture 5: CSC263H1 TUT 5

CSC263H1 Lecture Notes - Lecture 10: Zij

CSC263H1 Lecture 3: CSC263H1 TUT 3

Related Questions