Please enable JavaScript.
Coggle requires JavaScript to display documents.
chapters of algorithm course - Coggle Diagram
chapters of algorithm course
Chapter 5 (Greedy Algorithms)
Huffman coding
Visualization
Step by step
Interval scheduling maximization problem
Definition
Given a set of requests \(\{1,\ldots,n\}\), find the largest compatible subset.
A subset is compatible if no two of them overlap in time.
\(i{\text{th}}\) request corresponds to an interval of time starting at \(s(i)\) and finishing at \(f(i)\)
Optimal caching (TODO)
Definition
Given a full sequence S of memory references, what is the eviction schedule that incurs as few cache misses as possible?
A cache miss is when you request something in the cache which isn't there (need to remove something from cache to make room for the request)
Dijkstra's algorithm (shortest path)
Step by step
Mark all nodes unvisited
Assign zero tentative distance to initial node and infinity to the other nodes (tentative distance is the current discovered distance from the initial node to the node), and set the initial node as current node.
Consider all unvisisted neighbours and calculate their tentative distance, compare the calculated distance with the current distance and assign the smaller one.
When considered all unvisisted neighbours, mark current node visited
If destination node is visited or smallest tentative distance among unvisisted nodes is infinity, then stop.
Otherwise, select the unvisisted node with smallest tentative distance as the current node and go back to step three
Visualization
Minimum spanning tree
Definition
Find a subset of the edges of a graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight
Prim's Algorithm
Visualization
Step by step
Grow the tree by the edge connecting the tree (but not in yet) with smallest weight.
Repeat step 2 (until all vertices are in the tree).
Initialize a tree with a single node, chosen arbitrarily from the graph.
Kruskal's Algorithm
Visualization
Step by step
Start adding the edges with lowest weight in your path, but exclude those which create a cycle.
Chapter 1 (Introduction)
Stable matching problem
A matching \(f: A\to B\) is a bijection between members of \(A\) and \(B\). Note that each member have a list of preferences(e.g. \(a_1\) prefers \(b_2>b_1>b_3>b_4\))
A matching is stable iff there does not exist any pair \((a,b)\) which both prefer each other more than they prefer those they are matched with.
Gale-Shapley Algorithm
Step by step
Implementation
Chapter 2 (Algorithm Analysis)
Heap data structure
A heap data structre is a tree structure in which every level (except possibly the last) is completely filled, and all the nodes in the last level are as far left as possible.
A heap data structure in which
parent node value \(\le\) children node value
for all parent nodes.
Priority queue
Definition
Each element \(v\in S\) has a value \(\text{key}(v)\) that denotes the priority; smaller keys represent higher priority.
Operations
get_min
\(O(\log n)\)
insert_element
\(O(\log n)\)
Chapter 3 (Graphs)
Tree
Properties of binary tree
Given depth \(d\)
There can be a minimum of \(d+1\) nodes.
There can be a maximum of \(2^{d+1}-1\)
height/depth is the maximum number of edges in any path from the root.
DAC and topological orderings (DFS)
Analogy to a topology order, the order of courses you have to take to take a course (edge represents prerequisite and node represents course)
DAC stands for directed acyclic graphs
Properties of simple graph
Given \(n\) nodes
There can be a maximum of \(\frac{n(n-1)}{2}\) edges (complete graph, same as how many pairs of nodes can you pick from n nodes (n choose 2)).
There can be a minimum of \(n-1\) edges (connected line)
representation
adjacency matrix
incidence matrix
adjacency list
Chapter 4 (Divide and conquer)
Merge sort
Implementation
Visualization
Step by step
Divide the list into two halves and merge sort (recursion)
Merge the smaller sorted lists into a new sorted list.
If list has only one element, it is already sorted, return it.
Closest Pair of Points
Integer multiplication
Counting Inversions
Chapter 6 (Dynamic Programming)
Sequence Alignment
Definition
Largest Common Subsequence
Definition
Find the longest subsequence that is common to all the given sequences, provided that the elements of the subsequence are not required to occupy consecutive positions within the original sequences.
Knapsack problem
Definition
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible
Chapter 7 (Network Flow)
Maximum-Flow Problem
Definition
Find a feasible flow through a flow network that obtains the maximum possible flow rate.
Ford-Fulkerson Algorithm (Greedy)
Step by step
Let \(G_f\) be the residual graph, where \(c_f(u,v)=c(u,v)-f(u,v)\) and if \(f(u,v)\gt 0\) and \(c(v,u)=0\), then \(c_f(v,u)=f(u,v)\)
Let the flow \(f(u,v)\) be zero for all edges \((u,v)\)
While there is a path \(p\) from \(s\) to \(h\) in the residual graph \(G_f\) where \(c_f(u,v)\gt 0\) for every \(c_f\in p\) :
2.1. find \(c_f(p)=\min\{c_f(u,v):(u,v)\in p\}\)
2.2. For each edge in the path, add \(c_f(p)\) flow to \(f(u,v)\) and subtract \(c_f(p)\) of \(f(v,u)\)
Visualization
Minimum Cut
Definition
Find the minimum sum of weights of edges that, when removed from the graph, divide the graph into two sets.
Maximum Bipartite Matching
Definition
Given a bipartite graph, find the largest subset of edges M such that each node appears in at most one edge in M.
NP-complete problems
Packing Problems
Examples
Set Packing (k disjoint sets)
Independent Set (set of no neighbour of size k)
Description
Given a collection of objects, choose \(k\) objects, but there is a set of conflicts between the objects, preventing you from choosing certain groups simultaneously
Covering Problmes
Examples
Set Cover
Vertex Cover
Description
Given a collection of objects, choose a subset that collectively achieves a certain goal, while choosing only \(k\) objects
Sequencing Problems
Examples
Hamiltonian Path (path visiting every node once of length k)
Hamilton Cycle (cycle visiting every node once of length k)
Description
A search over a set of all permutations of a collection of objects.
Partitioning Problems
Examples
Graph Coloring (color graph with k colors, no neighbor)
3-Dimensional Matching (subset of disjoint triples of size k or more)
Description
A search over all ways to divide up a collection of objects into subsets such that each object appears in exactly one of the subsets.
Numerical Problems
Examples
Subset Sum (subset equal sum k)
Description
Everything related to sum
Complexity theory
Polynomial-time reduction \(A\le_p B\)
Definition
Formally, can arbitrary instances of problem A be solved using a polynomial number of standard computational stgeps, plus a polynomial number of calls to a black box that solves problem B?
Informally, if we had a black box capable of solving B, then we could also solve A?
Consequences
Problem A is no harder than problem B, and problem B is at least as difficult to solve as problem A.
Assuming \(P\ne NP\)
\(A\in NP\text{-complete}\Rightarrow B\in NP\text{-complete}\)
\(A\in P\Leftarrow B\in P\)
\(A\in P\Rightarrow B\in NP\)
\(A\in NP\Leftarrow B\in NPC\)
Classes
\(P\)
\(NP\)
\(NP\text{-complete}\)
\(NP\text{-hard}\)
\(\text{co}NP\)
