Level 108 Level 110
Level 109

Algorithms II


68 words 0 ignored

Ready to learn       Ready to review

Ignore words

Check the boxes below to ignore/unignore words, then click save at the bottom. Ignored words will never appear in any learning session.

All None

Ignore?
Greedy algorithms
Choose the highest value first
Why is the naive approach to the rod cutting algorithm bad?
Naive recursive solutions are highly inefficient due to the fact that they solve the same sub problems over and over.
How does the dynamic approach to rod cutting work?
Using memoization, we can solve each subproblem only once, and refer back to the subproblem's solution if needed later.
How is the memoization process more efficient?
The approach trades computation time for memory.
Btree non root
T - 1 to 2t - 1 keys
Btree root
1 to 2t-1 keys
Btree non leaves
One more children than keys
Btree leaves
All at the same level
Internal node property
Has a min (t-1) and a maximum number of keys in the node (2t - 1)
What type of algorithm is Prim's?
greedy algorithm for finding the minimum spanning tree
Prim's complexity
O(E log V)
Differences between Quicksort and Merge sort
Quicksort is a conquer-then-divide algorithm, which does most of the work during the partitioning and the recursive calls. The subsequent reassembly of the sorted partitions involves trivial effort. Merge sort is a divide-then-conquer algorithm.…
Quicksort pseudocode
function quicksort(array)
What is a hash table?
A hash table is a data structure that stores key/value pairs and can be quickly searched by the key
Stack
Data structure for Depth first search
Queue
Data structure for Breadth first search
Quicksort steps
Step 1. Choose a pivot value.
Pseudocode for inserting into a binary search tree
1 Check whether value in current node or new node are equal. If so, duplicate is found. Otherwise:
How do you choose a good hash function?
The function should provide a uniform distribution of hash values. This is because a non-
Euler Path
Euler vs Hamiltonian Paths and Cycles
Greedy Algorithm
an algorithm that follows problem solving heuristic of making optimal choices at each stage. Hopefully finds the global optimum. An example would be Kruskal's algorithm.
Divide and Conquer
works by recursively breaking down a problem into two or more sub problems until the problems become simple enough to be solved directly. An example would be mergesort.
Recursive Algorithms
solve a problem by solving smaller internal instances of a problem -- work towards a base case.
Dynamic Programming
Break down a problem into smaller and smaller subproblems. At their lowest levels, the subproblems are solved and their answers stored in memory. These saved answers are used again with other larger (sub)problems which…
Selection Sort
Non-stable, in place sort. Has an N-squared order of growth, needs only one spot of extra space. Works by searching the entire array for the smallest item, then exchanging it with the first ite…
Insertion Sort
Stable, in place sort with an order of growth which is between N and N-squared, needs only one spot of extra space and is dependent on the order of the items. Works by scanning …
ShellSort
Non-stable, in place sort with an order of growth which is undetermined, though usually given at being N-to-t…
Quick Sort
Non-stable, in place sort with an order of growth of NlogN. Needs lgN of extra space. It has a probabilistic guarantee. Works by making use of a divide and conquer method. The array is div…
3-Way Quick Sort
Non-stable, in place sort with an order of growth between N and NlogN. Needs lgN of extra space. Is probabilistic and dependent on the distribution of input keys.
Mergesort
Stable sort which is not in place. It has an order of growth of NlogN and requires N amount of extra space. Works by dividing an array in half continuously into smaller and smaller arr…
Heap Sort
Non-stable, in place sort which has an order of growth of NlogN. Requires only one spot of extra space. Works like an improved version of selection sort. It divides its input into a sorted…
Lower Bound on the complexity of pairwise comparisons
No compare based sorting algorithm can have fewer than ~NlogN compares
Counting Sort (Key Indexed sort)
An integer sorting algorithm which counts the number of objects that have a distinct key value, and then used arithmetic on those countes to determine the positions of each key value in the output array.
LSD Radix Sort
Stable sort which sorts fixed length strings. Uses an axillary array, and therefore is not in place. Goes through to the last character of a string (its least significant digit), and takes its value.…
MSD Radix Sort
Used to sort an array of strings based on their first character. Is done recursively and can sort strings which are of different lengths. This algorithm will be slower than its counterpart if used…
Unordered Linked List
Data structure with non-efficently supported operations. Is unordered. Has a worst case cost of search and insertion at N, an average case cost of insertion at N, and an average case cost of searching at N/2.
Binary Search
An ordered array of data which has efficiently supported operations. The worst and average case of a search using this structure is lgN. The Worst case of an insertion is N, and the average …
Binary Search Tree
Will have a best case high of lgN. This is also its expected height. In the worst case, it will have a height of N, and thus become similar to a linked list.
2-3 Tree
Balanced tree data structure with logN complexities on searching, inserting, and deleting in both the worst and average cases. In this data structure, every node with children has either two children and one data elem…
Red Black Tree
Worst case height of 2log(n+1). The nodes are either red or black. The root is black. If a node is red, its children MUST BE BLACK. Every path from a node to a leaf …
Tries
A collection of nodes, each of which can hold a key and a value- often the values will be null. The nodes will have a value attached to the last character of the string …
B-Trees
Items are stored in leaves. The root is either a leaf, or it will have between two and M children. All non-leaf nodes will have betwe…
Undirected Graph
Given any path connecting vertices A and B, you can travel from A to B or B to A
Directed Graph
Given a path connecting vertices A and B you can only travel in 1 direction
path
A drive and list of directories pointing to a file such as C:\Windows\command.
Weighted Graph
A graph which places "costs" on the edges for traveling their path
Cycles
When there are at least two unique paths which connect vertices A and B, forming a loop or loops
DAG (Directed Acyclic Graph)
A graph which is directed and contains no cycles
Depth First Search
A method which is used to traverse through a graph. Works by creating a stack of nodes to visit, which consist of all the nodes around your current position. You move to the next loca…
Topological Sort
Linear ordering of the vertices of a directed graph such that for every directed edge "uv" which connects "u" to "v" (u points to v), u comes before v. This ordering is only possibl…
Minimum Weight Spanning Trees (MST)
A spanning tree whose weight is no larger than the weight of any other spanning tree which could be made with the graph. The properties of this thing include that the graph is connected,…
Prim's Algorithm
MST builder/Greedy Algorithm which works by taking a starting vertex and then successively adding the neighbor vertices which have the lowest cost of addition and don't create cycles upon their addition.
Kruskal's Algorithm
MST Builder/Greedy Algorithm which works by taking edges in order of their weight values, continuously adding edges to the tree if their addition doesn't create a cycle.
Union Find
Data structure used to make sure a cycle is not created in a MST.
Dijksta's Algorithm
Finds the shortest path with no negative weights given a source vertex. Tries to find the distance to all other vertices in the graph. It produces a shortest paths tree by initializing the distanc…
Memoization
What happens when a sub problem's solution is found during the process of Dynamic Programming. The solution is stored for future use, so that it may be reused for larger problems which contain this …
Bellman-Ford Algorithm
Algorithm which computes shortest paths from a single vertex to all other vertices in a weighted digraph. Is slower than its counterpart, but is able to handle edge weights with negative values. Works by initi…
Class
A class is the blueprint from which individual objects are created. It is the code template you write.
object
A database item that contains data, as well as the actions that read or process the data.
Method
A sequence of statements that has a name, may have parameter variables, and may return a value
PARAMETER
A value that can be given to a function to get different results from the instructions
signature
Combination of identifiers, return value, name and parameters of a method. Example: public int calculateMonth(String name)
type
Specifies what kind of thing a variable or a parameter is. Example: int, char, boolean...
instance
An object.
multiple instances
The case when there are multiple objects from the same class instantiated at runtime.
State
a value of some condition that occurs during an object's life
return value
The value that comes back from a method after it is run. In the following method: public int calculateMonth(String name), the return value is an integer.
Field
A column in a table.