CSC 344
Homework 4
Assigned April 9, due April 23
You have 7 problems (including a programming problem with several
functions), and 14 days to do them. You do the arithmetic.
As you're doing these, think of which one you'd like to present in
class, and let me know as soon as you've decided. Solutions will be
presented in class April 23, 24, and 25.
Written problems from textbooks (to be done individually)
- CLRS 15.1-2 (demonstrate that a "greedy" algorithm doesn't work for
rod-cutting)
- CLRS 15.3-5 (demonstrate that a variant of the rod-cutting problem
doesn't have optimal substructure)
- CLRS 15.3-6 (currency changing and optimal substructure)
- CLRS 15.4-5 (longest increasing subsequence of a sequence of
numbers)
- CLRS 15.4-6 (an improvement on 15.4-5; extra
credit)
- CLRS 15-2 (longest palindromic subsequence)
- CLRS 15-4 (line breaking to minimize raggedness)
Programming problems (may be done in teams of two, if you wish)
Choose one of the following computational problems:
- rod-cutting (CLRS section 15.1)
- matrix-chain multiplication (CLRS section 15.2)
- longest common subsequence (CLRS section 15.4)
- longest palindromic subsequence (CLRS 15-2, above)
- weighted interval scheduling (from the "memoization and dynamic
programming" handout)
Implement three solutions in the programming language
of your choice, comparing running times
on a variety of input sizes:
- a straightforward recursive algorithm without memoization
- a memoized version of the same recursive algorithm
- a bottom-up table-filling algorithm
(As usual, provide several test cases with known right answers, and make
sure all three implementations pass these test cases.)
Do the empirical results match what you would have predicted?
Last modified:
Tue Apr 8 09:13:38 EDT 2014
Stephen Bloch / sbloch@adelphi.edu