ECE665: Algorithms

Instructor: Ramgopal Mettu

Time: TuTh 2:30-3:45, Place: Eng Lab 305

Homework Assignments

All homework is due at the beginning of class; late submissions will not be accepted.

Homework 1

Due: Feb 13

Problem 1.4
Problem 1.7
Problem 2.4
Problem 2.5
Problem 2.6
Problem 2.8

Homework 2

Due: Feb 22

Problem 3.2
Problem 3.3
Problem 3.6
Problem 3.7
Problem 3.8

Homework 3

Due: Mar 1

Problem 4.1
Problem 4.2
Problem 4.8
Problem 4.21
Problem 4.24

Homework 4

Due: Mar 14, 5pm (drop off in my mailbox or under my door)

Problem 5.1
Problem 5.4
Problem 5.6
Problem 5.7
An addendum to the homework was announced in class.

Homework 5

Due: Apr 5

For this homework, you are to rework your test. Each problem (including the extra credit) will count 5 points. If you have gotten a particular problem completely correct, provide an alternate proof/argument, or make your existing answer more concise.

Homework 6

Due: Apr 19

Using induction, prove the correctness of the recurrences (that define an optimal solution) given in class for Segmented Least Squares, Knapsack and Sequence Alignment. These correspond to statements 6.7, 6.11, 6.15.
Problem 6.1
Problem 6.3
Problem 6.9
Problem 6.12

Homework 7

Due: May 15

Problem 7.5
Problem 7.12
Problem 7.13
Show that Independent Set is polynomial-time reducible to Set Packing.
Problem 8.5
Problem 8.6
Problem 11.2, part a) only.
Problem 11.3