March 31, 2005

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 25, 2005

Avoiding premature cycles (due 3/30)

Answer the following questions:
  1. What is a premature cycle?
  2. 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.
  3. Sketch an algorithm and accompnying datastractures for detecting premature cycles as they are formed.
  4. Make sure you can detect premature cycles and that you can detect completed cycles too.
Solution

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)

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 i
solution

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 21, 2005

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 i
Show your work and turn in the reduced matrix and lower bound.

Posted by jones at 03:45 PM | Comments (0)

March 14, 2005

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

  1. In what order does the algorithm consider including objects in the knapsack?
  2. 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.
  3. 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)

March 04, 2005

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)

March 02, 2005

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)

February 23, 2005

Floyd's algorithm (due 2/28)

From the book, problems 8.17 and 8.18. Due 2/28. Note that in problem 8.18, you are adapting Floyd's algorithm to find a path if it exists, rather than find the shortest path. In this problem, you aren't given edge costs, so you don't care about finding the shortest path--just any old path will do.

solution
8.17 Yes. The algorithm works fine as long as there are no negative cycles. If there is a negative cycle, then a negative value is written to a diagonal.
8.18 The main modification is that don't add path lengths and use the min function. Instead, you just and together path existences and set matrix entries to 1 if a path exists.

Posted by jones at 03:16 PM | Comments (0)

Knapsack and Dynamic Programming (due 2/25)

From the textbook, problems 8.11 (hint: the equation on page 267 will be useful for you) and 8.12

Posted by jones at 03:12 PM | Comments (0)

February 15, 2005

Change of Variables (due 2/18)

The problems from section 3 of the handout on recurrences. Due 1 hour before class on Friday.

solution
Here is my solution to the first problem. Neither myself nor the other professor were able to solve the last one. I've posted this in good faith, but am sure that there's at least one error on it. i'll give everyone who points out an arithmetic error in my notes one extra point on their homework per error. No limit. Everyone who finds the same error gets a point. Have fun. :)

Posted by jones at 09:32 AM | Comments (0)

February 14, 2005

Nonhomogenous linear recurrances (due 2/16)

See the homework at the end of section 2 of the handout. Due 2/16. Remember not to stay stuck for more than 1/2 an hour on any one problem.

solution Typesetting of solutions curtesy of Andrew Harris.

1) Solve tn - 4(tn-1) + 3(tn-2) = 0.

tn - 4(tn-1) + 3(tn-2) = 0
replace tn with r^n...
r^n - 4r^(n-1) + 3*r^(n-2) = 0
write down characteristic function using theorem...
(r^n - 4r^(n-1) + 3*r^(n-2))/(r^n-2) = 0
factor ...
r^2 - 4r + 3 = 0
(r-3)(r-1) = 0
write down general solution...
tn = 1^n, 3^n
c1*1^n + c2*3^n = 0

use intial conditions to solve general solution for these initial conditions...
t0 = c1*1^0 + c2*3^0 = 0
t1 = c1*1^1 + c2*3^1 = 1

c1 + c2 = 0
c1 + 3*c2 = 1

c1 = 1/2
c2 = -1/2

and the final answer is...
----------------------------
tn = (1/2)*1^n + (-1/2)*3^n
----------------------------

2) Same idea, just more complicated. You may leave solutions with more than 2 unknowns in this form on an exam. I'll assume that you can solve for several unknowns, or that you will learn it in an algebra class...

tn - 3(tn-1) + 2(tn-2) = 1^n * n^2
(r^2 - 3r^2 + 2) (r-1)^3 = 0
(-2 (r^2 - 1)) (r-1)^3 = 0
(-2(r-1)(r+1)) (r-1)^3 = 0

tn = c1*(1)^n + c2*n*(1)^n + c3*n^2*(1)^n + c4*n^3*(1)^n + c5*(-1)^n
t0 = 0
t1 = 1
t2 = 7
t3 = 28
t4 = 86
t5 = 227

t0 = c1 + 0 + 0 + 0 +c5 = 0
t1 = c1 + c2 + c3 + c4 - c5 = 1
t2 = c1 + c2*2 + c3*4 + c4*8 + c5 = 7
t3 = c1 + c2*3 + c3*9 + c4*27 - c5 = 28
t4 = c1 + c2*4 + c3*16 + c4*64 + c5 = 86
t5 = c1 + c2*5 + c3*25 + c4*125 - c5 = 227

Posted by jones at 07:43 AM | Comments (0)

February 10, 2005

Linear homogeneous reccurance relations (due 2/14)

Do the homework in the recurrance relation notes (see full post for link to notes).

