C949 Flashcards
Array
An ordered list where each item is directly by a positional index. A data structure that stores subitems. Primary search method, Binary.
Linked list
Stores ordered list of items in nodes. Each node stores data and has a pointer to the next node. Faster than an array.
Hash Table
Stores unordered items by mapping(or hashing) each item to a location in an array(or vector)
Chaining
Handles hash table collision by using a list for each bucket. Each list may store multiple items that map to the same bucket.
Bucket
Each element in a hash table
Hash Key
Value used to map an index
Modulo hash function
(num_keys/num_buckets)
Hash table searching
Supports fast search, insert and remove. O(1) linear search requires(N).
Max-Heap
A binary tree that maintains the property that a node’s key is greater than or equal to the node’s children key. The root is always the max key.
Heap Storage
Heaps are stores using Arrays. If represented by a tree the root node is always entry 0. Works with Tree based data structures.
Max-Heap Insert
An insert into a max-heap starts by inserting the node in the tree’s last level. Then swapping the node with it’s parent until no violation occurs.
Max-heap remove
Always removes the root. Each node is swapped until no violation occurs.
Percolating
The upward movement of a node in a heap.
Min-Heap
Like a max-heap, but a node’s key is less than or equal to it’s children’s keys.
Heap parent and child indices
Because heaps do not have a node structure nodes are referred to by index. Parent index for a node at index 12: ((12-1) // 2) = 5, child index for a node at index 6: 2* 6 + 2 = 14 **Double # and add 1, double # and add 2.
Priority Queues with Heaps
Both functions return the value in the root, but the Pop() function removes the value and the Peek function does not. Pop and Push worst case is 0(logN) and Peek, IsEmpty and GetLength is worst case O(1)
Array Based List
A list ADT implemented using an array. Allows for operations such as append, prepend, insert after, remove and search.
Linked List vs Array
If a program requires fast insertion a linked list is a better choice.
Abstract Data Type(ADT)
A data type described by a predefined user operation. Such as “insert data at rear” without indicating how each operation is implemented.
Array in Java
Generic class that supports different data types.
Tuple
A container with ordered elements.
Stack
An ADT with “Last in first out” rule. Pop and Peek cannot be used in empty list.
Stack and Queue in Python
Can be implemented using a class with a single linked list.
Queue
An ADT in which items are inserted at the end and removed from the front.(Linked List, Array, Vector)
Linked List
A linear data structure that consists of nodes that link to the next node.
Double Linked List
A data structure that can also include a reference to the head node. If no variable is assigned returns None or Null.
Dequeue
Short for double ended queue. Items can be inserted and removed from the front and back.
Bag
An ADT for storing items in which the order does not matter and duplicates items are allowed.
Set
ADT for a collection of items. No duplicate items. (BST/Hash Table)
Priority Queue
A queue where each item has a priority. Higher are closer to the front.(Heap)
Dictionary(Map)
Keys and Value Pairs (BST, Hash Table)
Graph
A data structure for representing connections among items. Consists of vertices connected by edges.
Vertex
A line item in a graph. Also called nodes.
Edge
A connection between two vertices
Graph Weight
The graph in which weight is associated with edges
Graph Direction
The graph in which all the edges are bidirectional
Binary Tree
Each node has up to two children
Leaf
A node with no children
Internal Node
A node with at least on child
Depth
The number of edges away from the root.
Height
The largest depth of any node.
Preorder traverasal
Root, left, right
Bubble sort
Sorting Algorithm that swaps adjacent elements if the second element is less than the first element. Has a runtime of O(N2) N is the number of elements in a list.
Bucket sort
Sorting algorithm that individually sorts. Useful when input is uniformly distributed over a range.
Merge Sort
Continually splits a list in half. Used with a recursive function
Big O complexity
Best to worst: O(1), o(logN), O(n), O(nlogN), O(n^2), O(2^N), O(nl)
Radix Sort
10 buckets
Interval Search
Divides the data in half until it finds the target. Fastest for sorted data.
Record
Data structure for items that are related.
Class
A term for a template to create an object.
Characteristics of an algorithm
Uses an agnostic code repository.
O(1)
Constant time. Always at the top.
O(N)
Linear time. Twice as many variables means twice as much time.
O(log N)
Logarithmic time. Splits the variables in half with each search. Cutting time.
O(N^2)
Quadratic time. Checks every variable against every other variable. Twice as many variables means four times as long.
O(N^3)
Exponential. Longest
Quicksort
a sorting algorithm that repeatedly partitions the input into low and high parts (each unsorted), and then recursively sorts each of those parts. To partition the input, quicksort chooses a pivot to divide the data into low and high parts. The pivot can be any value within the array, commonly the value of the middle array element. Runtime O(N log N)
Selection Sort
Selection sort is a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part. Runtime O(N^2)
Insertion Sort
a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part. Runtime O(N^2)
Merge Sort
Merge sort is a sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list. The recursive partitioning continues until a list of one element is reached, as a list of one element is already sorted. Runtime O(N log N)
Radix Sort
Radix sort is a sorting algorithm designed specifically for integers. The algorithm makes use of a concept called buckets and is a type of bucket sort.
Any array of integer values can be subdivided into buckets by using the integer values’ digits. A bucket is a collection of integer values that all share a particular digit value
Bubble Sort
a sorting algorithm that iterates through a list, comparing and swapping adjacent elements if the second element is less than the first element. Runtime O(N^2)
Quickselect
an algorithm that selects the
smallest element in a list. Ex: Running quickselect on the list (15, 73, 5, 88, 9) with k = 0, returns the smallest element in the list, or 5.
Bucket Sort
a numerical sorting algorithm that distributes numbers into buckets, sorts each bucket with an additional sorting algorithm, and then concatenates buckets together to build the sorted result.
