Exam 2 Review
Exam 2 Review CSC 2310
Popular in Princliples of Computer Programming
verified elite notetaker
Popular in ComputerScienence
This 0 page Study Guide was uploaded by Taylor Kahl on Thursday March 24, 2016. The Study Guide belongs to CSC 2310 at Georgia State University taught by Kebina Manandhar in Winter 2016. Since its upload, it has received 131 views. For similar materials see Princliples of Computer Programming in ComputerScienence at Georgia State University.
Reviews for Exam 2 Review
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 03/24/16
Exam 2 Review From chapter 10 compareTo method allows you to compare objects as less than greater than or equal to 0 many java classes have a compareTo method Example String S and String X can be compared alphabetically a String is quotless thanquot another if it comes before it alphabetically scompareTot s amp t are variable names for Strings returns lt 0 ifs comes before t returns gt 0 ifs comes after t returns 0 ifs t 0 this method is from the Comparable interface which is in the java library so to use compareTo on objects from a class that class must implement Comparable Example de ning a Point class to implement Comparable public class Point implements ComparableltPointgt 0 you have to put the type of object in the ltgt brackets 0 Here39s what Comparable looks like public interface ComparableltEgt this is an abstract method public int compareToE other it has no body statements 0 so if your class implements Comparable it has to have its own compareTo method that completes the body statements and explains how the objects should be compared it must also return an int value 0 Example write the compareTo method to compare Point objects Point objects have x amp y elds xy the method should compare which Point has a greater x value if the x values are equal it should then compare the y values 0 Calling the method pcompareToq p is the implicit parameter o q is passed as an additional parameter o returnlt0ifpltq o returngt0ifpgtq 0 return 0 if p q public int compareTo Point other if x lt otherx x refers to the x eld of the implicit parameter p return 1 else if x gt otherx otherx refers to the x eld of q which was cast as other return 1 else if y lt othery if you reach this point that means x otherx return 1 else if y gt othery return 1 ese return 0 X otherx ampamp y othery From chapter 12 Recursion de ning an operation in terms of itself 0 a recursive method calls itself from within itself 0 Recursive algorithm 1 Base case the simplest solution to a problem directly answerable 0 like if there are 0 iterations or a String is empty 2 Recursive case not directly answerable answered in terms of more simple occurrences 0 Example a recursive method to print a line of n stars 0 What39s the base case Simplest solution n 0 Just print an empty line 0 What39s the recursive case n gt 0 Print a star call the method again for n1 when n gets to 0 the method will print an empty line and stop execu ng public static void printStarsint n if n 0 Systemoutprintln else Systemoutprintquotquot printStarsnl 0 Example a recursive method that accepts a String and returns whether it39s a palindrome Base case a String of length 0 or 1 is automatically a palindrome Recursive case check if the 1st character the last character 0 remove the 1St and last character check the new 1St and last characters 0 repeat until you get to length 1 or 0 o if the String gets that small it means the rest of it is a palindrome returns true public static boolean isPalindromeString s if sength lt 2 return true else if scharAtO scharAtslength 1 String newString ssubstring1 sength 1 without 1St amp last char return isPalindromenewString return false if the 1st character didn39t equal the last it39ll return false 0 The mechanics of recursion java s call stack keeps track of the sequence of methods that have been called imagine each method as a piece of paper the 1St method is a piece of paper the next method goes on top of it the next method goes on top of that and so on java will execute the most recently called method and then move to the next method below it o Recursive tracing a way to keep track of which methods have been called and executed Here39s a trace of one of the methods from our last quiz public static int mystery2int a int n if n 0 return 0 ese return an mysterya n1 int a 4 2 1 4 5 6 1 9 2 3 How does java execute mysterya 4 n 4 execute ese statements return a4 mysterya 3 a4 5 n 3 execute ese statements return a3 mysterya 2 a3 4 n 2 execute ese statements return a2 mysterya 1 a2 1 n 1 execute ese statements return a1 mysterya 0 a1 2 n execute if statement k return 0 return 2 0 2 return 1 2 3 return 4 3 7 return 5 7 12 Dr Manandhar said that backtracking WON39T be on the test that means problems like nding all possible combinations of letters in the String quotmartyquot Make one choice then make another until there are no choices left to be made Then quotbacktrackquot by removing the previously made choices and make a new one until all possible combinations have been made Now go do some recursion practice problems That39s the only way to really learn this stuff From chapter 13 0 Methods for searching lists 0 Sequential search examines every element to nd a target value returns the index of the target value or 1 if it39s not found not very ef cient o Binary search repeatedly divides a sorted list in half to nd target value Examines the middle element If the middle the target it stops 0 if middle lt target eliminates the 1St half searches the larger half 0 if middle gt target eliminates the 2nCI half searches the smaller half repeats until the target is found returns the index of the target value if the target is notfound returns insertionPoint 1 insertionPoint is the index where the target would be in the sorted list Example int a 137 19 binarySearcha 7 returns 2 binarySearcha 16 returns 3 1 4 Ef ciency how much of the computer39s resources are used by a piece of code 0 measured in runtime 0 Assume that every single statement has the same runtime o a loop s runtime N times through the loop number of statements in the loop 0 Example Statementl Statement239 2 for lnti 1 i lt N 39 statement3 2N statement4 for lnti 1 i lt N i l I for intj 1 lt Nj statement5 NN N2 This code will take N2 2N 2 units of time to run 0 Growth rate change in runtime as the size of input N changes 0 depends on the highest order exponent of N 0 reported as bigoh notation O or quotruns on the order ofquot 0 Example Runtime 04N3 25N2 8N 17 N3 is the highest order of N ignore the coef cients this code is ON3 quotbigoh of N3quot or quotruns on the order of N3 0 code with a larger growth rate takes increasingly longer to run as more input is added 0 Complexity class category of code s ef ciency based on its growth rate Class BigOh If you double N the growth rate constant 01 doesn39t change logarithmic OlogzN increases slightly linear ON doubles loglinear ON log2N slightly more than doubles quadratic ONZ quadruples cubic ON3 multiplies by 8 exponential O2N multiplies drastically avoid 0 What39s the complexity class of sequentialSearch for N elements it will examine up to N elements as N increases the time to run increases linearly with N I ON 0 What39s the complexity class of binarySearch for an array of size N it eliminates 12 of the elements until 1 remains The number of elements goes in a series N N2 N44 2 1 Or starting from 1 how many times do you need to multiply by 2 to reach N o 1 2 4N4 N2 N o x number of multiplications 2X N after multiplying by 2 x times arrive at N o x log2N Olog2N Sorting rearranging a list in order 0 Arrays amp Collections have a static method sort using these methods requires importing javautil Arrayssortname Collectionssortname this one can be used for ArrayLists of types that implement Comparable 0 because the sort method requires comparing objects 0 Bogo sort scans the list to see if it39s sorted if it39s not randomly shuf es the list and checks again terribly inef cient there39s no limit to how long it could take 0 Selection sort scans list for smallest value swaps it for the value in element 0 check the list for the 2nCI smallest value swap it for element 1 and so on 0 What39s the complexity class of selection sort How many comparisons need to be made 1 then 2 then 3 then N The sum of comparisons NN1 2 N2 N 2 0N2 0 Bubble sort repeated passes through the list swapping adjacent pairs that are unordered slower than selection sort requires more swaps Also 0N2 The code will have to run through the list N1 times 0 each time it runs through the list it makes N1 comparisons N1N1 public static void bubbleSortint a for int i0 ilt aength1 i go through the list Nl times for intj0 jltalength1 j for N1 elements if ajgtaj1 compare it to the next element int tempaj swap elements if necessary aJaj1 aj1temp o Insertion sort examine each element When you reach an element ithat39s less than the one before it swap them Then compare ito every element that comes before it in the list swapping with larger elements until it39s in its proper spot faster than selection sort 0 instead of comparing each element to the entire list you only compare it to the beginning of the list which is already sorted Also 0N2 public static void insertionSortint a for int i0 iltaength1 i go through Nl elements for int ji jgt0 j go through the elements that come before ai if ajgtaj1 int tempaj aJaJ1 aj1temp 0 Merge sort repeatedly divide the list in half sort each half and combine the sorted halves implemented recursively divide by half until each half has 1 element go back and combine the halves o 0Nlog2N N comparisons each time the halves are merged 2x N o x divisions by 2 necessary to get from N to 1 o x log2N The code for merge sort bogo sort and selection sort are in the chapter 13 slides Good luck on the test
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'