CompSci 260  Fundamentals of the Design and Analysis of Algorithms  Winter, 2017 (Dillencourt)
The required problems are due at the start of class.
When you turn them in, please be srue they are neat and legible.
Typesetting is preferred.
The Reader, at his discretion, may decide that a homework assignment
is unreadable and not grade it.
The nonrecommended additional problems, while highly recommended,
are optional.
Some of the problems are straightforward. Others are more challenging.
They are intended to help you learn the material by applying it.
This works best if you make a serious attempt to solve them yourself.
If instead of trying to solve them yourself you prefer to ignore them,
obtain solutions from a friend, or look them up on the internet,
that is your choice.
 Homework 1: posted January 9:
 No required problems
 Recommended problems: Chapter 1, Problems 18
 Homework 2: posted January 17.
Required problems are due Tuesday, January 24 at the start of class.
 Required Problems: Chapter 2, Problems 4,5,6
 Note: On Problem 5, in all parts, f and g should be positive.
 Recommended Additional Problems: Chapter 2, Problems 1,2,3,8
 Homework 3: posted January 25.
Required problems are due Tuesday, January 31 at the start of class.
 Required Problems: Chapter 3, Problems 4,6,9
 Recommended Additional Problems: Chapter 3, Problems 3,5,7,10,12
 Homework 4: posted February 1.
Required problems are due Tuesday, February 7 at the start of class.
 Required Problems: Chapter 4, Problems 9,11,17
 Recommended Additional Problems: Chapter 4, Problems 3,4,8,27
 Homework 5: posted February 14.
Required problems are due Tuesday, February 21at the start of class.
 Required Problems:
 Recommended Additional Problems: Chapter 5, Problems 1 , 5
 Homework 6: posted February 23:
 No required problems
 Recommended problems: Chapter 6, Problems 1, 2, 3, 4, 5, 6, 9
 Homework 7: posted March 2.
Required problems are due Tuesday, March 7 at the start of class.
 Required Problems:
 Chapter 6, Problems 9,11
 Chapter 7, Problems 1,2,3
 Recommended Additional Problems:
 Chapter 6, Problem 19
 Chapter 7, Problems 4,5,8
 Homework 8: posted March 14:
 No required problems
 Recommended problems: Chapter 8, Problems 17
 Additional recommended problem added March 18.
(Solution will be posted March 20):

Define the UHC to be the problem of determining whether an undirected
graph has a Hamiltonian cycle.
Define the UHP to be the problem of determining whether an undirected
graph has a Hamiltonian path.
Show that the UHC problem is polynomially reducible to the UHP.
Last modified: March 18, 2017