Join StudySoup for FREE

Get Full Access to
ASU - CSE 205 - Study Guide

Description

Reviews

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. If you want to learn more check out What is the acidity of alkynes?

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. Don't forget about the age old question of Desert occur at what latitude?

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 (Xy) and 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. We also discuss several other topics like What general pattern describes human heterosexual mating
preferences?

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 If you want to learn more check out Starch can be converted into what?

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). If you want to learn more check out What are the three types of stress?

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). We also discuss several other topics like What makes a family?

- 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 1st 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 2nd 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`