Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
119 Cards in this Set
- Front
- Back
|
What is a data structure? |
A systematic way of organizing and accessing data |
|
|
What is an algorithm? |
A step-by-step procedure for solving a problem in a finite space of time |
|
|
Why are arrays not optimal? |
Because they are a fixed size |
|
|
What information does a singly linked list node store? |
Data and Pointer |
|
|
In linked list terms: What's a head |
The first node in the linked list |
|
|
In linked list terms: What's a tail? |
The last node in the linked list |
|
|
In linked list terms: What's a header? |
A sentinel node that has no data and points to the first element in a linked list |
|
|
In linked list terms: What's a trailer? |
A sentinel node that has no data and points to the last element in a linked list |
|
|
What is a linked list? |
An ordered collection of nodes |
|
|
What can circular lists be used for? |
scheduling processes in an OS |
|
|
What's another name for postfix? |
Reverse Polish Notation |
|
|
What's another name for prefix? |
Polish Notation |
|
|
What can queues be used for? |
Playlist Buffers Asynchronous Data Transfer |
|
|
How does a Naive Queue work? |
Moves along memory |
|
|
Why are Naive Queues bad? |
They are an inefficient use of space |
|
|
What is a Deque? |
A double ended queue |
|
|
What does a Deque support? |
Insertion and Deletion at both ends of the queue |
|
|
What is a Deque used for? |
Certain scheduling problems |
|
|
How would you inplement a Deque? |
Use a circular array-based implementation for a simple queue Or use a doubly linked list |
|
|
What is a priority queue? |
An abstract data type storing a collection of prioritized elements |
|
|
What must objects in a priority queue be? |
Comparable |
|
|
Do keys need to be unique in a priority queue? |
No |
|
|
What do keys have to be in a priority queue if they're objects? |
Linear Ordered |
|
|
What's the naive implementation of a Priority Queue |
O Insert at head, search whole list to remove O Insert into ordered list, remove head of list |
|
|
Why are naive implementation priority queues inefficient? |
Because removal and insertion are proportional to the length of the list |
|
|
What does Big-Oh give? |
An upper bound on the growth rate of a function |
|
|
What does "f(n) is O(g(n))" mean? |
The growth rate of f(n) is no more than the growth rate of g(n) |
|
|
Order the orders of growth from smallest to highest |
log(n) n n log(n) n^2 n^3 2^n |
|
|
If f(n) is a polynomial of degree d then f(n) is... |
O(n^d) |
|
|
What two things must you drop when giving the order of growth? |
Low Order Terms Constant Factors |
|
|
What is a linear data structure? |
List-like structure |
|
|
What is a non-linear data structure? |
Richer structure |
|
|
What are three non-specific types of non-linear data structures? |
Non-sequential organisation Hierarchical Structure Networks |
|
|
What is the tree structure? |
A set of nodes organised by the parent-child relationship such that every node except the root has a parent |
|
|
What are the uses of a tree structure? |
Data Storage Data Analysis Search Algorithms Sorting Algorithms (heap sort, priority queues) |
|
|
What is an ordered tree? |
A tree with linear ordering on the children of each node |
|
|
What is an example of an ordered tree? |
A Parse Tree |
|
|
How can a tree be expressed with a Linked Structure? |
Each node has: Pointer to the parent node Data Collection of children |
|
|
What is a base case? |
No recursive calls are made |
|
|
What is the order of binary search? |
O(log n) |
|
|
What is a full/proper binary tree? |
A binary tree where eEach Node has 0 or 2 children |
|
|
What does each node have in a binary tree? |
Left child pointer Right child pointer Data Parent Pointer |
|
|
What is a binary expression tree? |
A proper binary tree where each internal node has an operator and each leaf node has a value or variable |
|
|
What is depth? |
The number of ancestors |
|
|
What is height? |
The longest path from the root to a leaf |
|
|
What is the ith level? |
All nodes of depth i |
|
|
What's the maximum number of nodes at level i? |
2^i |
|
|
What does a comparator object return? |
>0 if more than <0 if less than 0 if equal to |
|
|
What is PQ-Sort? |
Uses priority queue to sort |
|
|
What are the two types of PQ-Sort? |
Selection Sort Insertion Sort |
|
|
What is Selection Sort? |
The variant of PQ-Sort which uses an unsorted sequence |
|
|
What is Insertion Sort? |
The variant of PQ-Sort which uses a sorted sequence |
|
|
What is the Order of Growth for PQ-Sort? |
O(n^2) |
|
|
When ordering complete binary tree nodes, what number is the root? |
0 |
|
|
When ordering complete binary tree nodes, what are the values of the left and right children? |
Left: 2*parent+1 Right: 2* parent+2 |
|
|
What is a binary heap? |
A complete binary tree ordered from top to bottom so that the children keys are larger than their parents |
|
|
What is the term for insertion in a binary heap? |
Up-Heap Bubbling |
|
|
How does up-heap-bubbling work? |
Insert as last node Swap node and parent Repeat until order is restored |
|
|
What is the term for removal in a binary hep? |
down-heap bubbling |
|
|
How does down-heap bubbling work? |
Replace root with last node on heap Swap node with smallest key child until order is restored |
|
|
What is the order of growth for up-heap and down-heap bubbling? |
O(log n) |
|
|
What is the order of growth for heap building when implementing a priority queue using a heap? |
O(n log n) |
|
|
What is the order of growth for heap sorting when implementing a priority queue using a heap? |
O(n log n) |
|
|
What is a map? |
A model of a searchable collection of key-value entries |
|
|
What are examples of maps? |
dictionaries associative memory |
|
|
What are the main operations for maps? |
Searching for things Inserting new things Deleting things |
|
|
What's another name for a key-value pair? |
Entry |
|
|
What's an important part of keys in maps? |
They must be unique |
|
|
How are arrays like maps? |
They have an integer key for the data they hold. THey are special cases of maps |
|
|
What is the simple implementation of a map? |
Using a doubly linked list |
|
|
When is the simple implementation of a map good? |
When the map is small |
|
|
What happens if you insert a key value pair and an entry is found that already has the key in a map? |
That entry's data is replaced and the old data is returned |
|
|
What does remove return in a map? |
returns the value if it's found returns null if not |
|
|
Why are hashtables better at implementing maps than arrays? |
Better performance |
|
|
What two components do hash tables have? |
hash function bucket array |
|
|
What is a bucket array? |
arrays assigned to each array index and hold key value pairs |
|
|
What's the order of growth for insertions, removals, and searches of hash tables? |
O(1) |
|
|
What are the two parts of a hash function? |
1. Generate hash code (keys -> integers) 2. Apply a compression fuction (integers -> [0, N-1]) |
|
|
What does MAD stand for? |
Multiply, Add, Divide |
|
|
What's the equation of MAD? What are the components? |
((ay + b) mod P) P = prime number a and b = non-negative integers [0, P-1] |
|
|
What are the two ways of handling collisions? |
Separate Chaining Linear Probing |
|
|
What is separate chaining? |
Each bucket stores a list-based map |
|
|
What is linear probing? |
Placing colliding items in the next available cell (circular array) |
|
|
What are the 3 conditions that linear probe searching stops at? |
1. An item is found with the key 2. an empty cell is found 3. N Cells have been unsuccessfully probed |
|
|
What does the remove function require for linear probing hash tables? |
an AVAILABLE item |
|
|
What is the load factor? |
The expected number of entries in a bucket Described the probability of a collision |
|
|
What is the ceiling entry in an ordered map? |
entry with the smallest key >= k |
|
|
What is the higher entry? |
smallest key > k |
|
|
When is a search table the best implementation for an ordered map? |
When searches are the primary operation and the maps are small |
|
|
What is an AVL tree? |
A Binary tree with a height balance property so that the height of children of any node differs at most by 1 |
|
|
What extra steps need to be taken for an AVL tree during insertion? |
If the unbalance is right-right/left-left then you rotate the first node that becomes unbalanced and it's unbalanced child and shift the child node to balance If the unbalance is left-right/right-left then you rotate the first unbalanced node and it's unbalanced child and then use the left-left/right-right balance |
|
|
What is a graph? |
A set of nodes connected in some way by a set of edges |
|
|
Define a directed edge |
An ordered pair of vertices |
|
|
What is a directed graph? |
All edges are directed |
|
|
What are endpoints? |
Nodes of an edge |
|
|
Why are we taking this course? |
Because Bill said so. |
|
|
What is a path? |
A sequence of alternating vertices and edges |
|
|
What is a simple path? |
all vertices and edges are distinct |
|
|
What is a cycle? |
A circular path beginning & ending on the same vertex |
|
|
What's a simple cycle? |
All edges and vertices are distinct except start & finish |
|
|
What is an incident edge? |
Edges belonging to a vertex |
|
|
What is the edge-list structure? |
A list of nodes A list of edges Each edge has a pointer to two nodes |
|
|
What is the adjacency list structure? |
On top of the edge-list structure, edges have 2 more pointers: to their references in the sequences for both of the nodes Each node has a sequence of edges (Incidence Sequence) Nodes also have a pointer to their edge collections |
|
|
What's the problem with edge list structure? |
Nodes can't find what edges they're connected to without scanning all edges |
|
|
What is the Adjacency Matrix Structure? |
Similar to the edge list structure There's also another table labelled with nodes that points to edges Edges do not point to these references |
|
|
What is a subgraph? |
Vertices and edges that are a subset of a bigger graph |
|
|
What's a spanning subgraph? |
Contains all vertices of a bigger graph |
|
|
What does "Connected" mean? |
A path between every pair of vertices |
|
|
What is a connected component? |
A maximum connected subgraph |
|
|
What is a tree? |
an undirected connected graph with no cycles |
|
|
What is a forest? |
an undirected graph that has no cycles |
|
|
What's a spanning tree? |
A spanning subgraph that is a tree |
|
|
What is graph traversal? |
Systematic procedure visiting all nodes |
|
|
What can DFS do? |
determine whether G is connected find and report connected components compute a spanning forest |
|
|
What can BFS do? |
determine if a graph is connected Computer connected components Compute a spanning forest |
|
|
What are 3 BFS properties? |
visits all vertices and edges traverse edges frmo a spanning tree the shortest path from a node to another node |
|
|
What's Dijkstra's algorithm |
1. Start at a node and calculate the lowest distance to opposite nodes 2. Choose Lowest node to visit 3. Repeat using all nodes |
|
|
What does BFS use to find the shortest path? |
A Heap |
|
|
What does DAG stand for? |
Directed Acyclic Graph |
