Homework CSE202
Winter, 2008
Homework will be posted bi-weekly on Mondays
soon
after the previous homework was handed in.
-
Homework #1 :
Problems 1, 2,3,4,5,8 in Chapter 1
and Problem 1 in Chapter 2.
Solution 1
The counter example given in 1-8 is wrong. Here is a new counter example. Thanks to Priti for pointing it out.
Additional comments on Homework 1.
-
Homework #2 :
Problems 8,9,10,29,31 in Chapter 4.
Solution 2
-
Homework #3 :
Problems 2,3,5 in Chapter 5 and Problems 1,3,18,25 in Chapter 6.
Solution 3;
-
Homework #4 (the last set, due March 10):
Problems 3,12,13,16,18 in Chapter 7 and
Problem 1, 3 in Chapter 11.
Here is a worst case for Greedy Algorithm (Problem 11-1) given in the book. note
03/12/2008: A revised version of Solution 4. (A better solution to Problem 4 is added)
A bonus problem (also see problem 2 in the midterm exam)
Suppose that highways that connect n cities can be represented by
a connected graph G. Furthermore we assume that all edge costs are distinct.
There are two major cities A and B.
Design an algorithm for finding a connected network S such
that
(i) it contains a shortest path from A to B, and
(ii) the cost of S is minimum subject to (i).
Either give a polynomial algorithm, or prove this problem is NP-complete,
or show that any algorithm for this problem does not have polynomial running time.
Solution to Final. solution
Back to CSE202 page.