This week we continue the discussion of applications of max flow and in particular the weighted maximum matching problem in bipartite graphs. As mentioned this is also a nice segway to a discussion of integer and linear programming. We will also mention the graph labelling problem and then begin a discussion of linear programming (LP) rounding of an integer program (IP).
Every year, the department organizes an Alumni Mentorship Program where we match students with alumni working in the industry, based on your interests and those of the mentors. This is a great opportunity to find out what the jobs you're interested in are really like, from someone working in one of those jobs who has gone through one of our programs. If you are interested, please consult the [url=https://csc.cdf.toronto.edu/bb/YaBB.pl?num=1256508467]official announcement[/url] for more details (including a link to the application form). Note that the deadline for applications is [b]Monday 23 November[/b] and the program [b]is[/b] open to students who are currently on PEY.
The start of problem set 3 is now available. I have now included a question on max flows as well as the two previous local search questions.
I am attaching (for a short time) a proof apperaring in a text by West that for bipartite graphs, maximum matching size equals minimum vertex cover size and the minimum vertex cover can be computed using augmnenting paths.
As promised here is a handout showing how to reduce polynomial division to polynomial multiplication .
As promised, here (for a short time) are the relevant pages from Knuth's Vol 3 where he outlines how to achieve O(n^2) time bound for computing an optimal binary search tree .
It is the case that the d dimensional nearest pair problem can be solved (by a ``multidimensional divide and conquer'') algorithm in time O(d n log n). The original reference is Bentley and Shamos, STOC 1975. Briefly stated, while the immdeiate generalization of the two dimensional divide and conquer algorithm will result in an O(d n log^{d-1} n) (or even O(2^d n log^{d-1} ni if we are not careful) time algorithm, the improved time bound comes from a judicious choice of a dividing cut plane (perpendicular to one of the axis) to use for dividing the points. Namely, they prove that given a distance delta that there is a cut plane such that there are at least n/8 points on each side of the plane and there is a sublinear (in n) number of points within distance delta of the cut plane. They use an additional procedure (like the statement in problem 3a) to find all points within distance delta given that the number of points within a ball of radius delta has no more than some constant number of points). It is important that when projecting down onto the cut plane, the sparsity condition (with the same constant) remains intact.
Students are encouraged to check the undergrad announcements (UGA) website which contains announcements about things such as job and scholarship opportunities, academic and social events, and reminders of administrative deadlines. Students are also reminded as to guidelines as to How not to plagarize .
Please send any comments or questions to the instructor:
You may also find it helpful to look at the problem sets and other handouts for the most recent versions of CSC373 , and my most recent CSC375 courses .
Problem Sets, Tests and Other Handouts will be posted here.