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:
- 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′)).
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.
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
Blog post by Raghu N. Seshadri
- 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.
Also of note, Homework 10 was uploaded and is due next Friday.
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
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.