image University of Washington Computer Science & Engineering
  CSE 421,  Su '07:  Assignment #1, Due: Wednesday, 6/27, 2007
  CSE Home   About Us    Search    Contact Info 

Reading:

Chapters 1, 2 and start 3. (Section 2.5 should be review of data structures material; you should skim it, reading unfamiliar parts more carefully.)

Important Note:

For all homework assignments this quarter, it is a violation of my academic integrity policy for you to search for, read, or use solutions to these or similar problems written by others. You may discuss these problems with other students in this class, but you must write your solutions on your own.

Problems:

  1. Prove by induction that, for all n > 1, 1/(n+1) + 1/(n+2) + ... + 1/(2n) > 13/24

  2. Given an undirected graph G=(V,E), a matching in G is a subset M of edges no two of which have a vertex in common; a perfect matching is a matching that includes all vertices. Give an inductive construction of a family of graphs Gn, n≥1, with 2n nodes and n2 edges such that Gn has exactly one perfect matching.

  3. Chapter 1, Page 22, Problem 1.

  4. Chapter 1, Page 22, Problem 2.

  5. Chapter 1, Page 23, Problem 4. In this problem and the next, write a paragraph explaining why your algorithm is correct. (This doesn't have to be very formal, but do try to make it convincing.) See the faq page for some discussion about the level of detail expected when I say "give an algorithm.")

  6. Chapter 1, Page 25, Problem 6.

  7. Chapter 2, Page 67, Problem 2.

  8. Chapter 2, Page 67, Problem 3.

  9. Chapter 2, Page 67, Problem 5.

  10. Chapter 2, Page 69, Problem 8.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX