Design and Analysis of Algorithms Seminar

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.

- 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.
- Wednesday, Feb. 25, 3:30
- Robert Payton's colloquium talk, White Monkeys, Black Swan and Spotted Deer: Closing the Envelope in Japan.
- Friday, Feb. 27
- Discuss chapter 3 (summations) of the textbook, as well as parallel algorithms for compressing sparse arrays.
- Friday, Mar. 6, 3:30
- Discuss chapter 4 of the textbook: recurrence relations.
- Monday, Mar. 9, 3:30
- Discuss chapter 5 of the textbook: basic combinatorics
- Wednesday, Mar. 11, 3:30
- Robert Bradley's colloquium talk on Self-Avoiding Walks, Polymers and Knots.
- Monday, Mar. 16 - Friday, Mar. 20
- Adelphi Spring Break -- no class
- Monday, Mar. 23, 3:30
- Chap. 29: Gates, circuit size and depth, and addition
- Wednesday, Mar. 25, 3:30
- Colloquium, "Using the TI-83 Graphing Calculators in the Mathematics Classroom", by Steve Okolica and Georgette MacRina of the Wheatley School.
- Monday, Mar. 30, 3:30
- Chap. 29: Multiplication circuits, circuit-based complexity classes
- Wednesday, April 1, 3:30
- Colloquium talk by Gus Petrakos: "More on Strategies for Two-player Games"
- Friday, April 10, 3:30
- Chap. 30: PRAM algorithms, pointer jumping, complexity classes
- Monday, April 13, 3:30
- 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.

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)

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.

Last modified:

Stephen Bloch / sbloch@boethius.adelphi.edu