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′)).

Continue reading

Posted in fall 2011 | Leave a comment

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.

Continue reading

Posted in fall 2011 | Leave a comment

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
Posted in fall 2011 | Leave a comment

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

  Continue reading

Posted in fall 2011 | Leave a comment

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 ce 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.

Continue reading

Posted in fall 2011 | Leave a comment

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

Continue reading

Posted in fall 2011 | Leave a comment

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.

Continue reading

Posted in fall 2011 | Leave a comment