CMSC 451 Introduction Stable Marriage Slides By Carl Kingsford Department of Computer Science University of Maryland College Park Based on Chapter 1 of Algorithm Design by Kleinberg Tardos Course overview Objective Study algorithms for interesting computational problems focusing on principles used to design those algorithms Not as focused on recurrence relations as 351 Nor on getting the best smallest runtime Usually interested in proving correctness and efficiency polynomial time Syllabus Basically cover the entire book some chapters more than others We ll skip chapters 9 and 10 although there may be an extra credit assignment related to them Chapters 1 3 should mostly be review we ll cover these over the next two classes Then we ll discuss several general techniques for designing algorithms Greedy algorithms Divide and conquer Dynamic programming 4 Linear programming 5 Network flow 1 2 3 A surprisingly large number of algorithms are based on one of these techniques Syllabus II We ll cover the theory of NP completeness and the P NP problem Finally we ll talk about how to deal with problems for which there is no known good solution Approximation algorithms local search Mechanics Course work 2 midterm exams dates are on the syllabus each 25 of grade 1 comprehensive final exam 40 of grade 12 homeworks 10 of grade Reading for the semester is on the syllabus I strongly encourage you to keep up with the reading Nothing will make the class easier than that Homework Goal with the homeworks is to get some practice designing algorithms and writing up clear solutions Some problems are easy some are challenging Exams will be closed book closed note but you may use your graded homework Messy or poorly written homeworks will not be graded You can work together on the homeworks but you must write up your own solutions independently Homeworks for the first half of the semester are on the handout Why study algorithms It s true that usually a very small portion of real programs deal with the kinds of algorithms we will study But often it s a very important part choosing the right algorithm can often lead to a dramatic increase in performance Changing the algorithm can be far more effective than simply tweaking the code Finally algorithms are fun and interesting in their own right Issues in algorithm design Our focus Correctness Does the algorithm do what it is supposed to do Can we prove it Efficiency Does the algorithm have a runtime that is polynomially bounded Is it as fast as possible How to describe algorithms Describing algorithms Keep it as simple as possible but no simpler Difficult algorithms require more detail than intuitively obvious ones No need to write assembly code high level statements that can obviously be implemented are fine Though this can depend on the context If S is a set we can generally assume we can iterate its elements test if p is in S etc In some contexts we can assume calculating S1 S2 is obviously easy In others we have to spell out how to do this E g suppose S is the set of primes Knowing the level of detail to present is a bit of an art The solved exercises in the textbook can help How to describe algorithms II Prove the algorithm is correct Again keep it simple briefly say why the algorithm works in general and then focus on the non obvious parts Assume you are trying to convince one of your classmates Analyze its efficiency Ensure that it runs in polynomial time Then try to give the best possible worst case upper bound on how many steps it will take Representative problems Some of the problems we ll discuss 1 Interval Scheduling 2 Weighted Interval Scheduling 3 Bipartite Matching 4 Independent Set These are representative problems that we ll come back to over the semester Interval Scheduling You want to schedule jobs on a supercomputer Requests take the form si fi meaning a job that runs from time si to time fi You get many such requests and you want to process as many as possible but the computer can only work on one job at a time Interval Scheduling Given a set J si fi i 1 n of job intervals find the largest S J such that no two intervals in S overlap Weighted Interval Scheduling Suppose you assign a weight vi to each job This models the benefit to you of choosing that job Maybe it is the amount of money the customer will pay Weighted Interval Scheduling Given a set J si fi vi i 1 n of job intervals si fi and their weights P vi find the S J such that no two intervals in S overlap and i S vi is maximized Interval Scheduling can be solved by a greedy algorithm Weighted Interval Scheduling seems to require dynamic programming Bipartite Matching A graph is bipartite if its nodes can be partitioned into two sets X and Y so that every edge has one end in X and one end in Y A matching is a set of edges M such that no node appears in more than one edge in M Bipartite Matching Given a bipartite graph G find a matching M of maximum size Independent Set Definition Independent Set Given a graph G V E an independent set is a set S V if no two nodes in S are joined by an edge Maximum Independent Set Given a graph G find the largest independent set Apparently a computationally difficult problem No efficient algorithm know and good reason to suspect that none exists Independent Set Definition Independent Set Given a graph G V E an independent set is a set S V if no two nodes in S are joined by an edge Independent Set is very general Interval Scheduling can be written as an Independent Set problem How Independent Set is very general Interval Scheduling can be written as an Independent Set problem How Define a graph G with a node for each job request and an edge if two requests overlap The largest independent set to the largest choice of jobs that do not overlap Independent Set is very general Bipartite Matching can also be written as an independent set problem How Hint What are the constraints in choosing edges in a matching Independent Set is very general Bipartite Matching can also be written as an independent set problem How Hint What are the constraints in choosing edges in a matching Let G be the graph we want to find a matching in Define a new graph G 0 with a node for every edge in G Add an edge u v to G 0 if the edges u and v in G share an endpoint The largest choice of independent nodes in G 0 to largest choice of edges that do not share an endpoint in G A representative problem Stable Matching A representative problem Suppose three students are applying for jobs