false

Study Guides
(248,042)

United States
(123,275)

Boston University
(4,488)

Computer Science
(38)

CAS CS 330
(3)

John Byers
(3)

Midterm

Unlock Document

Computer Science

CAS CS 330

John Byers

Spring

Description

Stable Matching
How to do it:
Stability: No two people prefer each other
Perfect matching: Every pair is stable.
★ Stable Marriage
○ How to recognize: Two distinct sets of people w preferences
○ Propose and Reject Algorithm
○ Everyone is matched monogamously
○ There is always a stable matching
★ Stable Roommate
○ How to recognize: One set/ group of people w preferences
○ There is not always a stable matching
■ Unlike the stable marriage problem, a stable matching may fail to
exist for certain sets of participants and their preferences. For a
minimal example of a stable pairing not existing, consider 4 people
A, B, C, and D, whose rankings are:A:(B,C,D), B:(C,A,D),
C:(A,B,D), D:(A,B,C)
In this ranking, each of A, B, and C is the most preferable person
for someone. In any solution, one of A, B, or C must be paired with
D and the other two with each other (for example AD and BC), yet
for anyone who is partnered with D, another member will have
rated them highest, and D’s partner will in turn prefer this other
member over D. In this example, AC is a more favorable pairing
than AD, but the necessary remaining pairing of BD then raises
the same issue, illustrating the absence of a stable matching for
these participants and their preferences.
Algorithm:Propose and Reject Algorithm/Gale Shapley(Gives stable matchings)
Initialize each person to be free.
while (some man is free and hasn't proposed to every woman) {
Choose such a man m w = 1st woman on m's list to whom m has not yet
proposed
if (w is free)
assign m and w to be engaged
else if (w prefers m to her fiancé m')
assign m and w to be engaged, and m' to be free
else
w rejects m }
2
Runtime: O(n )
Example Problems:
1)Is there always an instance where there is a man and woman who get their first pick?
FALSE 2) If there is a pair (m,w) that prefer each other they will always be in the stable matching
set. TRUE A man will ask his first preference first. If he is her first preference as well,
then she will never switch.
Max-Sum Subinterval
BFS
Breadth first search. Traversing the entire graph one level at a time.
Algorithm:
Pseudocode:
L0 = { s }.
L1 = all neighbors of L0.
L2 = all nodes that do not belong to L0 or L1, and that have an edge to a node in
L1.
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a
node in Li.
Runtime: O(m+n)
Proof:
total time processing edges is Σu∈V deg(u) = 2m
each edge (u, v) is counted exactly twice in sum: once in deg(u) and once in
deg(v)
Example Problems:
★ Performing BFS
*Alphabetically Chosen*
AB ,AC,AF, BD,CE
★ Finding a single node on its level
★ Finding a edge in which the one u remove destroys all paths between s and t
★ Using BFS to tell whether a computer is infected at a certain time.
Notes: Topological Sorting
★ DAG- is a directed graph that contains no cycles. If a Dag it can and should be put in
topological ordering.
○ Must have a starter node
○ Has some topological ordering
★ Topological ordering-
You have a starting node
Organize graph in a way that puts the classes in order from start to leaf(s)
Applications:
Course Preq
Computing jobs
Compilation
Algorithm:
Pseudocode:
Find a node v with no incoming edges and order it first
Delete v from graph
Recursively compute a topological ordering of G -{v}
Append this order after v
Runtime: O(m+n)
Proof:
Maintain the following information: – count[w] = remaining number of incoming
edges – S = set of remaining nodes with no incoming edges
Initialization: O(m + n) via single scan through graph.
Update: to delete v – remove v from S – decrement count[w] for all edges from v
to w, and add w to S if c count[w] hits 0 – this is O(1) per edge
Example Problems:
-Longest sequence problem
-Longest path
Notes: Strong Connectedness
Def: A graph is strongly connected if every pair of nodes is mutually reachable. Node u
and v are mutually reachable if there is a path from u to v and also a path from v to u
Aka. You can reach all nodes from any specific nodes.
Algorithm:
Runtime: O(m+n)
Proof:
Pick any node s.
Run BFS from s in G.
rev
Run BFS from s in G . (reverse orientation of every s in G)
Return true iff all nodes reached in both BFS executions.
Correctness follows immediately from previous lemma.
Aka. run BFS down and up if all nodes reached both times then it is strongly
connected.
Easy to check:
-Separate components
-Node with no incoming edges.
Bipartiteness
Def. An undirected graph G = (V, E) is bipartite if the nodes can be colored red or blue
such that every edge has one red and one blue end. Proof(s):
1) Suppose no edge joins two nodes in adjacent layers. By previous lemma, this
implies all edges join nodes on same level. Bipartition: red = nodes on odd levels,
blue = nodes on even levels.
2) Suppose (x, y) is an edge with x, y in same level Lj. Let z = lca(x, y) = lowest
common ancestor. Let Li be level containing z. Consider cycle that takes edge
from x to y, then path from y to z, then path from z to x. Its length is 1 + (j-i) + (j-i),
which is odd.
Notes:
★ Can not have an odd length cycle
★ Two nodes in same layer can not be connected
Interval Scheduling(weighted and unweighted)
Unweighted
Input: Set of jobs with start times and finish times.
Goal: Find maximum cardinality subset of mutually compatible jobs.
Earliest___ time(normally finish time)
Weighted
Input: Set of jobs with start times, finish times, and weights.
Goal: Find maximum weight subset of mutually compatible jobs
Algorithm: Greedy( by increasing order of finish time)
Sort jobs by finish times so that f1< f2

More
Less
Related notes for CAS CS 330

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.