Study Guides (248,042)
United States (123,275)

CAS CS 330 Midterm: CS330-Midterm Notes

16 Pages
Unlock Document

Computer Science
CAS CS 330
John Byers

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

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
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.

Add your courses

Get notes from the top students in your class.