CIS 110 Final Exam Review 12 5 Array vs Linked List Varying amount of data Access random elements Stack queue Has to be really fast Types of Sorting Array LinkedList Selection Sort The first step is to find the smallest element and make it first using a swap then the second smallest element and make it second using a swap etc If there s a 100 billion elements we d have to do 100 billion comparisons to find the smallest element n 2 The idea of selection sort is rather simple we repeatedly find the next largest or smallest element in the array and move it to its final position in the sorted array Insertion Sort Comparisons are made from the beginning of the array of elements from left to right If the right element is less than the left the two elements swap otherwise they stay in place The process continues Takes just as much time as selection sort n 2 in the worst case In the best case if everything is already sorted everything arrives as you started and you only do n comparisons Merge Sort Divide the list into the smallest groups as possible and individually sort the groups then sort the different parts THE FASTEST KIND OF SORTING Dividing into groups hardly takes any work Combining pairs into groups NlogN 2 to the what power gives you N What We Have To Know About Sorting Know how sorting works the implementation of them and how fast each of the sorting methods is be able to know how to recognize their code May ask questions that ask you to code programs similar to SelectionSort Binary Trees Discussed to lead to the understanding of the graph Root is at the top of the tree and each end node is called a leaf if it has no children If a node does not lead to another node it is considered null Max of two edges leaving a node Binary Search Trees Impose a condition or rule that everything in the left sub tree of the root node comes before alphabetically or numerically etc comes before the root which comes before the right sub tree o Allows you to do binary search o Very useful o Pre order root left right Depth First Search In Order left node right Post Order left right node CIS 110 Final Review Notes 12 8 14 Private cannot access outside class but inside a class is fine o Instance variable private String name private int age private String SSN different class o All classes o Most methods Public Everything has access to a public method whether it s the same class a When would you require a method to be private Private dfs dfs is private because you don t want outside classes to know how dfs runs DFS is a helper function that is only called within findPath There s no reason to call dfs directly besides to be used for findPath Internal methods Static vs non static Non static Whenever you call a method upon an object it is a non static method Only can be called when there are instance variables Need to use h name or object methodName to do the operation o i e Integer parseInt 35 class name static method 35 Navigating Through a Binary Tree Pre order Parent Left Right Post order Left Right parent In order Left Parent Right Binary Tree any kind of tree Binary Search Tree A tree with a rule left and right sub trees NullPointerException Trying to do something on a thing that doesn t exist Dog d SOPL d null If no toString memory dump d wag Dog hasn t been made yet or actually defined yet Look for the existence of n next next 2 places where a null pointer exception could be thrown N is null Or n next is null d itself cannot throw a null pointer exception only d something can throw a null pointer exception Sample questions Can this throw a null pointer exception ArrayIndexOutOfBounds Trying to access an element of the array that doesn t exist Int arr new arr 10 arr 9 YES arr 10 arrayIndexOutOfBounds Same with Strings S charAt s length arrayIndexOutOfBounds Maximum character you can get is S charAt s length 1 ArgumentMismatchException detected at compile time compileTimeError Foo int a String s Foo a 3 ArgumentMismatch here Why Strings are Primitive Types or Objects Neither They have characteristics of primitive types and objects Primitive Types No New Doesn t work by pass by reference Objects equals not capitalized Can call methods on Strings For trees and LinkedList what s the worst case and average case for runtime for contains Concept Computational complexity Input N Worst Average LinkedList N N N 2 Binary Search Tree N N 2 Log2 N Write a function that takes in a string and removes all the vowels in it given a public Boolean method public boolean isVowel char a and returns true if it s a vowel private String withoutVowels String Alex String output for int i 0 i Alex length i if isVowel Alex charAt i false output Alex charAt i return output Types of Exceptions 1 Null pointer exception Alex a because a is null a hi 2 Type Mismatch Trying to pass in something and it s the wrong data type Good example of Type Mismatch Reading in a file and reading in wrong type 3 Illegal Argument Exception Implement a stack via a queue Queue Given a queue and Add and remove make a stack and push and pull Queue first in first out Stack last in first out Change first in first out to last in first out Public Stack