CSC 344
Algorithms and Complexity
Spring, 1997
This course meets from 9:25-10:40 AM TTh in room 116 Alumnae Hall.
Note room change! We are not meeting in
room 39 in the basement of the Business Building.
The textbook
Fundamentals of Algorithmics, by Gilles Brassard and Paul
Bratley, is required.
The
syllabus
is available in LaTeX,
DVI,
Postscript, and
HTML.
An
updated schedule will
contain
the latest updates to homework due dates, lecture topics, etc.
Please check the schedule regularly and keep up on the assigned reading!
Homework Assignments
I shall assign several homework assignments during the semester, mostly
"paper assignments" (i.e. not programming), although they may
be turned in on paper or by email.
- Homework 1, assigned 30 Jan, due 18 Feb
- Read problems
1.13,1.17,1.21,1.24,1.27,1.28,1.29,1.30,1.34,1.46.
Work and turn in any four of them, including at least
one induction proof.
Read problems
2.2,2.5,2.6,2.7,2.8,2.11,2.19,2.20.
Work and turn in any three of them.
- Homework 2, assigned 21 Feb, due 18 Mar
- Read problems
3.2,3.5,3.6,3.7,3.11,3.14,3.15,3.17,3.21,3.28.
Work and turn in any four of them.
Read problems
4.1,4.2,4.5,4.6,4.7,4.8,4.10,4.11,4.17,4.21.
Work and turn in any four of them.
- Homework 3, assigned 3 April, due 17 April
- Do 50 points' worth of problems from the following:
- 5 point (easy) problems
- 5.1,5.6,5.18,5.20,5.33,5.34,5.35,5.38
- 10 point (moderate) problems
- 5.2,5.3,5.4,5.10,5.11,5.12,5.13,5.17,5.19,5.21,5.22,5.23,5.25,5.26,
5.27,5.28,5.29,5.30,5.31,5.32,5.36,5.37
- 15 point (hard) problems
- 5.5, 5.14, 5.15, 5.16, 5.24
- Homework 4, assigned 17 April, due 1 May
- Read problems
6.2, 6.3, 6.7, 6.8, 6.9, 6.10, 6.14, 6.15, 6.18, 6.19, 6.21(a), 6.21(b).
Work and turn in any six of them, including at least
one proof. (Yes, problem 6.21 counts as two.)
Reading assignments
By Thursday, 17 April, you should have read pages 1-180 of the textbook.
I'll discuss section 5.7 in detail in class on the 17th; you can read
section 5.8 for yourselves; and I'll try to discuss section 5.9 in
class.
You are visitor number
to this page
since Jan. 13, 1997.
Last modified:
Stephen Bloch / sbloch@boethius.adelphi.edu