solution

1. first one is, others are not.

2. t_n = 2^n is indeed a solution for t_n - 5t_{n-1} + 6t_{n-2} = 0 because 2^n -5(2^{n-1}) +6t^{n-2) = 0 (details left for the reader).

3. Finally, we can verify that verify that c1(3^n) + c2(2^n) is a solution for t(n) - 5t(n-1) + 6t(n-2) = 0 for any constants c1 and c2. by doing the following (curtesy of Kawika Heftel). 

c1(3^n) + c2(2^n) - 5(c1(3^(n-1)) + c2(2^(n-1))) + 6(c1(3^(n-2)) + c2(2^(n-2))) = 0
c1(3^n) + c2(2^n) - 5c1(3^(n-1)) - 5c2(2^(n-1)) + 6c1(3^(n-2)) + 6c2(2^(n-2)) = 0
c1(3^n) - 5c1(3^(n-1)) + 6c1(3^(n-2)) + c2(2^n) - 5c2(2^(n-1)) + 6c2(2^(n-2)) = 0
c1((3^n) - 5(3^(n-1)) + 6(3^(n-2))) + c2((2^n) - 5(2^(n-1)) + 6(2^(n-2))) = 0
c1*3^n(1 - 5(3^-1) + 6(3^-2)) + c2*2^n(1 - 5(2^-1) + 6(2^-2)) = 0
c1*3^n(1 - 5/3 + 6/9) + c2*2^n(1 - 5/2 + 6/4) = 0
c1*3^n(1 - 5/3 + 2/3) + c2*2^n(1 - 5/2 + 3/2) = 0
c1*3^n(1 - 1) + c2*2^n(1 - 1) = 0
c1*3^n(0) + c2*2^n(0) = 0
0 = 0

Posted by jones at 08:15 PM | Comments (0)

February 04, 2005

Binary Search (due 2/4)

A few relatively easy questions about binary search. Due Friday 2/4.

1. Use the biniter (page 228) version of binary search to find 130 in the following list of numbers: 

 

1 5 9 20 50 130 200 210 230 410

Give the values of i and j for each trip through the while loop.

solution
I will use base-1 indexing so that 1 means the first entry, which in this case, is a 1.

iteration 0: 1 10
iteration 1: 1 6
iteration 2: 4 6
iteration 3: 5 6
iteration 4; 6 6

2. What does the algorithm return if you search for 120 in the above list?

solution

6 because array[6] is the first entry such that 120 <= array[6]. See page 226.

3. Give a modification of the algorithm that returns -1 if the search target is not in the list.

solution

before returning, check to see if T[i] = x. If not, return -1.

Posted by jones at 09:41 AM | Comments (0)

January 26, 2005

Minimum spanning trees (due 1/26)

1. Can a minimum spanning tree have a cycle? why or why not.
2. Suppose you are going to build a network connecting n computers. Suppose you know the cost to connect any pair of computers. Should you use Kruskal's algorithm or Prim's algorithm? Why?

solution
1. No. It wouldn't be a tree first of all. And second of all, if a "minimum spanning graph,er,tree" had a cycle, then you could drop at least one edge and get something that is more minimal and still spans every vertex in the graph. There's an assumption about edge costs being made here. What is it?

2. Prim's. See first full paragraph on page 198.

Posted by jones at 02:34 PM | Comments (2)

January 24, 2005

Parts of a Greedy Crossing the Desert Algorithm (due 1/24)

Answer the Five Demands of a Greedy Algorithm for the crossing the desert problem. Due 1/24 by email before 1pm.

The Five Demands of a Greedy Algorithm are:


  1. What is the candidate set for a given node? Meaning, which nodes can I choose the next node in my solution from?
  2. What is the solution function? Meaning, how do I know if I have created a solution and I can stop?
  3. What is the feasibility function? Meaning, how do I know if adding more candidates will eventually result in a solution?
  4. What is the selection function? Meaning, how do I chose the next candidate for inclusion?
  5. What is the objective function? Meaning, how do I measure the goodness of a solution?

Solution


  1. You may choose any node within capacity/3 from a node in the solution set if you need a round-trip caching-trip to build a cache or you may choose any node with capacity/2 from a node if you don't need a round-trip caching trip.
  2. You can stop when you have added the start node to the solution set. You also may stop if there are no more nodes to add or if you have exceeding 1 Million food on all paths.
  3. The feasibility function is whether or not you have exceeded 1 Million food on all paths.
  4. Select the node from which it is cheapest to build the cache at a node in the solution set.
  5. How much food does it take to get from start to finish?

Posted by jones at 03:02 PM | Comments (2)

