CS201 Final - Cheat Sheet PDF

Preview

Summary

string builder appending is O(1), for string concatenation its O(n) implements means you are using the elements of a Java Interface in your class. extends means that you are creating a subclass of the base class you are extending. You can only extend one class in your child class, but you can implem...

Description

string builder appending is O(1), for string concatenation its O(n) implements means you are using the elements of a Java Interface in your class. extends means that you are creating a subclass of the base class you are extending. You can only extend one class in your child class, but you can implement as many interfaces as you would like.

Arrays.sort and Collections.sort are O(n log n) Prioritiy Queue is O(log n) usually queue: FIFO, stack: LIFO 1+2+...+n=n(n+1)/2 = n2 We use breadth first search to find shortest path IPercolate is an interface A binary search tree is O(log n) when balanced and O(n) when unbalanced For LinkedList, remove(0) is O(1) but get(n) is O(n); For ArrayList, remove(0) is O(n) but get(n) is O(1) Brute: N + M log M + k, BinarySearch: log N + M log k + k

overloaded method: compiler decides which method to call - 2 methods have same name but: either dif number of parameters, dif data types of parameters, or dif order of parameters

If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.

Huffman.compress: 1. Determine the frequency of every eight-bit character/chunk in the file being compressed (see line 64 below). 2. From the frequencies, create the Huffman trie/tree used to create encodings (see line 65 below). 3. From the trie/tree, create the encodings for each eight-bit character chunk (see line 66 below). 4. Write the magic number and the tree to the beginning/header of the compressed file (see lines 68-69 below). 5. Read the file again and write the encoding for each eight-bit chunk, followed by the encoding for PSEUDO_EOF, then close the file being written (see lines 71-73 below)....