INF234 - Algorithms
∅
empty set symbol
∩
the union symbol. represents the set of all unique elements from both sets.
∪
The intersection symbol. Represents the intersection of two sets, which is the set
containing common elements between both sets.
⊆
The subset symbol. Means that the left set has few or all elements equal to the other set
⊂
the strict subset symbol. means the left subset has fewer elements than the other set.
∈
The "element of" symbol. Means that an element is a member of a set.
∈/
the "not element of" symbol. means that there is no set membership.
\
the relative complement symbol. represents objects that belong to A and not to B.
|·|
the cardinality symbol. Represents the number of elements in a set.
Bipartite graphs
A graph where the vertices can be divided into two sets such that all edges connect a
vertex in one set to a vertex in the other set. There are no edges between vertices
within the sets.
A bipartite graph cannot have an odd cycle.
To test Bipartiteness, use BFS and alternate "colors" for each layer of neighbors.
Finding a neighbor with the current color of the "cycle" means the graph is not bipartite.
Topological ordering
A linear ordering of vertices such that for every directed edge u-v, vertex u comes
before v in the ordering. Graph must be a DAG to have a topological ordering and vice
versa.
, Modified approach using DFS for ordering
Strongly connected components
A strongly connected component is a component of only a directed graph that has a
path from every vertex to every other vertex in that component.
Brute force between all pairs or use Tarjan's Algorithm
Interval Scheduling
Given N events with their starting and ending times, find a schedule that includes as
many events as possible.
Algorithm: always select the next possible event that ends as early as possible
Interval Partitioning
Given N events with their starting and ending times, find a minimum number of
resources to schedule all lectures so that no two occur at the same time using the same
resource (classroom problem)
This problem can be solved optimally with a greedy strategy of scheduling requests
based on earliest start time i.e., from the set of remaining requests
Scheduling to minimize lateness
Given a set of n jobs all of which must be scheduled on a single resource such that all
jobs arrive at time s and each job has a deadline di and a length ti, minimize the
maximum lateness of the resulting schedule
This problem can be solved optimally with a simple greedy strategy of scheduling jobs
based on earliest deadline
∅
empty set symbol
∩
the union symbol. represents the set of all unique elements from both sets.
∪
The intersection symbol. Represents the intersection of two sets, which is the set
containing common elements between both sets.
⊆
The subset symbol. Means that the left set has few or all elements equal to the other set
⊂
the strict subset symbol. means the left subset has fewer elements than the other set.
∈
The "element of" symbol. Means that an element is a member of a set.
∈/
the "not element of" symbol. means that there is no set membership.
\
the relative complement symbol. represents objects that belong to A and not to B.
|·|
the cardinality symbol. Represents the number of elements in a set.
Bipartite graphs
A graph where the vertices can be divided into two sets such that all edges connect a
vertex in one set to a vertex in the other set. There are no edges between vertices
within the sets.
A bipartite graph cannot have an odd cycle.
To test Bipartiteness, use BFS and alternate "colors" for each layer of neighbors.
Finding a neighbor with the current color of the "cycle" means the graph is not bipartite.
Topological ordering
A linear ordering of vertices such that for every directed edge u-v, vertex u comes
before v in the ordering. Graph must be a DAG to have a topological ordering and vice
versa.
, Modified approach using DFS for ordering
Strongly connected components
A strongly connected component is a component of only a directed graph that has a
path from every vertex to every other vertex in that component.
Brute force between all pairs or use Tarjan's Algorithm
Interval Scheduling
Given N events with their starting and ending times, find a schedule that includes as
many events as possible.
Algorithm: always select the next possible event that ends as early as possible
Interval Partitioning
Given N events with their starting and ending times, find a minimum number of
resources to schedule all lectures so that no two occur at the same time using the same
resource (classroom problem)
This problem can be solved optimally with a greedy strategy of scheduling requests
based on earliest start time i.e., from the set of remaining requests
Scheduling to minimize lateness
Given a set of n jobs all of which must be scheduled on a single resource such that all
jobs arrive at time s and each job has a deadline di and a length ti, minimize the
maximum lateness of the resulting schedule
This problem can be solved optimally with a simple greedy strategy of scheduling jobs
based on earliest deadline
