Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
DSA
Data Structures & Algorithms
| Question | Answer |
|---|---|
| When would we write f(n) ∈ O(g(n)), and what does it represent? | When there exists constants C, n0 > 0 such that for all n >= n0, ∣ f(n) ∣ ≤ ∣ Cg(n) ∣ An upper bound on how fast f grows as n increases |
| When would we write f(n) ∈ Ω (g(n)), and what does it represent? | If there exist C, n0 >0, such that for all n > n0: C∣ g(n) ∣ ≤ ∣ f(n) ∣ A lower bound on how fast f grows as n increases |
| When would we write f(n) ∈ θ(g(n)), and what does it represent? | If there exist C0, C1, n0 > 0 such that for all n > n0: C0∣ g(n) ∣ ≤ ∣ f(n) ∣ ≤ C1∣ g(n) ∣ Both upper and lower bounds given by same function. |
| What is the worst case complexity? | The (best) upper bound on the complexity of an algorithm. |
| What does bubble sort do, and what is it's complexity? | Multiple passes over an array of items, swapping neighbouring items that are out of order as it goes. Complexity is O(n²). |
| What does the selection sort do, and what is it's complexity? | Selects smallest remaining element of input array and appends it to the end of all already inserted elements by partitioning the input array. Complexity is O(n²). |
| What does the merge sort do, and what is it's complexity? | Recursively splits problem into smaller problems until left with arrays containing one element. Merges sorted pieces into bigger sequences until fully sorted. Complexity is O(nlogn). |
| What does the quick sort do, and what is it's complexity? | Selects a pivot, then partitions the array to left/right pivot, and recursively repeats on the two partitions. Complexity is O(nlogn), but in worst case O(n²). |
| What does amortized complexity mean? | Average time taken over a sequence of consecutive operations. |
| What does the pigeonhole sort do? | Sorts the numbers from 0 to n-1, in place of the array. e.g 3 is in a[3], etc. |
| What does it mean for a sorting algorithm to be stable? | It does not change the order of items in the input if they have the same sort key. |
| What is a data type vs abstract data type (ADT)? | A type is a set of possible values with a set of allowed operations on those values. An ADT is a type whose internal representation is hidden to the user, e.g integer. |
| What is a list? | An ordered collection of elements. |
| What is a linked list? | They hold values of a particular type, and have nodes containing a value variable holding the value and one or more node variables to identify the next node in a linked list. |
| Name the three stack operations, and define a stack. | push, pop, isEmpty. A list of values that perform in a Last In First Out (LIFO) manner. |
| Name the three queue operations, and define a queue. | enqueue, dequeue, isEmpty. A list of values that perform in a First In First Out (FIFO) manner. |
| What is an invariant (in code)? | A condition on code that must be true during the execution of some section of code (e.g a loop). |
| In Computer Science, what is a tree, binary tree and quad tree? | A data structure consisting of linked nodes connected in a graph, with each node having at most one parent node, and zero or more children nodes. Binary trees have at most 2 children per node. Quad trees have exactly 4 children per node. |
| What is the level of a node? | The depth, i.e the length of the path from the node to the root (root has level 0). |
| What is the height of a tree? | The length of the longest path from the root to a leaf, i.e the max depth of a node. |
| What is the size of a tree? | The number of nodes in the tree. |
| What makes a binary tree complete, and what makes it full? | Complete: if every level, except possibly the last, is completely filled, and all leaves on the last level are placed as far left as possible. Full: If every node has 0 or 2 children. |
| What is a depth first search and it's time complexity? | Traversing the tree using recursion results in following a branch until its leaf, backtracking if value is not found. Time complexity is O(n). |
| What is a breadth first search and it's time complexity? | Traversing the tree by levels, i.e all children on level 1 visited before level 2. Time complexity is O(n). |
| What is a heap/priority queue and it's basic operations? | An ADT that maintains a collection of items with an associated priority value, and can return the item with highest priority efficiently, usually done using keys. Opeations: EmptyHead, insert, get_max, delete_max. |
| What is a heap tree? | A tree where the key of each node is bigger than or equal to the key of it's children. |
| How are type/binary search trees ordered? | Either empty or values in left subtree are smaller than the root, and values in right subtree are larger than the root. These subtrees are also binary search trees. |
| What is the most efficient way of deleting from a binary search tree? | If it's a leaf, remove it. If only one of it's children is not empty, replace the node with the root of the non-empty subtree. Else, find smallest value in right sub tree, replace deleted value with this, and replace smallest node with it's right child. |
| Define the balance of a node. | The difference between the height of the left and right subtree. In specific, height(left) - height(right). Height of an empty tree is -1. |
| What makes a Binary Search Tree an AVL tree? | The balance at every node is either 1, 0 or -1. |
| How do you rebalance an AVL tree after insertion? | Through performing left/right rotations that must preserve order. |
| How do you know whether to perform a left rotation or a right rotation? | Follow the path to the root and find the lowest unbalanced node. If balance is -2, and balance of it's right child -1 or 0, apply L rotation. If balance is 2, and balance of it's left child 0 or 1, apply R rotation. |
| How do you know whether to perform a RL or LR rotation? | Follow path to the root, and find the lowest unbalanced node: If balance is -2 and balance of the right child is 1, apply RL rotation. If balance is 2 and balance of left child is -1, apply LR rotation. |
| How do you insert a value into an AVL tree? | Insert as if a regular Binary Search Tree, and update balance of nodes on the path from the root until the height of tree remains unchanged. |
| How do you delete a value from an AVL tree? | Delete the node using the Binary Search Tree algorithm. Update balance of all nodes on the path from last updated node to the root. Follow updated path, find the lowest unbalanced node and rotate as necessary. |
| If an AVL tree has n nodes, what is it's height and time complexity of executing operations? | Height = θ(log n) Time complexity = O(log n) |
| What is a graph? | Objects and their pairwise relationships, built from nodes/vertexes (V) and edges (E). G = (V, E) is a graph. |
| How can a graph be represented in code? | Using an adjacency list/matrix, ingredients as follows: -A linked list V containing vertices -A linked list E containing edges -Each edge e has a pointer to two of its endpoints -Each vertex v has pointer to each of it's incident edges |
| How can you use BFS exploration to search graphs and identify all vertices reachable from s? (Assuming graph G = (V, E), and starting vertex v) | Create sets Explored and Unexplored, and Q = queue, initialised from s. Put s in Explored, all others Unexplored. While Q != empty, dequeue the next vertex v, and for each edge (v, w), if w is unexplored, mark it as explored and enqueue it. |
| What do you use to find the shortest distance between two nodes on a weighted graph, and how does it work? | Dijkstra's algorithm. It considers each connected node and visits arcs with minimal cost, adding it to a set until optimal solution found. |
| What is topological sorting? | Given a directed graph G = (V, E), come up with an assignment f of numbers on V such that for each arc (v,w) ∈ E, f(v) < f (w) |
| What is a connected component? | Given a graph G = (V,E), a connected component is a maximal set of vertices S such that any vertex in S can reach any other vertex in S. |
| What is a strongly connected component? | A connected component, but an edge can exist between different SCCs. This is only for directed graphs. |
| How can you identify all SCCs in a graph? (Name the algorithm and define) | Kosaraju's Algorithm. Topologically sort a version of G where edge directions are reversed. Mark vertices of G unexplored. For each vertex, in increasing order: if v is unexplored, increase number of SCC, and do a depth-first-search on (G,v). |
| When finding SCCs, why must we topologically sort the version of G with reversed edge directions? | When topologically sorting, we ensure f(v) < f(w). If v is discovered first, f(w) is assigned before f(v), so f(v) < f(w). But, if w is discovered first, v cannot be discovered in TopoSort. |
| What is a greedy algorithm? | An algorithm which constructs a solution iteratively by making local/myopic decisions each time, and hope it works. |
| What are the inputs and outputs in Prim's Algorithm, and what is it's run time? | Inputs: A connected undirected graph, and a cost/weight for each edge. Outputs: A spanning tree which has the minimum possible sum. Run-time: O(n + mlogn) |
| For any path P, what is the bottleneck of P? | The max-weight edge. |
| What is the max flow problem? | Finding the maximum flow that can be sent from a source node to a sink node through a network of directed edges, without exceeding any edge's capacity. |
| What does it mean for e to be saturated? | e is saturated if max flow f(e) = capacity c(e). Otherwise, unsaturated. |
| How can residual graphs be used to solve the max flow problem? | Let f be a flow f in G. The residual graph G(f) is a graph with residual capacity C(f), where C(f)(u, v) = c(u, v) - f (u, v), with C(f)(u, v) being the amount of additional flow that can be sent through (u, v). Edge with no residual capacity are omitted. |
| How does the Ford-Fulkerson Algorithm work? | Initialize f = 0. While there is (s,t)-path P in G(f), the residual graph: f' := maximum flow along P in G(f), f := f + f'. At the end, return f. |
| What makes edges (A,B) an s-t cut? | If s ∈ A and t ∈ B and A U B = V. |
| What is the max-flow min-cut theorem? | For any graph G and (s,t), value of minimum (s,t)-cut = Value of maximum (s,t)-flow. |
| What is a blocking flow? | A flow f in G is a "blocking flow" if every path from s to t in G contains a saturated edge (meaning we cannot push more flow from s to t along a path in G) |
| How does Dinic's Max-Flow Algorithm work? | Similar to Ford-Fulkerson Algorithm, except let G' = (V, E'), where E' = edges in (s,t)-shortest paths in G(f), and let f' := any blocking flow in G'. |
Created by:
user-2035207