« February 2005 | Main | April 2005 »
March 31, 2005
[Homework] Solutions posted
The solutions to the TSP premature cycle detection and edge inclusion/exclusion homeworks have been posted.
Posted by jones at 08:53 AM | Comments (0)
March 30, 2005
[Projects] Scheduling for presentations
April 6 Rob and Doyle and Chris Hathaway and
April 8 Kawika and Andrew Harris and Ben Booth and Brad
Posted by jones at 03:54 PM | Comments (0)
[Projects] More about improvement presentations
YOu have to write a presentation and describe your favorite improvement. That presentation should go about 10 minutes and you should allow a few minutes for questions. The TAs will use the following form to evaluate your presentation:
- Content [60 points]: Could you understand what they did for their improvement? Did you know what their improvement was supposed to accomplish? Did they present enough data so that you could conclude that their improvement did or did not accomplish its objective? Did their conclusion about their improvement match the data they presented? Did they have any idea why their improvement did or did not work ? Did they have any ideas for what to do next to either improve their improvement or try something else?
- Visual Presentation [20 points]: Were the slides readable? Was the data well-presented? Were the slides tacky and distracting? Did they look at their feet or the keyboard the whole time?
- Oral presentation [20 points]: Did they speak clearly? Did they vary their tone and speed?
For 312, you will probably want to use an outline that goes something like this. Variations are fine, you know the scoring criteria so have fun if you want to do something completely different.
- INtroduction. What problem does your improvement work on? (1 slide)
- What is your improvement supposed to improve about your solution to that problem? How do you know that this is a problem? (1 or 2 slides)
- What is your improvement? (1 or 2 slides) This would be a good place to talk about how you implemented your improvement, but be careful not spend forever talking about coding.
- Say wehter or not you think your improvement accomplished anything and then present some data that supports your conclusions. (2-3 slides)
- Close by saying why your improvement did or did not work and what you would change next if you had enough time. (1 slide).
I've posted a guide to writing presentations. It is written mostly for graduate students presenting research, but the ideas apply to presenting improvements. You'll find that its pretty opinionated. I can be pretty dogmatic when I want to be, and I did. So try not to get caught up in that.
Posted by jones at 02:35 PM | Comments (0)
[Lectures] Notes about TSP Algorithms
What to put in each node?
- Reduced matrix
- lower bound
- included edges
- excluded edges
How to generate children?
- one child for from “here” to every destination
o probably not a good idea. Queue gets too big too fast.
- Pick “here” and generate a child for the n closest cities. N children per node.
- Include or exclude an edge to generate 2 children
How to traverse the graph?
- best first search using a pruning function.
A bounding function
- the matrix reduction algorithm from Wednesday.
Way to generate initial solutions
- pick the smallest edge from A to X then smallest from X to next city (other than A) and so forth. Then return to A.
- pick a permutation of the city list and try that.
- Its probably worth doing more than 1 of these trials, but not worth doing all the permutations. You have to find the sweet spot. Well, in your improvement you can find it if that’s what you want to do.
The algorithm.
class node
members
matrix matrix, bound bound, vector solution,
Boolean optimal
etc;
methods
reduce // reduce the matrix and increase the
bound accordingly.
NextEdgeToIncludeAndExclude
// pick an edge that maximizes exclude child’s bound or some other strategy.
excludeCityEdge (i,j)
// excludes the edge from i to j, re-reduces the matrix and increases the bound as needed.
Algorithm tsp-bb (matrix M)
: (vector v, int cost, bool optimal)
priorityQueue of nodes pq;
// set up my bssf.
node bssf; // best solution so far.
(bssf.vector, bssf.bound) =
min (several different solutions);
bssf.matrix = M;
bssf.optimal = false;
// build initial node.
inode.matrix = M;
inode.bound = 0;
inode.reduce();
pq.push (inode);
while (!pq.empty) {
if (time has expired)
then bssf.optimal = false;
break;
curnode = pq.pop ();
(i,j) = curnode.NextCityEdgeToIncludeAndExclude();
node include = new node(curnode);
node exclude = new node(curnode);
exclude.excludeCityEdge (i,j);
include.includeCityEdge (i,j);
if (include.isASolution()
&& include.bound < bssf.bound)
updateBSSF (include); // set optimal = true.
pq.prune();
// the order here matters, and you can use an else
// to simplify the code.
if (include.bound < bssf.bound)
pq.push (include);
if (exclude.bound < bssf.bound)
pq.push (exclude);
}
// return the bssf.
return bssf
Class node (int,int) NextCityEdgeToIncludeAndExclude ()
// one strategy is to minimize bound on include-child.
For each (i,j) such that M[i,j] = 0
M’ = copy of array M
Set row i = infinity and column j = infinity
Set M’[j,i] = infinity
Difference = Reduce (M’) – bound
// another method…
If M[k,m] = 0 then
Difference = min (row m) + min (column k)
Excluding M[k,m].
//Just a sketch. Have fun and design your // own.
Let i,j = M[i,j] so that we get the include and exlcude bounds we want.
// make sure there are no premature cycles.
Use an array called “to” that tracks where you go “to” from city i.
Write a for-loop to see if city i is connected to itself in less than n steps where n = # of cities.
If i,j causes a premature them replace M[i,j} with infinity, reduce and try again.
Posted by jones at 11:50 AM | Comments (0)
[Projects] An Access Database with more TSP Examples
A kind student has created an access database with more TSP examples
Warning: some lines have a preceeding space on their row definition and others do not.
Posted by jones at 10:37 AM | Comments (0)
March 28, 2005
[Projects] More TSP Problems
We have created an archive with more tsp problems. They aren't in an access database, you get to do that tedious step yourself.
If you do put them in the database you are invited to send that database to me and I will distribute it.
Posted by jones at 10:41 AM | Comments (0)
[Schedule] The plan for the rest of the semester
We will wrap up the TSP algorithm today. Wednesday (3/30) we will do the minimax algorithm and start linear programing if time permits. Friday (4/1) we will go into linear programing in earnest and stick with that through the last day of class.
Linear programing is not in the textbook. A handout will be made available before 4/1. Linear programing is an important topic because it gives you another way to think about optimization problems and ties together most of hte ideas from the whole course.
The last project is to code up the simplex method. In linear programming problems, half the "fun" is coming up with the formulation of the problem as a linear program. So this project will be a little different. We will give you a constraint satisfaction problem and you will formulate it as a linear program, convert it to slack form, implement the simplex method and use your implementation to solve the slack form of your linear program. That will simplify the project a little while focusing on the main ideas.
Posted by jones at 08:52 AM | Comments (0)
March 25, 2005
[Lectures] Putting the TSP Algorithm Together
This is the algorithm so far. We will continue fleshing out the details on Monday.
What to put in each node?
- Reduced matrix
- lower bound
- included edges
- excluded edges
How to generate children?
- one child for from “here” to every destination
o probably not a good idea. Queue gets too big too fast.
- Pick “here” and generate a child for the n closest cities. N children
per node.
- Include or exclude an edge to generate 2 children
How to traverse the graph?
- best first search using a pruning function.
A bounding function
- the matrix reduction algorithm from Wednesday.
Way to generate initial solutions
- pick the smallest edge from A to X then smallest from X to next city
(other than A) and so forth. Then return to A.
- pick a permutation of the city list and try that.
- Its probably worth doing more than 1 of these trials, but not worth
doing all the permutations. You have to find the sweet spot. Well, in
your improvement you can find it if that’s what you want to do.
The algorithm.
class node
members
matrix matrix, bound bound, vector solution,
Boolean optimal
etc;
methods
reduce // reduce the matrix and increase the
bound accordingly.
NextEdgeToIncludeAndExclude
// pick an edge that maximizes exclude child’s bound or some other strategy.
excludeCityEdge (i,j)
// excludes the edge from i to j, re-reduces the matrix and increases the
bound as needed.
Algorithm tsp-bb (matrix M)
: (vector v, int cost, bool optimal)
priorityQueue of nodes pq;
// set up my bssf.
node bssf; // best solution so far.
(bssf.vector, bssf.bound) =
min (several different solutions);
bssf.matrix = M;
bssf.optimal = false;
// build initial node.
inode.matrix = M;
inode.bound = 0;
inode.reduce();
pq.push (inode);
while (!pq.empty) {
curnode = pq.pop ();
(i,j) = curnode.NextCityEdgeToIncludeAndExclude();
node include = new node(curnode);
node exclude = new node(curnode);
exclude.excludeCityEdge (i,j);
include.includeCityEdge (i,j);
if (include.isASolution()
&& include.bound < bssf.bound)
updateBSSF (include);
pq.prune();
// the order here matters, and you can use an else
// to simplify the code.
if (include.bound < bssf.bound)
pq.push (include);
if (exclude.bound < bssf.bound)
pq.push (exclude);
}
Posted by jones at 07:50 PM | Comments (0)
[Homework] Avoiding premature cycles (due 3/30)
Answer the following questions:- What is a premature cycle?
- Are premature cycles possible in the include/exclude formulation of the problem? That's the algorithm that picks an edge to include and exclude resulting in two new nodes.
- Sketch an algorithm and accompnying datastractures for detecting premature cycles as they are formed.
- Make sure you can detect premature cycles and that you can detect completed cycles too.
The other questions are pretty straightfoward, here's a premature cycle detection algorithm...
array to of int[n]. // an array that lives in each nod.e
is edge (x,y) ok to add?
int here;
here = y; // note that I didn't modify the "to" array.
for (i = 1 ; i < n; i++) // since I started at y (rather than x) I only go up to n-1 in a solution.
here = to[here];
if (here == x) then return false // not ok to add x,y.
return true // it is ok to add x,y.
Posted by jones at 03:45 PM | Comments (0)
[Homework] Which edge to include/exclude? (updated, due 3/28 or 3/30)
We didn't cover all of the ideas behind this homework yet. But I would expect that you can do this on your own. Either way. Its due either monday or Wednesday. Your call.
Consider the following reduced matrix...
Changed 3/28 at 8am to have 6 rows and to actually be reduced Which edge would you include and exclude (to create to new nodes) so that you ...
Maximize the bound on the "exclude" child?
Minimize the bound on the "include" child? I changed it to minimize on 3/29. If you did maximize, that's ok, but minimize is what you really want.
i 9 3 0 8 3 0 i 0 3 0 2 5 4 i 8 3 0 9 0 3 i 5 7 7 6 0 8 i 4 1 4 7 0 8 isolution
Maximize the "exclude" child is the edge at row 4 column 2.
Minimize the "include" child is row row 3 column 6 or row 5 column 3. Both result in no increase to the lower bound.
Posted by jones at 03:44 PM | Comments (0)
March 23, 2005
[Exams] Final exam is in the testing center 4/16 through 4/21
It turns out that 312 section 003 meets the requirements for putting an exam in the testing center. Its already scheduled and that's what we will do.
Posted by jones at 02:55 PM | Comments (0)
March 22, 2005
[Exams] Exam 2 Stats and Curve
The high score on exam 2 was 86/90 so I added 4 points to everyone's grades. With that 4 points, the summary statisitcs on exam 2 are:
Average 81/90
Std Deviation 10.2
variance 104.4
Posted by jones at 02:33 PM | Comments (0)
March 21, 2005
[Homework] Reduce this TSP Matrix (due 3/25)
[TSP Project homepage, including an example of the reduction algorithm] Apply the reduction algorithm to get a lower bound on the optimal solution to the following TSP problem:i 4 3 2 5 i 9 4 1 2 i 3 9 3 2 iShow your work and turn in the reduced matrix and lower bound.
Posted by jones at 03:45 PM | Comments (0)
March 14, 2005
[Announcements] Kawika Heftel, live in concert on April 16!
Kawika Heftel has a gig lined up at Sweet's barbequeue on April 16. That's in Provo kind of by the DI and hospital dow n at the end of Bulldog Avenue. There's a $2.00 cover charge, which is a lot less than its going to cost to hear Kawika live after he gets famous. See the freedb for a list of songs on Kawika's CD
Posted by jones at 03:46 PM | Comments (0)
[Lectures] General form for branch and bound algorithms
Branch and bound algorithms look roughly like this. You may find this helpful for your homework and general learning.
bssf = approximate some solutions and pick the best one
push initial node onto pQueue
while (pQueue is not empty)
node = pQueue.pop()
for child = all feasible children of node.children
child.bound = compute bound on this node.
if (child.isASolution and child is better than bssf)
prune the tail of pQueue to eliminate newly non-promising nodes
if (child.bound is potentially better than bssf)
pQueue.push (child)
return bssf
Notes: be careful about what it means for a solution to be "better" than the bssf and what it means for a child to be "potentially better" than the bssf.
Posted by jones at 03:36 PM | Comments (0)
[Homework] Knapsack branch and bound (due 3/18)
A few questions related to solving the knapsack problem using branch and bound. This is discussed in section 9.7.2 of the textbook but the authors say "we leave the details to the reader". Well, here we go on some details...
Consider the following knapsack problem as we go along:
capacity, W = 100
item 1 2 3 4 5
weight 10 20 30 40 50
value 20 30 66 40 60
- In what order does the algorithm consider including objects in the knapsack?
- If only item 3 has been included in the knapsack, then what is the upper bound on the profit that can be obtain with just item 3 in the knapack? Use the estimation function suggested by the equation on page 316 of the book.
- Draw the exploration tree for this branch and bound algorithm on this problem. Indicate the order in which nodes are expanded and indicate which nodes are "pruned" during the search.
Posted by jones at 03:11 PM | Comments (0)
[Projects] No self assessment for magic squares project (in section 003 at least)
So all you have to do is code it up and get in under a second.
Posted by jones at 03:10 PM | Comments (0)
[Projects] TSP with Branch and Bound project (due 4/1)
[TSP with Branch and Bound Homepage] The homepage includes a description of the database, some documentation for the algorithm and a sample database. This is not an easy lab. Its probably more similar to crossing the desert than drill core alignment. The entire algorithm is covered in the documentation and in class. Its a tricky algorithm to understand but really isn't that hard to code up once you get your head around it. Start early and learn the algorithm before you start coding. Due April 1.
Posted by jones at 12:54 PM | Comments (1)
March 09, 2005
[Announcements] BYU iOscars 2005
Quinn Taylor passed this contest along to me. Some of you more artsy people might have a shot at winning this... [BYU iOscars '05 :: Make a movie, win an iPod!]
Posted by jones at 02:47 PM | Comments (0)
March 04, 2005
[Homework] The match game, problem 9.7 (due 3/9)
Solve homework problem 9.7. Due Wednesday 3/9.
Posted by jones at 03:04 PM | Comments (0)
[Exams] Exam 2 study list
The second exam will run wednesday through Saturday (assuming I can get it changed again, which shouldn't be a big deal). If I were taking the exam, I would study the following topics:
- Master theorem (equation 7.1). While you all are experts in solving recurrences, you still need to know how to use the old standby.
- The prinicple of optimality and how it applies to dynamic programming.
- Understand the dynamic programing algorithms we talked about in class
- Understand why the knapsack dynamic programming algorithm has pseudopolynomial complexity and integer multiplication does not.
- Memory functions
- Know how to translate a symetric two player game into a graph for win/loose analysis.
- Study solutions to homework and study problems.
Same rules as last time: 2 hour time limit, one page of notes.
Posted by jones at 02:59 PM | Comments (0)
March 02, 2005
[Homework] Complexity of matrix multipliation algorithm (due 3/4)
from the book: problem 8.23 page 280. Due Friday 3/2
Posted by jones at 02:33 PM | Comments (0)