### Create a StudySoup account

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

Already have a StudySoup account? Login here

# CSE 205 - Exam3 - Study Guide CSE 205

ASU

GPA 4.0

### View Full Document

## Popular in Object-Oriented Program & Data

## Popular in Computer Science and Engineering

This 13 page Study Guide was uploaded by RianMartins on Friday November 27, 2015. The Study Guide belongs to CSE 205 at Arizona State University taught by Hsiao in Fall 2015. Since its upload, it has received 64 views. For similar materials see Object-Oriented Program & Data in Computer Science and Engineering at Arizona State University.

### 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: 11/27/15

CSE 205 – STUDY GUIDE EXAM 3 - Recursive methods A recursive method is a method that calls itself. To avoid infinite loop inside the method, we must follow some crucial steps. All recursive methods should have (as the first statement of the method) a base case and a recursive case. The base case is a condition that checks whenever it should return a value and get out the method. The recursive case is where the actual call for the function is located. See some examples below: o Recursive factorial public int factorial(int n){ if (number <= 1) // test the base case return 1; else return n * factorial(n-1); } o Recursive reverseString public String reverseString(String str){ if(str.length() == 1){ return str; } return reverseString(str.substring(1)) + str.charAt(0); } How to construct a recursive method: 1. Identify your sub-problem. i.e., the same problem as the original problem, but on a subset of the original input. 2. Think how you can use a solution of the sub-problem to solve the original problem. Consider an example to sum all the elements of an int array: the original problem is to compute the sum from 1 to n, and the sub-problem is to compute the sum from 1 to n-1. If we had the sum from 1 to (n-1), then we just need to add n to it to get the sum from 1 to n. 3. Also consider your base case(s). 4. When converting an iterative method to a recursive method, in some cases additional parameter(s) might be needed. One such parameter is the variable used to increment or decrement the loop in iterative methods. You can practice on writing recursive methods starting computations on power (X ) andy factorials. - Understand java collection framework The java collection framework has lots of benefits, some of them are: It dramatically increases the readability of your collections by providing a standard set of interfaces to be used by many programmers in many applications. It makes your code more flexible by allowing you to pass and return interfaces instead of concrete classes, generalizing your code rather than locking it down. It offers many specific implementations of the interfaces, allowing you to choose the collection that is most fitting and offers the highest performance for your needs. A basic set of collection implementations: In addition to the trusty Hashtable and Vector, which have been updated to implement the Collection interfaces, new collection implementations have been added, including HashSet and TreeSet (set), ArrayList and LinkedList (list), and HashMap and Map (map). Using an existing, common implementation makes your code shorter and quicker to download. Also, using existing Core Java code core ensures that any improvements to the base code will also improve the performance of your code. o List A List is an ordered Collection (sometimes called a sequence). Lists may contain duplicate elements. Elements can be inserted or accessed by their position in the list, using a zero-based index. o Set A Set is a Collection that cannot contain duplicate elements. There are three main implementations of Set interface: HashSet, TreeSet, and LinkedHashSet. HashSet, which stores its elements in a hash table, is the best-performing implementation; however it makes no guarantees concerning the order of iteration. TreeSet, which stores its elements in a red-black tree, orders its elements based on their values; it is substantially slower than HashSet. LinkedHashSet, which is implemented as a hash table with a linked list running through it, orders its elements based on the order in which they were inserted into the set (insertion-order). o Map A Map is an object that maps keys to values. A map cannot contain duplicate keys. There are three main implementations of Map interfaces: HashMap, TreeMap, and LinkedHashMap. HashMap: it makes no guarantees concerning the order of iteration TreeMap: It stores its elements in a red-black tree, orders its elements based on their values; it is substantially slower than HashMap. LinkedHashMap: It orders its elements based on the order in which they were inserted into the set (insertion-order). - LinkedList The linkedList is a dynamic data structure that grows and shrinks as required by the information it contains Using Iterator in the ArrayList We can use the iterator of an ArrayList object to traverse it (without using any index). ArrayList arraylist1 = new ArrayList(); ... Iterator iterator1 = arraylist1.iterator(); while (iterator1.hasNext()) { System.out.println(iterator.next()); } Here, we use iterator.next() to access each element in the array list. Since a linked list does not have any index to trace each element, we need to use an iterator such as above. Note that the above loop is equivalent to: for (int i=0; i<arraylist1.size(); i++) { System.out.println(arraylist1.get(i)); } The ListIterator interface allows access of a position in a linked list. This interface contains a subset of the methods of the standard java.util.ListIterator interface. The methods for backward traversal are not included. public interface ListIterator { //Moves the iterator past the next element. Object next(); // Tests if there is an element after the iterator position. boolean hasNext(); // Adds an element before the iterator position and moves the iterator past the inserted element. void add(Object element); // Removes the last traversed element. This method may only be called after a call to the next() method. void remove(); // Sets the last traversed element to a different value. void set(Object element); } We have Linked List class in java.util package. (but it is important to have some idea of how it is implemented as a programmer. We need to know how efficient to do each operation using it.) Comparison between ArrayList and Linked List (in terms of Efficiency of operations of ArrayList and LinkedList): --------------------------------------------------------------- Operation ArrayList LinkedList --------------------------------------------------------------- Access O(1) O(n) Add/Remove O(n) O(1) -- assuming that the iterator is already in the right position an element -In ArrayList, we can access any element by specifying its index in constant time. – O(1) -In LinkedList, we need to go through n/2 elements on average to get to an element. – O(n) -In ArrayList, adding or removing an element can take O(n) (=O(n/2) on average) because of shifting all elements. -In LinkedList, adding or removing an element can be done in constant time, assuming that the iterator is already in the right position – O(1). Depending on the algorithm we write, we should choose a data structure that is more efficient. Example: public class LinkedListTester { public static void main(String[] args) { LinkedList list1 = new LinkedList(); ListIterator iterator = list1.listIterator(); iterator.add("A"); printList(list1); -> { A } iterator.add("B"); printList(list1); -> { A B } iterator.add("C"); printList(list1); -> { A B C } iterator = list1.listIterator(); iterator.next(); iterator.add("D"); printList(list1); -> { A D B C } iterator.next(); iterator.add("E"); printList(list1); -> { A D B E C } iterator = list1.listIterator(); iterator.next(); iterator.remove(); printList(list1); -> { D B E C } iterator.next(); iterator.next(); iterator.remove(); printList(list1); -> { D E C } } //This method prints out the content of LinkedList public static void printList(LinkedList list1) { ListIterator iterator = list1.listIterator(); String result = "{ "; while (iterator.hasNext()) result += iterator.next() + " "; result += "}"; System.out.println(result); } } o Stack A stack is a data structure in which access is only allowed from one end. Imagine the candy Pez dispensers You insert and remove candy from the same end. The first piece in is the last piece out. You have a stack of books - to get to the bottom, you have to remove the ones on top. This is called LIFO - Last-in/First-out Java.util.Stack • Provides the stack class • Constructor • isEmpty or empty • peek - get the top item without removing it • pop - remove the top item • push - push a new item onto the stack • size - the number of items in a stack Implementation • A stack can be implemented using an array or a linked list – Using an array, elements are pushed and popped from the back end of the array – Using a linked list, elements are added (pushed) to the head of the list and also removed from the head of the list when popped. o Queue A queue is a data structure of ordered items where items are added to the rear (in the order that they are entered and removed from the front.) Examples: • The first person in line at a bank is served first and so on. People are served on in respect to their position in line. • At the bakery, you pull a number out of the machine that distributes numbers in order on a first-come, first serve basis. When your number in the queue is called – it is your turn. A queue is a FIFO (First-in / First-out) data structure o Adding an item is called “enqueue” (Entering the queue) o Removing an item is called “dequeue” (Removing from the queue) Implementation • There are “manyNodes” representing the number of nodes • The head is the front of the queue (where items are removed) • The rear (tail) is the end of the queue where the items are added) - Tree & Tree Traversal Tree Traversals: How can we process or go through all nodes in a tree? We will look at three types of traversals, pre-order traversals, in-order traversals, and post-order traversals. o Pre-order Traversal: The root is processed previous to its two sub-trees. For a non-empty tree: Step1: Process the root. Step2: Process the nodes in the left sub-tree with a recursive call. Step3: Process the nodes in the right sub-tree with a recursive call. //The following preorderPrint method prints the data from each node //at or below this node of the binary tree. //Assume that this method is defined in the Node class in the previous page. public void preorderPrint() { System.out.print(data + “ “); if (left!= null) left.preorderPrint(); if (right != null) right.preorderPrint(); } o In-order Traversal: The root is processed in between the processing of its two sub-trees. For a non-empty tree: Step1: Process the nodes in the left sub-tree with a recursive call. Step2: Process the root. Step3: Process the nodes in the right sub-tree with a recursive call. //The following inorderPrint method prints the data from each node //using in-order. //Assume that this method is defined in the Node class in the previous page. public void inorderPrint() { if (left != null) left.inorderPrint(); System.out.print(data + “ “); if (right != null) right.inorderPrint(); } o Post-order Traversal: The root is processed after processing its two sub-trees. For a non-empty tree: Step1: Process the nodes in the left sub-tree with a recursive call. Step2: Process the nodes in the right sub-tree with a recursive call. Step3: Process the root. //The following postorderPrint method prints the data from each node //using post-order. //Assume that this method is defined in the Node class in the previous page. public void postorderPrint() { if (left != null) left.postorderPrint(); if (right != null) right.postorderPrint(); System.out.print(data + “ “); } Binary Search Trees: The binary search property is that any element in the right sub tree is larger than the value of the node, and any element in the left sub tree is smaller than (or equals to ) the value of the node. Thus those elements need to be compared such as numbers or strings. Obs.: In-order Print/Traversal: prints out all the keys in a binary search tree in sorted order. Important Codes: Search Value: TreeNode search (TreeNode root, int k) { TreeNode x = root; while (x != null && k != x.key) { if (k < x.key) then x = x.left; else x = x.right; } return x; } Find Minimum Value: TreeNode minimum (TreeNode x) { while (x.left != null) x = x.left; return x; } Find Maximum Value: TreeNode maximum (TreeNode x) { while (x.right != null) x = x. right; return x; } Heaps: A heap or min-heap (max-heap) is a binary tree with two special properties: 1. A heap is almost complete: all nodes are filled in, except the last level may have some nodes missing toward the right. 2. The tree fulfills the heap property: all nodes store values that are at most as small (large) as the values stored in their descendants. It is easy to see that the heap property ensures that the smallest element is stored in the root. Example of an almost complete tree: For an element at the index i of the array, The index of its left child is: 2*i + 1 The index of its right child is: 2*i + 2 The index of its parent is: the integer part of (i-1)/2 Using these formulas, we can find the children or the parent of a node in the array. For example, For the node at the index = 3, The left child is 2*3+1=7 The right child is 2*3+2=8 The parent is: (3-1)/2 = 1 Insertion steps: Step1: Insert a new element as the last element in the heap (array). (This makes the 1st property of the heap hold.) Step2: Repeat the following until we are done or reach the top of the heap (no parent) Compare the added element to its parent. If the parent is larger than the new element, then swap them Else DONE! (This makes the 2nd property of the heap hold.) Extraction (Removing) steps: Step1: Extract the root element. Step2: Remove the last element in the heap (array) and set it as the root. (This makes the 1 property of the heap hold.) Step3: Repeat the following until we are done or reach the bottom of the heap (no child) Compare the new root element to its children. If at least one of the children is smaller than the new root, then swap it with the smaller value child element, Else DONE! (This makes the 2 property of the heap hold.) HeapSort The main idea: • Build a heap from an array. • With a max-heap, we can extract the root to get the largest value, and put it aside (put it as the last element of the array by swapping the root and the last element.) • Then we continue to extract the next root (the second largest value, and put it as the second last element of the array. • After doing this for n-1 times (where n is the number of elements in the initial heap), we will have a sorted (ascending order) array. To have a descending order array, we can use a min- heap. Since sorting an array means to sort any array, first we need to build a heap before we start extracting the roots. Turning a tree into a max-heap. (Building a max-heap from an array) For each node that has a child node, we call “fixHeap” method. We do this starting the node in the lowest level first, then we do for nodes in the one level above. Then we keep going up to the node in the above level until we call fixHeap on the root. The fixHeap method: Repeat the following until both children are smaller or we reach the bottom of the tree. 1. We compare the node and its children. 2. If at least one of the children is larger than the node, then swap it with the larger child. Else DONE! 3. If it is not done, go back to the step 1, with the node’s new location. Heap Sort summary: (using a max-heap) 1. Build a heap from a given array. 1.1. For each node with at least one child node (i.e., not leaves), starting with the ones in the lowest level and ending with the root (bottom-up order), call the fixHeap (Heapify) method: 1.1.1 Repeat the following until its child nodes are smaller or reach the bottom of the heap: Compare the node and its children. If at least one child is larger than the node, then swap the node with the larger child node. Else, DONE. 2. Extract the root for n-1 times where n is the number of elements in the heap (array). for (int i=0; i < n-1; i++) Extract the root and swap it with the element at the (n-1-i)-th position of the array. Adjust the tree so that the heap property holds for every extraction. Worst case running time of Heap Sort: O(n log n)1`

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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