Category Archives: fall 2011

Class started with “administrivia” announcements: Notice of Final Solutions to HW10 given at the end of class. We then looked at the general overview of the CSE-331 course: Problem Statement -> Definition -> Algorithm Design -> Implementation -> Analysis Throughout … Continue reading →

P vs NP, Approximation and Randomized Algorithms P vs NP We began by recalling the great question of P vs NP, where P is the set of problems that can be solved by polynomial time algorithms, and NP is the … Continue reading →

Last Class: Atri introduced the Longest Path Problem as a problem in the set of NP problems We were also introduced to the notion of the great P = NP? problem

Posted by: Dylan Grabowski Today we reviewed the three guidelines of when to use Dynamic Programming from last class which are as follows: 1) There are polynomially many sub-problems. 2) The optimal solution can be computed by the sub-problems solutions … Continue reading →

Blog post by Raghu N. Seshadri LAST CLASS: We looked at the shortest path problem where we obtain the shortest path from every s to by inputting a graph of G=(V,E) and all edges have a ce of any weight … Continue reading →

Andrew Westcott Fresh off the Interwebs:  We discussed at the opening of class that there was a discovery of a faster algorithm to solve matrix multiplication. We then began to discuss when to use Dynamic Programming. When there are polynomial … Continue reading →

Poster: Cheng Cheng We were talking about the volunteers of CSED week and a new algo for matrix multiplication at the beginning of this class. We also spend a little time on using Dynamic Programming. Today, we focused on the … Continue reading →

For Lecture 36 we studied Weighted Interval Scheduling and the use of Dynamic Programming. A quick review of the lecture is followed with the formula: M[j] = max {Vj + M[p(j), M(j+10]}. Inputs provided: n jobs (Si, Ti, Vi) Outputs … Continue reading →

Started the class with a quick review from the class before thanksgiving. -Weighted Interval Scheduling- Input n jobs(Si, Ti, Vi) Output: schedule S s.t.no two jobs in S have a conflict Goal: Max <= i in S Vj Assume: jobs … Continue reading →

Moreover we did the same thing, which was done in last lecture about Weighted Interval scheduling by using Dynamic programming. Input: n jobs (si,ti,vi) Output: A schedule S s.t. no two jobs in S have a conflict We had to … Continue reading →