June 19, 2006
Homework Keys 13-15
Here are the keys for homeworks 13 - 15
Homework 13 RTF
Homework 14 RTF
Homework 15 RTF
Posted by ryanShepherd at 05:39 PM | Comments (0)
June 16, 2006
Homework 15
The very last homework! Congratulations on enduring to the end.
1. Problem 11.4
2. Suppose you have a parallel algorithm that runs in O(T(n,p)) time for T(n,p) = log n for a problem of size n using p processors. Suppose that the best known sequential algorithm solves problems of size n in O(S(n)) time for S(n) = n log n. What is the speedup for this algorithm and what is the efficiency? Did this algorithm achieve linear speedup?
Due Monday, June 19, 2006
Posted by tonglaga at 04:06 PM | Comments (0)
June 14, 2006
Homework 14
Homework in Section 3.3 of the Linear Programming Handout
due June 16, 2006
Posted by tonglaga at 03:45 PM | Comments (0)
June 12, 2006
Keys for homeworks 8 - 12
Here are the keys for homeworks 8 - 12
Homework 8 RTF
Homework 9 RTF
Homework 10 RTF
Homework 11 RTF
Homework 12 RTF
Posted by ryanShepherd at 05:25 PM | Comments (0)
Homework 13
Homework in Section 1.1 of the Linear Programming Handout
Homework in Section 2.3 of the Linear Programming Handout
Due June 14, 2006
Posted by tonglaga at 04:10 PM | Comments (0)
June 09, 2006
Homework 12
1. R&N Problem 4.1: Trace the operation of A* search applied to the problem of getting to Bucharest from Lugoj using the straight-line distance heuristic. That is, show the sequence of nodes that the algorithm will consider and the f, g, and h score for each node. Here is the map of Romania.
The following problem from the Russell and Norvig book sketches an interesting approach to solving the TSP using branch and bound. Do not do this problem, but use the idea in question 2 below.
The traveling salesperson problem (TSP) can be solved via the minimum spanning tree (MST) heuristic, which is used to estimate the cost of completing a tour, given that a partial tour has already been constructed. The MST cost of a set of cities is the smallest sum of the link costs of any tree that connects all the cities. (a) Show how this heuristic can be derived from a relaxed version of the TSP. (b) Show that the MST heuristic dominates straight-line distance. (c) Write a problem generator for instances of the TSP where cities are represented by random points in the unit square. (d) Find an efficient algorithm in the literature for constructing the MST, and use it with an admissible search algorithm to solve instances of the TSP
2. Which MST algorithm would you recommend for addressing problem part (d) above and why? As your search progresses and the reduced cost matrix for a given search state gets filled with infinities (i.e., as the set of remaining edges shrinks), would you change your recommendation for an MST algorithm? Why?
3. Give two ways in which a probabilistic algorithm differs from a deterministic algorithm.
4. State the definitions of the following:
a. A Monte Carlo algorithm
b. A Numerical probabilistic algorithm
c. A Las Vegas algorithm
5. Why is it easier to "amplify" the stochastic advantage of a biased Monte Carlo algorithm more quickly than for an unbiased MC algorithm?
Due Monday, June 12.
Posted by tonglaga at 04:13 PM | Comments (0)
June 07, 2006
Homework 11
Due Friday, June 9.
Consider the following reduced cost matrix M, in which M[a,b] = i means that the path from a to b has been excluded from
consideration (by setting its cost to infinity) with the given lower bound lb:
M =
0 4 6 0 i 2
i i i i i i
3 0 0 4 i 7
5 2 6 0 i 0
4 i 0 8 i 2
0 3 1 2 i 0
lb = 25
1. Suppose your algorithm includes the edge from city 5 to 3 next (this edge has cost 0 relative to the current lower bound lb=25).
Give a new reduced cost matrix and new lower bound that have the following properties:
a. All edges that can now be excluded from consideration have had their cost replaced by i.
b. The resulting matrix has been reduced.
c. The new lower bound includes the impact of the reduction.
2. Take a look at the new reduced cost matrix. Which edge would you decide to include in a solution next? Justify your answer
(Note that I can think of 3 different ways to pick this edge and each of those picking methods have a good justification. And, there
might be more good methods that I haven't thought of)
-----------------------------------
On the third day we talk about edge selection algorithms and put the whole algorithm together. Putting the whole algorithm
together means generating nodes from other nodes, managing the priority queue, the structure of the search tree and the best
solution so far and deciding when to terminate the algorithms. You can structure the search tree two different ways. The structure
of the search tree influences the design of the edge picking algorithm. The first way is to pick an edge then generate children by
including that edge and by excluding that edge. For this tree structure, one might pick an edge by maximizing the difference
between the included edge child and the excluded edge child or one might pick the edge that maximizes the bound on the
exclude-edge child. In this tree formulation, one needs to be careful to not create a cycle prematurely (because the edges are
picked willy nilly).
The second way is to generate n children per node where each child is generated by including one of the edges that leave city i
where i is the depth of the tree. The nice thing about this formulation is that one does not create cycles prematurely but the
downside is that on many problems this problem formulation will result in excessively priority queues. The edge picking algorithm
for this formulation is quite simple: you just pick them all. Of course, bright students will say, well, why don't I just pick the best one
leaving city i instead of all of them? That's not a bad idea, but keep in mind that later on you might need to go back and pick a new
edge leaving city i so don't throw the parent node away quite yet.
Posted by tonglaga at 04:30 PM | Comments (0)
June 05, 2006
homework 10
1. Give 1 similarity and 2 differences between branch-and-bound and backtracking.
2. 9.53 part a only.
3. Problem 9.55. Explain your answer.
4. Question about the Travelling Salesperson Problem (TSP). This question will help you start building your understanding of this problem.
In a TSP solution, how many times does the final route leave a particular city? How many times does the final route enter a given city? Give both an upper and a lower bound.
5. consider the following instance of the TSP with cost matrix M given below.
M =
0 4 9 2 5
2 0 7 5 1
8 3 0 6 4
1 4 9 0 3
9 2 7 6 0
(in which it costs 4 to get from city 1 to city 2, and in general it costs M[i,j] to get from city i to city j)
1. Reduce all rows and columns of the cost matrix. Give both the reduced cost matrix and the resulting lower bound on the cost of
the optimal tour.
2. Generate a quick, correct but not necessarily optimal solution to this TSP instance. List the cities in the resulting tour and give
the cost of that tour. This tour cost will be an upper bound on the optimal tour cost.
Due Wed, June 7.
Posted by tonglaga at 04:08 PM | Comments (0)
June 02, 2006
Homework 9
There are a lot of homework problems today, but most of them are easy and help you understand better today's material.
9.1, 9.6, 9.22, 9.23, 9.9, 9.14, 9.31, 9.42
knapsack : solve an instance of the type of knapsack problem described in section 9.6.1 involving three types of objects, whose weights are respectively 2, 3, and 4 units, and whose values are 3, 5, and 6. The knapsack can carry a maximum of 8 units of weight. Draw the implicit tree explored by backtracking to find the optimal load (the one that maximized the value of the included objects, while respecting the capacity (weight) constraint (similar to Figure 9.12).
due Monday, June 5.
Posted by tonglaga at 04:11 PM | Comments (2)
May 31, 2006
Homework 8
1. Section 3.2, first question, on page 10 of the Recurrence Relations notes
2. Consider figure 8.4 for filling a knapsack using dynamic programming. Let's use a new set of objects whose weights are 1, 2, and 4 units, and whose values are 1, 7, and 15, respectively. If we can carry a maximum of 12 units of weight, construct a new table like 8.4 to determine the optimal load in a knapsack (using DP) with these objects. Analyze the new table to determine which objects will be included in the optimal load.
3. 8.13 (on extracting equivalent optimal solutions to 0/1 knapsack from the DP table)
4. 8.17 page 279
Due Friday, June 2.
Posted by tonglaga at 11:29 AM | Comments (0)
May 30, 2006
Homework keys 4, 5, 6, and 7
Here are the keys for homeworks 4 - 7
Homework 4 RTF
Homework 5 RTF
Homework 6 RTF
Homework 7 RTF
Posted by ryanShepherd at 03:53 PM | Comments (0)
May 24, 2006
Homework 7
Homework #7 due Friday, May 26
Homework problems from the recurrence relations handout - all the problems from both parts 1 and 2 (parts 1.2 and 2.3 respectively).
Posted by ryanShepherd at 04:22 PM | Comments (0)
May 15, 2006
Homework 6
Homework #7: Due Wed May 17 (More intense)
7.10 (write down how you became convinced)
7.12 (be sure that your proof of the correct big-O bound is solid)
7.14
7.15
7.23
Posted by tonglaga at 04:15 PM | Comments (2)
May 12, 2006
Homework 5
1. Problem 6.18
1. Problem 7.2
2. Problem 7.7
3. Use equation 7.1 to give a bound on the running time of a divide and conquer algorithm that splits a problem into pieces that are 1/5 the size of the original problem, solves 4 of the pieces and requires ?(n^2) to recombine subproblems at each level. Suppose that you could recombine the subproblems using an ?(n) algorithm if you solved all 5 subproblems rather than only 4. Which algorithm has a better bound?
Due Monday, May 15
Posted by tonglaga at 04:11 PM | Comments (0)
May 10, 2006
Homework 3 key
Homework 3 RTF
Posted by ryanShepherd at 05:08 PM | Comments (0)
May 09, 2006
Homework Keys
Here are the keys for Homeworks 1 & 2
Homework 1 RTF
Homework 2 RTF
Posted by ryanShepherd at 02:58 PM | Comments (0)
Homework 4
Question 1 Simulate each step of Dijkstra's algorithm, and turn in a table similar to the table in the middle of page 199, on the following directed graph consisting of 5 vertices labeled 1,2,3,4,5 and the following 5 edges
1 to 2 is connected by an edge with cost 6
1 to 3 is connected by an edge with cost 4
2 to 4 is connected by an edge with cost 3
1 to 4 is connected by an edge with cost 9
1 to 5 is connected by an edge with cost 20
4 to 5 is connected by an edge with cost 6
Question 2 Implementing Dijkstra's algorithm requires finding the smallest element in a set (line 8 of pseudocode on page 199) and removing an element from a set (line 9). Discuss the datastructures and algorithms that you might use to implement these operations in the intelligent scissors project. In your discussion, address the efficiency implications of your decisions.
due Friday, May 10.
Posted by tonglaga at 12:03 PM | Comments (0)
May 08, 2006
Homework 3
1. Problem 6.1 page 214
2. how that the greedy algorithm for making change in Section 6.1 will or will not always make correct change for the Nephite coinage system given in Alma 11.
3. get really comfortable with VS 2005.
i. Read through the highlights of set of documents linked from this page at MSDN: Introduction to C#
ii. Work through this "Hello, World" example at MSDN: Hello, World
iii. Extend your "Hello, World" example:
For this assignment, please simply submit a screenshot of your final sorting GUI and indicate which sorting algorithm you implemented.
Read sections 6.3 and 6.4 on Spanning Trees and Shortest Paths.
due Wed, May 10.
Posted by tonglaga at 04:30 PM | Comments (0)
May 05, 2006
homework 2
Consider the following algorithm for getting a drink of water in an apartment in which n roomates share n cups.
Procedure get-drink (dirty: int, clean: int, n:int)
if (clean = 0) then
for (j = 1 to n) do wash-cup(j);
dirty = 0;
clean = n;
drink-water();
return (dirty+1, clean-1,n)
Question 1 Suppose that rather than using the get-drink algorithm above, the roomates decided to implement a "you use it, then you wash it" policy instead. Under policy, one would get a drink of water then immediately wash the cup so that all cups were clean at all times. Compare and contrast the amount of time required to get a drink of water under both policies. How does this related to the design of algorithms and data structures?
Question 2 Problem 4.19 page 142
Question 3 Problem 12.35
Question 4 problem 12.49
due Monday, May 8.
Posted by tonglaga at 10:47 AM | Comments (0)
May 03, 2006
Homework
Homework is 1.21, 2.2, 2.3, 2.4, 3.5, 3.20
Due Friday, May 5.
Posted by tonglaga at 03:52 PM | Comments (2)