Limited time offer 20% OFF StudySoup Subscription details

Georgia Tech - CS 1332 - Study Guide - Midterm

Created by: Samantha Notetaker Elite Notetaker

Georgia Tech - CS 1332 - Study Guide - Midterm

5 5 3 36 Reviews
This preview shows pages 1 - 4 of a 17 page document. to view the rest of the content
background image CS 1332 Exam 1    06 February 2, 2019    Arrays    •  A sequenced collection of variables of all the same type   •  Values stored in arrays are called  elements   •  Can store primitives & objects   •  Capacity  =  length  = Max # elements that can be stored in an array  # is fixed     •  Indices      •  Declaration          Generics    •  Allows a class to be flexible with type acceptance   •  <T>    Iterator/Iterable    Iterators  •  Usually a special class/object that allows user to easily traverse a data structure  •  Abstract away the specific operations that can be done on a specific data structure  •  Provide a few simple generic methods  Get current item  Go to next item  Go to previous item  •  Java.util.Iterator (an interface)  hasNext()  •  Tells whether calling next() will return next item  •  When false, if you call next() it will return a NoSuchElementException  next()  •  Returns next item  remove()  •  Removes most recently returned item  •  Does not have to be implemented   •  An inner class or private class in Data structure class implements iterator  •  Data structure class itself implements Iterable interface  Iterator()  •  That returns an iterator() instance 
background image CS 1332 Exam 1    06 February 2, 2019  •  User asks for instance of iterator  Call methods in iterator interface to get each item  •  ** adding/removing elements may break iterator  •  Implementation of an iterator for a SLL:    •  How an iterator might be used by user       Iterable  •  Use a for-each loop to go through data structure   Java gets iterator object and gives you back EACH item  Less error-prone than directly using iterator object  •  Less code to write   Class must implement Iterable interface and return a proper iterator       Summary  Iterator  Iterable  Can access all available objects directly  2 methods: next(), hasNext()  Can obtain iterator object from Iterable object and use  it to retrieve all items from Iterable object indirectly  1 method: Iterator<T> iterator()           
background image CS 1332 Exam 1    06 February 2, 2019  Notes  •  Only 1 iterator can be used with for-each loop  •  Only 1 iterator can be returned in iterator() method   Performance  •  Iterator has same/better performance than other methods   •  Arraylist: same complexity as get() for each item  •  Linked list: iterator has better complexity than get() for each item  Iterator: O(n)  Get(): O(n^2)    Recursion    Definition: a programming process where a method calls itself repeatedly until it reaches a defined  termination point      Ex.        Construction:  •  Has selection statements for termination   •  Has recursive calls involving parameter advancing to base  Base case(s): values of parameter(s) for which there is no recursive call   •  Every recursive method must have at least 1 base case  •  Every possible chain of recursive calls must eventually reach a base case  Recursive calls:  •  Explicit calls to current method  •  Each call must be defined so that it advances  towards base case   Visualization: A recursion tree  -  Box for each recursive call   -  Arrow from each caller to callee  -  Arrow from each callee to caller showing return value         
background image CS 1332 Exam 1    06 February 2, 2019  Binary Search Method        Consider 3 cases:  •  Target = data[mid]   Target found    •  Target < data[mid]   Call method on 1st  half of sequence   •  Target > data[mid]   Call method on 2nd  half of sequence         •  Visualize:  •         •  Analyze  Runs O(n)  Portion of list being searched is size (high - low + 1)  After comparison, size becomes 1 of   •    --> each recursion divides list in half --> at mot log(n) levels     Computing powers Ex.  •      --> more efficient:          Tail Recursion  •  Special form - can be interpreted as iteration, avoiding inefficiencies  When every recursive method call is the last step before returning from the method 

This is the end of the preview. Please to view the rest of the content
Join more than 18,000+ college students at Georgia Institute of Technology who use StudySoup to get ahead
School: Georgia Institute of Technology
Department: Computer Science and Engineering
Course: Data Struct & Algorithms
Term: Spring 2019
Tags: java
Name: Exam 1 Study Guide
Description: Exam material covers: Arrays, Generics, Iterator/Iterable, Recursion, List ADT, ArrayLists, LinkedLists, Stacks, Queues, Trees, BSTs, Heaps
Uploaded: 02/03/2019
17 Pages 673 Views 538 Unlocks
  • Better Grades Guarantee
  • 24/7 Homework help
  • Notes, Study Guides, Flashcards + More!
Join StudySoup for FREE
Get Full Access to GATech - Study Guide - Midterm
Join with Email
Already have an account? Login here
×
Log in to StudySoup
Get Full Access to GATech - Study Guide - Midterm

Forgot password? Reset password here

Reset your password

I don't want to reset my password

Need help? Contact support

Need an Account? Is not associated with an account
Sign up
We're here to help

Having trouble accessing your account? Let us help you, contact support at +1(510) 944-1054 or support@studysoup.com

Got it, thanks!
Password Reset Request Sent An email has been sent to the email address associated to your account. Follow the link in the email to reset your password. If you're having trouble finding our email please check your spam folder
Got it, thanks!
Already have an Account? Is already in use
Log in
Incorrect Password The password used to log in with this account is incorrect
Try Again

Forgot password? Reset it here