Basics Flashcards
What are combinatorial search problems?
Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions. Finding all permutations/subsets, solving sudoku and 8-queens are classic combinatorial problems.
What does permutation mean?
Arranging things with an order. The number of permutations is given ny n!
What is a combinatorial explosion?
The complexity of combinatorial problems often grows rapidly. The rapid growth of solution space with even a small increase in problem size is called combinatorial explosion.
How can we think of combinatorial search as a tree?
The search space is in the shape of a tree. The tree represents all the possible states is called a state-space tree. Each node of the tree represents a state we can reach in a combinatorial search. Leaf nodes are the solutions to the problem (permutations).
What is the basic solution formula for combinatorial search problems?
- Indentify the states
- Draw the state-space-tree
- DFS/backtracking on the state-space tree.
What are the differences between linear and non-linear data structures?
In linear data structures the data is arranged sequentially where every element is attached to its previous and next adjacent element. (Stack, array, queue, linked list, hash tables (can both be linear and non-linear)).
Non-linear data structures are for example trees and graphs.
What is the primary use case of a disjoint sets data structure?
To address the connectivity between the components of a network. For example given vertices and edges between them, we can determine if two vertices are connected using a disjoint set.
What are the two ways to implement disjoint set?
- Quick find - here the time complexity of find will be constant but the union function will take more time O(N).
- Quick union - here the time complexity of the union function is better (with rank and path compression optimizations) but the “find” function will take more time?
What are the main differences between the quick find and quick union implementations?
Quick find finds the root node of each element during union and selects one of the root nodes to be stored in a root array. Hence checking whether to elements are connected can be done simply by checking if the same root node is written in the root array for both elements.
Quick union does a similar thing except it selects a sub tree root and merges the other node/sub tree to it.
- with rank and path compression we can on averge do this in constant time.
Where is amortized complexity used?
Amortized complexity analysis is most commonly used with data structures that have state that persists between operations. The basic idea is that an expensive operation can alter the state so that the worst case cannot occur again for a long time, thus amortizing its cost.
What is a spanning tree?
It is a connected subgraph in an undirected graph where all vertices are connected with a minimum number of edges.
What is a minimum spanning tree (MST)?
Is a spanning tree with the minimum possible total edge weight in a weighted undirected graph.
What is the cut property (MST)?
We first need to understand two basic concepts:
1. A cut is a partition of vertices in a graph into two disjoint subsets.
2. A crossing edge is an edge that connects a vertex in one set with a vertex in the other set.
The cut property states that for any cut C, if the weight of an edge E in the cut-set of C is smaller than the weights of all other edges in the cut-set, then this edge belongs to all MSTs of the graph.
What is Kruskal’s algorithm?
Algorithm to construct a minimum spanning tree of a weighted undirected graph.
- Sort all edges in ascending order
- Add edges in order. Skip edges that form a cycle.
- Repeat until N-1 edges are added where N is the number of vertices.
What is a Monotonic Queue?
It’s a data structure where the elements from the front to the end is strictly either increasing or decreasing.
We have either increasing or decreasing queue:
- increasing: to push an element, we start from the rear and pop elements that satisfy the less than condition.
- decreasing: we pop elements statisfying the opposite condition.
