This course is officially a "guided reading" course for individual
grad students. However, since there are several students interested in
the topic, we'll do it as more of a seminar. We'll meet from 2:30-4:00
PM in room 116 Alumnae Hall, once a week on Monday, Wednesday, or Friday
depending on the schedules of the participants and the room.
The textbook
Introduction to Algorithms, by Cormen, Leiserson, and Rivest, is required.
(I haven't ordered it through the Adelphi bookstore, but you should be
able to find it through any good technical bookstore, or at
Amazon.com.)
There is no syllabus, but if you wish, you can look at the
syllabus for a graduate course I taught from the same textbook several
years ago.
Schedule
Friday, Jan. 30, 2:30
Initial meeting. Discussed algorithms vs. programs, counting
steps, improving algorithms vs. improving hardware. Analyzed efficiency
of insertion-sort algorithm.
Monday, Feb. 2, 2:30
Analyzed merge-sort algorithm, both sequential and parallel. Introduced
recurrence equations for algorithm analysis. Reviewed logs and summations
from calculus.
Wednesday, Feb. 11, 2:30
Formal definitions of asymptotic notation. Discuss summations and
recurrences.
Wednesday, Feb. 18, 3:30
Gus Petrakos's colloquium talk, "Complexity Driven Control Strategies
for Two-Person Games".
Friday, Feb. 20, 2:30
We planned to discuss chapters 3 and 4 of the textbook, but in fact
spent the time arguing about parallel sorting algorithms. Which is fine
with me, as long as it's within the subject of the course.
Colloquium talk by Dr. Bloch: "Computation and Oracles"
(a survey talk to provide background for Chris Pollett's talk)
Friday, April 17, 3:30
Colloquium talk by Chris Pollett of Boston University: "Bounded
Query Classes and Bounded Arithmetic"
Monday, April 20, 3:30
Discussed halting problem and computability
Monday, April 27, 3:30
Discussed parallel deterministic symmetry-breaking,
as well as Busy Beaver function & other topics
Wednesday, April 29, 3:30
Colloquium talk by Robert Thompson of the CUNY Graduate Center: "Rational
Homotopy Theory"
Monday, May 4, 3:30
Chap. 36: Complexity classes, P, NP, and completeness
Wednesday, May 6, 3:30
Colloquium talk by Ethan Berkove of West Point: "The Long Arm
of Calculus and Physics: the Mathematics of Space Shuttle Robots"
Monday, May 11, 3:30
Catch up and review
Friday, May 15, 3:30
Scheduled final exam, according to Directory of Classes.
We'll have a take-home final, aka Homework 3, due at this time.
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 2/20/98, due 3/6/98.
Read and think about all of the following problems. I've assigned
"points" to each (in parentheses after the problem number); write
up and turn in 15 points' worth.
1.2-3 (1), 1.3-6 (1), 1-2 (4), 1-3 (4)
2.1-4 (1), 2.2-2 (1), 2.2-5 (2), 2-4 (8), 2-6 (8)
3.1-3 (2), 3.1-7 (1), 3-1 (6)
Homework 2 assigned 3/6/98, due 3/23/98.
Read and think about all of the following problems. Write up and turn
in the ones with stars below.
4.1-5, 4.1-6
4.2-2*, 4.2-4*
4.3-2*
4-1, 4-2*, 4-7*
Homework 3 assigned 4/28/98, due 5/15/98.
Read and think about all of the following problems. I've assigned
"points" to each (in parentheses after the problem number); write
up and turn in 10 points' worth, including at least one problem from
each chapter.
29.1-4 (1), 29.2-7 (1), 29.2-8 (1), 29.2-9 (2), 29.4-5 (1), 29-2 (5)
30.1-1 (1), 30.1-3 (1), 30.1-4 (1), 30.1-5 (1), 30.2-3 (1), 30.2-4 (1),
30.5-3 (1), 30.5-5 (1), 30-1 (3), 30-3 (8)
Reading assignments
By Monday, May 4, you should have read at least chapters 1-5, 29, 30,
and 36 of the textbook.
You are visitor number
to this page since Feb. 1, 1998.