In problem 30-2, note that a Toeplitz matrix is constant along diagonals. Your algorithm for multiplying Toeplitz matrices may take longer than time n*log(n); time n^2*log(n) is fine here.
Group work allowed in accordance with policy.
Expanded Cumulative Syllabus
|Title||Math 416, Theory of Algorithms|
|Place||1068 East Hall|
|Prerequisites||Math 312 or 412 or EECS 203, and EECS 281 or permission|
|Text||Introduction to Algorithms, 2e Cormen, Leiserson, Rivest, and Stein (Follow links for errata.)|
|Instructor||Assistant Professor Martin Strauss|
|Office, central campus||3063 East Hall, MWF|
|Office, north campus||2238 EECS, TTh|
|martinjs .at. umich.edu|
|Office hours||by appointment and M,F 10-11 EH 3063; Thursday 1-2 2238 EECS. Check web page for exceptions.|
Past revisions of documents