Lecture 41

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 the semester we mainly focused at the Algorithm Design stage; we learned several effective methods to approach a problem, namely:

• Greedy
• Divide & Conquer
• Dynamic Programming

Dr. Rudra then mentioned that if any one is interested in continuing their algorithm education, they may want to look at two courses: CSE-396 and CSE-431/531.
(As a side note, both are offered next semester (Spring 12′)).

Lecture 40 (12/7/2011)

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 set of problems that have a verifiable witness to an optimal solution in polynomial time.

Lecture 39 (12/05/2011)

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

Lecture 38

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

3) The sub-problems have an ordering that allows for an iterative solution

 

Lecture 38 (12/02/2011)

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 c_e of any weight (positive/negative).

• Dynamic programming was used to solve the problem.  There are 3 basic rules of thumb:

*There are many sub-problems

*Optimal solutions can be computed from solutions with sub-problem

*For each problem, there is a total ordering that gives way for an iterative solution.

• We also defined a recurrence relation with OPT(i,u) = cost of the shortest path from u to t with at most I edges.  The full relation is: 

Also of note, Homework 10 was uploaded and is due next Friday.

Lecture 37

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 number of sub-problems
• Optimal solutions can be computed from solutions to sub-problems
• There is an ordering among sub-problems that allows for iterative solutions

Lecture 37 (Nov.30)

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 Dynamic Program for shortest path.

Lecture 36

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 produced: A schedule (S) such that no two jobs in S conflict.

Lecture 36

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 are sorted by their finish time

Lecture 36

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 assume that jobs are sorted by their finish time and our goal was to find max Σi in S vj.