January 21, 2005

Computing the cost (due 1/21)

Suppose you are at an oasis at (2,7) and want to travel to an oasis at (10,16). Your carrying capacity is 100 and you want to cache 105 food units at oasis (10,16). How much food do you need to build a cache of 105 food units at (10,16) assuming you start at oasis (2,7) and end at oasis (10,16)? Explain how you computed your result. Due 1/21.

solution:

You need to store 105 food at the end. The distance beween the oases is 

 

sqrt ((2-10)^2 + (7-16)^2) = 12.041
So you can carry with you an extra 
 

LastTripCacheCap = 100 - 2 * 12.041 = 75.918
food units to build the cache on your last trip to (10,16).

That means you will need 

 

CacheRoundTrips = max (0, ceil (105 - 75.918) / (100 - 3 * 12.041))) = 1
caching trip.
The cost of that caching trip is 
 

CacheRoundTripsCost = 2 * 12.041 + (105 - 75.918) = 53.164

food units. And a total of 
 

TotalCost = (100 - 12.041) + 43.164 = 141.123

food units to build a cache of 105 food at (10,16) and end a oasis (10,16)

Posted by jones at 08:40 AM | Comments (0)

January 19, 2005

Homework Grades

The first two homeworks have already been graded and placed on blackboard. If you have questions about your grade then send me an email and I'll try to explain why you got the score you did.

Also, I have not recieved submissions from many people. Please check to make sure that if you submitted homework it has been graded.

Posted by terry at 05:39 PM | Comments (0)

amortized analysis (due 1/19)

Use the accounting trick method to show that the count algorithm from the text page 113 has amortized linear running time. Assume that the counter is intially set to 0. Due January 19 before class via email.

solution
As in the textbook, add 2 tokens per call to count and remove 1 token for each trip through the while loop. Each trip, except for the last one, through the while loop flips a bit from 1 to 0. The last trip flips a bit from 0 to 1. This is like adding 1 to a binary number and rippling the carry bits until there are no more carry bits to ripple.

The crux of the homework is to show that each call either increases the number of tokens in the account by the increase in the number of bits set to 1 or decreases the number of tokens in the account by the decrease in the number of bits set to 1.

Posted by jones at 08:33 AM | Comments (0)

January 11, 2005

What does it take to show NP-completeness?

If you want to prove that problem X is NP-complete, what do you have to prove about problem X? Turn this in (the normal way, via email or on paper) by 2pm Wednesday January 13. If you skimed over Chapter 12 already, this will be quite easy. Solution has been posted below...

Solution: You must show that X is in NP. This can be done by either giving a non-deterministic Turing machine that solves X is polynomial time, or, by giving a deterministic algorithm that verifies a solution to X in polynomial time. One can prove that a problem is in NP if and only if there is a deterministic algorithm for verifying "guessed" solutions in polynomial time.

Second, you must show that every other problem in NP can be reduced to X in polynomial time. More precisely, you must find a function f such that: for all Y in NP, y is in Y iff f(y) is in X. And you must show that your function f can be computed in polynomial time on a deterministic turing machine.

The first problem that was shown to be NP complete is the satisfiability problem. Given a boolean formula, like (a /\ b \/ c) the satisfiability problem is the problem of determining whether or not values can be assigned to a, b and c such that the formula evaluates to true. Showing that satisfiability is NP complete required showing how to take any non-deterministic turing machine and reduce it to a satisfiability problem in polynomial time. Interestingly, this was done using a process that looks a lot like synthesizing a circuit from a program. In the end, the satisfiability problem looks like a circuit you might use to implement the program.

Posted by jones at 04:59 PM | Comments (0)

January 05, 2005

How hard is it to learn C#?

[Visual C# Developer Center] In which you spend no more than 3 hours writing a simple C# windows application that does simple data manipulation with a button and text box. The purpose is to see how hard it is for you to write in C#. Details in the full body of this post... Due Monday January 10th by 1pm

Eric Mercer (who teaches the other section) and I were trying to guess how hard it would be to have 312 students write in C# rather than C++. We think it wouldn't be that hard, but want to try an experiment to find out. Eric and I agree that using C# is much more natural and elegant in VisualStudio than using C++ in VisualStudio. But the problem is that 312 is supposed to be about algorithms not learning a new language. So if learning C# is going to be a big drag, then we'll stick with C++. Otherwise, if we can use C# without distracting from the purpose of the class then the projects will be a whole lot more fun.

So here's the homework...

Create and build a Visual C# application that


See the helpful post on using VisualStudio for tips.

Posted by jones at 01:51 PM | Comments (10)