CSC263H1 Lecture Notes - Lecture 12: Binary Logarithm, Las Vegas Algorithm, Telescoping Series

35 views3 pages

maroonhyena426

27 Oct 2015

School

Department

Course

Professor

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

Document Summary

Sample space sn = { all permutations of [1, 2, . , n]} with uniform probability distribution (not necessarily a good assumption in general). Note implicit assumption in our choice of sn: no repeated element. Input s one permutation from sn. tn(s) = # of comparisons on input s in sn. Let i = rst element of s. this will be the pivot. t0(s) = 0, t1(s) = 0, tn(s) = n 1 + ti 1(l) + tn 1(g) Because of our choice of probability distribution over the sample space, all permutations are equally likely. , n} equally likely to be rst in s. Pivot equal 1 with probability 1/n, . Also, after parition, l, g equally likely to be in any order. This leads to recurrence for t (cid:48)(n) = e[tn]: 1 n n(cid:88) i=1 (n 1 + t (i 1) + t (n i)) n 1(cid:88) j=1. First, write down expressions for t (cid:48)(n) and t (cid:48)(n 1):

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

9. Write a method with the following header public static void replace (String oldFile, string newfile, char oldChar, char newChar) throws IOException This method opens the file whose name is given by the String parameter oldFile (the input file) for reading, and opens the file whose name is given by the string parameter newlile (the output file) for writing. It then reads every lime in the input file. For each line, it creates a new line identical to the original line, creept for the fact that all occurrences of char oldchar in the original String have been replaced by occurrences of char newchar in the new line. When the new line has been properly created, it write it to the output file. Once all the lines in the input file have been read and a corresponding line has been written to the output file, the method clases both files. Additional notes: • You MAY assume that none of the parameters this method accepts are null; in other words, your method does not have to handle the case where one or more of the parameters are null. You MAY assume that all the 10-related classes have already heen imported properly . Finally, because the replace() method is specified to throw an exception object of type TORxception, you MAY assume that I/O related problems will occur while reading from the input file or writing to the output file. In other words, your method DOES NOT have to check that no such problems occur, and DOES NOT have to manage Texceptions using try-catch blocks. WRITE YOUR replace() METHOD IN THE SPACE BELOW: YOUR replace() METHOD CONTINUED: USE THIS PAGE IF YOU NEED ADDITIONAL SPACE. CLEARLY INDICATE WHICH QUESTION(S) YOU ARE ANSWERING HERE. USE THIS PAGE IF YOU NEED MORE ADDITIONAL SPACE. CLEARLY INDICATE WHICH QUES- TION(S) YOU ARE ANSWERING HERE. • String (package java.lang) Methods: - public String chal wale Al t ri g od med in the chance au - public int length(): R e ach of the string - public char chattin R echar w heefd index public chart to Chachay: Consthis String to a new c r y - public boolean equals Object anbject): Ce this string to and yect - public boolean equalsigmoce Case String anotherstring]: Cam p ing sider this String to anotherString - public int compareToString anotherString: Compare this String to anotherstring graphically returns a negative ef this string before anotherstring, apithe value of this Stringatering distries publie iw paneelgoro (String another Camp i ng Garden ces, string to anoth i ng li hically returns te value of this thing care anotherstring, apie as if this string e r anotherstring, Strings - public int indexin ch Rather within this string of the och ch-lil does not - public int index fint.ch, int from index): Returns the index within this string of the first Roe of character ch, starting the search at position from Index retums - 1 il ch does not in this String - public int indexor (String ste): Returns the index within this string of the first currence of ringt-d eur - public int indexOf(stringate, int from index): Resures the index within the string of the fare currence of shariaparting police froiden liste des not count i ng - public String subat ring it begintndax) Rema new string which is a webstring of this string compend of the chesting at position begintndex (inclusive) - puble string subat ring intaginindex intendindex: Returns a new sering that waring of this string, composed of the characters starting at position beginIndex (inclusive, and ending at - public String replace(char oldChar, char newchar): Returns a new string resulting from replacing a Tences of olchar in this string with new Char. puble string tolon Case(): Returns a new string consisting of all the characters in this sting - publle ting toppe : Roum ingiting of all the c on in this thing uverted to perce - publie ting tet): Returns a copy of this line with leading and wailing whitespace • Scanner (package java.util) Methods: - publie danner File source) thrown jatorio Foundation sa Scanner the fun the specified file - public scanner InputStream source): Cits Scanner that process and from the input stream - puble Scannerstag source): Corsa ww Scanner that produces wales w ed from the specified String -puble vold close(): Cwes this Scanner -puble boolean asext(): Return this can het in its input puble boolean asext.Double(): Return to the taken in this season al ante pasadala w ith Doble() ed publie boolean hat Into: Reutte le inse gule ed wat w eet Int() had - public boolean hati : Return true if this w ee - puble boolean has longt) Return true if the r in this cannerm ane das along the next long) with puble ting at the t e rm from the canner puble double Smerthea ter puble intention there the l ot. puble w ith the need them - puble Intolog m u long • Printstream ( kape Java.io) Methods: a - Pri le rlle) throw alo.Pilo t Pelat ihan the p rile - Printing the throw r alo. Pet Stichw e d the wind - le void lose them - le void phone boolean ve - void prichar public void print chart 6): the way of char public void print double d o uble bed, public void print (int ) Fins int value - public void printet a n net public void printing : Strings - public void printin (1 Tm the line by writing the line para ring - public void printinhoolna ) Prints hoolean when thinorminates the public void printin (cthar c h ar wheelthening the line public void print in char i ta way of cars and then the line public void print in double d in double valued and the terminates the line public void printin(int 1) Pints int value and then into the line public void printin ( jat ova t terminates the line pulle void print intring): Tits Strings then to the line Note that the printwriter class defines the same methods and constructors (except for the fact that the structors are called Print.writer instead of PrintStream) • Math (package java.lang) Methods: - please le podle double bear the value of a t the of - puble balle blanche a Returns they u se of dele with pe r than realto - pietate double random Ruma doble 0.0 wi th .. puble stat la doble sin double a: Rethe puble statie doble con double a Return ther l e, where a ininin we angle, wherea in in e -puble statie doble tan double a) R he i ngold , whereas o m public statie double toeges double agrad): C a ngrad v ideo puble salle de anable and we a r e - - estatie delle au t olewa idle de ahholooble • Character (packape java.lang) Methods: - public static boolean ibigit charch: D i chtechisadil public static int digit(charch, int radix: Return the meal of cho ch in the di radix-lich des representa digit - public statie char forbigit chat digit, ut radix) Rems the character of digit in the disa - public statie boolean isletter charch): Demines if character chalet publle statie boolean islowerCase(char ch): Determines if character ch is a character - public static boolean ipparate(char eh): Determines ir ductes chinuppercase cura nd - publicatie boliwhip (arch Termine if character his white a intola - public static char tolowrane(char chevert hech to low - public static char tolpperCase(char ch): Covers Chococh topp • Array list (package java.util) Methods: - public ArrayList(): Create a new em ArrayList which contains clements of type - public int (1 : R m the number of clans in this list - public boolean isimpty(): Rens true if this in contains no elements - public boolean contains (object o): Return true if this lintutins el compr a re performed using the equals() method on - public int IndexOf(obj ): Returns the index of the first currence of elemento in this list, or lir this listes contain this element companies are performed wing the equals() method - publiek galimt in ): Returns the elementat position index in this list - publieket fint inde element): Replace the element at the position index in this list with the - puble honlanad a ): Appends the specifiedalent to the end of this list. - public void (int in aw e t the specified element the price index in this - publiek veint index): Remove the de s ition index in the list - publie hoolean remove(object a s the fir e of the president of this if it is p r epared wing the equals() methodno - public void clear(): Remes all of the elements from this • Vile (package java.io) Methods: - puble File(String pathname: Creates a File representing the file at the given pathane

CSC263H1 Lecture Notes - Lecture 12: Binary Logarithm, Las Vegas Algorithm, Telescoping Series

Document Summary

Get access

Related Documents

CSC263H1 Lecture Notes - Lecture 6: Quicksort, Sample Space, Random Variable

CSC263H1 Lecture 14: CSC263 Week 7 Lecture 1 Amortized Analysis

CSC263H1 Chapter 11: CSC263 Chapter 11 Hash tables

Related Questions