Exam (elaborations)
INF234 - Algorithms.
- Course
- Institution
INF234 - Algorithms.
[Show more]
Seller
Follow
lydiaomutho
Content preview
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller lydiaomutho. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
75759 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now