Algorithms Assignments, Spring 2019

General Assignment Information

HW1

HW2

Problems based on Appendix B or 04A_Recurrence.html: Find the Θ order of T. Assume integer division in the recurrence relation. Recall logb bk = k.

HW3

Also these problems not in the book:

HW4

HW5

HW6

HW7

critPath.png

HW8

M-kruskal.png

HW9

HW10

  • 11.3: 5

  • 11.3: 6

  • 11.3: 7a (Note that the assumption made in 7a is to reduce your work, but checking legality is required in general to confirm a solution),

  • 11.3: - 9ac (Show polynomial reducibility in both directions for clique and independent set; you can skip the middle one)

  • 11.3: 11[10]

  • 11.3: 12a[11a]

  • Problem W

    1. A Hamiltonian Path is a path that visits each vertex once, but being a path rather than a cycle, it starts and ends at different vertices. Show that the undirected Hamiltonian path decision problem is polynomially reducible to the directed one.
    2. Based on your reduction from part a, and the knowledge that the directed problem in NP complete, could you conclude that the undirected problem is NP complete?
    3. Same question as b. with except with the italicized directed and undirected swapped.

    W Hint: The mapping should be easy.