CS Final Notes PDF

Preview

Summary

Big-Oh:Big Oh Examples Constant: O(1) adding ints, prepending onto a list, finding element in hash map (?)Logarithmic: O(logkn) Finding element in TreeMap, binary searchLinear:O(n) Finding element in unsorted ArrayListLinearithmic/Quasilinear: O(nlogn)Lower bound for comparison sorts, Fast Fourier t...

Description

Arbelaez, ja268

Big-Oh: Big Oh Constant: O(1)

Examples adding ints, prepending onto a list, finding element in hash map (?)

Logarithmic: O(logkn)

Finding element in TreeMap, binary search

Linear:O(n)

Finding element in unsorted ArrayList

Linearithmic/Quasilinear: O(nlogn)

Lower bound for comparison sorts, Fast Fourier transforms

Quadratic: O(n^2 )

Given n points in 2 dimensions, find closest two points

Cubic: O(n^3 )

Given n points in 2 dimensions, determine if any three form a straight line

Exponential: O(k^n)

n queens, a whole lot of interesting problems

Data Structure Array Stack Queue Linked-List

Doubly Linked-List Binary Search Tree

Average

Worst

Access O(1) O(n) O(n) O(n)

Search O(n) O(n) O(n) O(n)

Insert O(n) O(1) O(1) O(n) **O(1) for front and last O(1)

O(n)

O(n)

O(log(n))

O(log(n)) O(log(n) )

Delete O(n) O(1) O(1) O(1)

Access O(1) O(n) O(n) O(n)

Search O(n) O(n) O(n) O(n)

Insert O(n) O(1) O(1) O(1)

Delete O(n) O(1) O(1) O(1)

O(1)

O(n)

O(n)

O(1)

O(1)

O(log(n) )

O(n)

O(n)

O(n)

O(n)

Search

Insert

Delete

Find Min

Unsorted ArrayList

O(n)

O(1)

O(n)

O(n)

Sorted ArrayList

O(log(n))

O(n)

O(n)

O(1)

Arbelaez, ja268 Linked List

O(n)

O(1)

O(n)

O(n)

TreeSet

O(log(n))

O(log(n))

O(log(n))

O(log(n))

HashSet

O(1)/O(n)

O(1)/O(n)

O(1)/O(n)

O(n)

PriorityQueue

O(n)

O(log(n))

O(n)

O(1)

Trie

O(w)

O(w)

O(w)

O(w)

Algorithm Quicksort Mergesort Timsort Heapsort Bubble sort Insertion sort Selection sort Tree Sort

Best O(n log(n)) O(n log(n)) O(n) O(n log(n)) O(n) O(n) O(n^2) O(n log(n))

algorithm

Average O(n log(n)) O(n log(n)) O(n log(n)) O(n log(n)) O(n^2) O(n^2) O(n^2) O(n log(n)) initialize

Worst O(n^2) O(n log(n)) O(n log(n)) O(n log(n)) O(n^2) O(n^2) O(n^2) O(n^2) union

Quick-Find Quick-Union Weighted Quick-Union Weighted Quick-Union with Path Compression

~

find

Arbelaez, ja268

  

Order : O(1) < O(log n) < O(n) < O(n log n) < O(n^c) < O(c^n)< O(n!) < O(n^n) 1 + 2 + … + N – 1 = N(N+1)/2 ⇾ O(n2) 1 + 2 + 4 + 8 … + 2^N = 2^(N+1) - 1 1 + 3 + 5 + … + 2N-1 = (1 + 2 + … + 2N-1) - (2+4+...+2N) = o (2N-1)(2N)/2 - 2*(2N)*(2N+1)/2  =N^2 → O(n2) Big O = O(log n) bc of k *2

Big O=O(nlogn) bc nested loops, n, other log n

Arbelaez, ja268 Big O=O(n) because not nested loops

Big O=O(logn)

Big O=O(n) bc o(n) > o(logn) and take bigger one

Arbelaez, ja268

Linked Lists and Examples: -

-

To add a new node in linked list, make current first node equal to a new node variable, for example OldFirst. make the current first equal to what you’re adding, and then make its next OldFirst. Doubly linked lists have pointers in both directions (can make a comparison with trees)

Arbelaez, ja268 ADDING TO THE FRONT

Arbelaez, ja268 ADDING TO THE END

ADDING TO CERTAIN POSITION

REMOVE FIRST NODE

REMOVE END

Arbelaez, ja268 REMOVE NODE FROM CERTAIN POSITION

REMOVE SPECIFIC NODE

COUNTING NODES public int recsize(Node list) { if (list == null) return 0; return 1 + recsize(list.next); } REVERSE A LIST

last.next = first; add this line before return and then return last to make this circular. REMOVE DUPLICATE

Arbelaez, ja268 RETURN CERTAIN POSITION/DATA

Binary Trees, BSTs, and Tries: -

Tree Traversal o In-order (left, root, right) o Pre-order (root, left, right) o Post-order (left, right, root)

-

Tree height is balanced if left and right subtrees are height balanced, heights of left and right subtrees do not differ by more than one Binary search trees - each node has a value, nodes that are less than parent are in left subtree, greater in right subtree When calling a value, the parameters are (value, left pointer, right pointer) Complete tree = every leaf has two children, all leaves at the same levels o Number of nodes in a complete tree = 1 + 2 + …2N = 2(N+1) – 1 = 2 x 2N – 1 o Big-Oh = O (2N )

-

-

Union Find:

Stacks, Queues, and Priority Queues:

Arbelaez, ja268 -

Stack: Last in first out Queue: First in first out Stacks LIFO, push to add to back, pop removes back.

Recursion: -

-

T(n) = O(1) + T(n/2) o If change * to + doesn’t change runtime, just answer

Base case/exit case where recursive call is not made, all other cases are recursive and slowly getting closer to base case

Arbelaez, ja268

Sorting: -

Comparators: return positive if a is greater, negative if b, 0 otherwise

Percolation Summary: -

PercolationDFS, DFSFast and UF will be at least O(N^2) because they have to open N^(2)/2 cells in the grid - Percolates method in DFS and DFSFast are both O(N) bc have to check whole last row, and constants are dropped - PercolationDFSFast: o Runs the updateOnOpen() function on only the surrounding boxes, not all of them like is done in regular DFS o N^3 - PercolationDFS o N^4 - PercolationUF o With QuickFind is N^4 - QuickUWPC o Implements path compressions as optimizers o N^2 on UF - PercolationStats PurposeTerm- encapsulates a word/term and its corresponding weight, includes several comparators to allow sorting in custom orders. It stores a word/term and weight pair. PrefixOrder- compares Term based on a fixed number of characters at the start of the word. PrefixOrder(r).compare(v,w) should only take O(r) to run independent of length of v and w. String.substring(0,r) takes O(r) to run where r is any value less than the length of the String object on which .substring is called. WeightOrder- compares Term based on weight in ascending order ReverseWeightOrder-^ in descending order **Term.compareTo will sort by lexicographic order using the word parameter only (utilized in BSA constructor) BinarySearchAutocomplete- efficient autocomplete algorithm that finds Terms with given prefix by performing a binary search on a sorted array of Terms. Sorts in lexicographic order in constructor. Immutable class. O(logn + m) First/lastIndexOf- returns the index of the first Terms in the array that is equal to the parameter key (prefix), does so using given comparator, uses binary search ***must make at most 1 + (log2n) comparisons of Terms

Arbelaez, ja268 topMatches- returns the k words with the largest weights that start with given prefix, in order of descending weight. Must return an arraylist or linkedlist or list of string objects. Basic idea: call firstIndOf and last and use this range of M matching terms to find the heaviest k of these matching terms. If M < k, return all M strings that match the given prefix. Priority Queue- min heap based on weights. The last element added to the LinkedList (to the front) will be the heaviest element, it will be the first returned. topMatch- returns the single word with the largest weight that starts with given prefix weightOf- acceses interal collection of Terms, finds th term whose String matches the parameter of w eightOf, returns the weight of given term. If none, 0.0. TrieAutocomplete- a more efficient autocomplete algorithm that finds terms with a given prefix by builing a trie to store the terms. Root is referenced by instance variable myRoot. Nodes are represented using the Node class. O(w) Add- inserts word/weight pair to trie, creates new nodes if needed topMatches- same as before topMatch- same as before weightOf- same as before Autocompletor- implemented by all autocomplete algorithms BruteAutocomplete- uses brute-force search through all terms Big O - BSA TopMatches- O(log(n) + mlog(k) + klog(k)). Logn because of binary search in firstIndexOf call. Mlogk because find all matches and add to pq m times. Klogk because another pq that keeps what you want (k) and adds to it k times. - BSA TopMatch- O(log N + M) if you find all matching terms for the prefix using first/lastindof and then loop over these values to find the term with the highest weight. - BSA weightOf- O(log n). n = number of elements in myTerms. - Trie weightOf- O(w) where w is the length of the String parameter. - Trie topMatches- O(w + logk + logm) - BAC topMatch O(n) - BAC topMatches O(m*n) because you have to search all to find the prefix then search again to find out how many have the prefix (m start with prefix, n terms total) Discussion and Analysis - If you use Arrays.binarySearch to implement BinarySearch.firstIndexOf the worst case = O(n)

Autocomplete Summary: -

Term o Creates 3 comparators BinarySearchAutocomplete: O(logn +m) o firstIndexOf/lastIndexOf o topMatches: O(log(N) + Mlog(N))

Arbelaez, ja268 From first index to last index (the ones that match the prefix), adds them to a PQ, compares the weight, if greater it adds it to the list to be returned o topMatch: O(log(N) + M)  From first index to last, if weight greater than max, replace it TrieAutocomplete: O(w) o topMatches: O(w+logk+logm) 

-

Arbelaez, ja268...