### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Exam 2 Review CSC 2310

GSU

GPA 4.21

### View Full Document

## 131

## 7

## Popular in Princliples of Computer Programming

## 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.

## Popular in ComputerScienence

## Reviews for Exam 2 Review

### 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.