Outline People Reading Grading Academics Homepage

MA 351 Fall '99 Syllabus

Course Outline*

Lecture Topic(s) Notes Book(s)
1. Aug 17 What are discrete models: Fibonacci's rabbits
DMM §1
2. Aug 19 Graphs and digraphs: basic set theoretic definitions
DMM §2
3. Aug 24 (Di)Graphs continued: toric mesh, hypercube Class notes
4. Aug 26 Paths, reachability, connectedness
DMM §2.2
5. Aug 31 Vertex basis, strong components
DMM §2.3
6. Sep 2 Matrix representation, transitive closure
DMM §2.4
7. Sep 7 Return of homework 1; strong components via transitive closure

8. Sep 9 Basic definition and examples of trees; rooting of a tree
DMM §2.2, Ex 22
9. Sep 14 Return of homework 2; review for first exam

10. Sep 16 hurricane Floyd class cancelled
11. Sep 21 First exam Counts 17.5%
12. Sep 23 Expression trees and their linearization via parenthesized strings; depth first search trees Class notes
DMM §3.3
Mon, Sep 27 Last day to drop the course
13. Sep 28 Return of exam; strongly connected orientation of a graph
DMM §3.3
14. Sep 30 Testing for cycles in digraphs by DFS; expression grammars and parse trees Class notes
15. Oct 5 Linearization of parse trees; MathML and XML; Lindenmeyer systems Online notes

16. Oct 7 Fractals
TA §12; online notes
Mon-Tue, Oct 11-12 Columbus Day, no class
17. Oct 14 More fractals


18. Oct 19 Chromatic number

DMM §3.6
19. Oct 21 Planarity

DMM §3.6
20. Oct 26 Zero-knowledge proof for the Hamiltonian cycles problem
Class notes

21. Oct 28 Zero-knowledge proofs continued; Boolean expressions and propositional calculus
Class notes

22. Nov 2 Review for exam

23. Nov 4 Second exam Counts 17.5%
24. Nov 9 Return of exam; catch-up

25. Nov 11 Computing a k-element clique in a graph is as hard as factoring an integer
Class notes

26. Nov 16 Group decision making

DMM §7
27. Nov 18 Group decision making continued


Fri, Nov 19 Topic for term paper must be declared at 5pm
Mon, Nov 22 Approvals of topics for term papers by me are sent to you
28. Nov 23 Catch-up; visual cryptography

Thursday-Friday, Nov 25-26 Thanksgiving, no class
29. Nov 30 Markov chains
DMM §5
30. Dec 2 Markov chains continued; presentations begin (volunteers)

Thu, Dec 9, 08h00-11h00 Presentations continue
NEW Presentation titles
08h00-08h15: Terry P,
08h15-08h30: Robert P,
08h30-08h45: Robert W,
08h45-09h00: Mark M, 		09h00-09h15: Sean R,
09h15-09h30: Cuong N,
09h30-09h45: Bryan A,
09h45-10h00: Jynelle McC, 		10h00-10h15: BREAK,
10h15-10h30: Trung N,
10h30-10h45: Robyn J,
10h45-11h00: Sam S.
* This is a projected list and subject to amendment.

Instruction Personnel

For instructor, office hours, telephone numbers, email and physical address see the homepages of Erich Kaltofen.

Textbook and Online Notes

Professor Helminck ordered the book. I will cover topics that are not in the book. I will put another book on reserve in the Hill library: The syllabus above refers to chapters in these books. For topics in neither book, handouts will be provided.

On-line information: All information on courses that I teach (except individual grades) is now accessible via html browsers, which includes this syllabus. My courses' directory is at

You can also find information on courses that I have taught in the past, and examinations that I have given.

Grading and General Information

Grading will be done with plus/minus refinement.

There will be six to eight homework assignments of approximately equal weight, two mid-semester examinations during the semester, and a term paper and a short presentation of it at the end of the sememster.

I will check who attends class, including the paper presentations by your class mates Nov 30 and Dec 2. You will forfeit 5% of your grade if you miss 3 or more classes without a valid justification. I you miss a class because you are sick, etc., please let me know. I may require you to document your reason. If you need assistance in any way, please let me know (see also the University's policy).

For a term paper, you are asked to select and read a mathematical paper or a chapter/section in a book, whose topic is in discrete mathematical models. You can select a section in DMM that was not covered in class. The term paper is a 3-5 page summary (typed, single spaced). You will present the information to me in a 10 minute talk. I will give more details on what I expect from the presentation and the write-up during class.

I have not taught this course before, so there is no history of grades and there are not previous exams available.

Academic Standards

Examinations:The two examinations will be closed book-closed notes. However, you will be able to bring note sheets of paper with pertinent information to the examinations (1 for first exam and 2 for second exam).

Collaboration on homeworks: I expect every student to be his/her own writer. Therefore the only thing you can discuss with anyone is how you might go about solving a particular problem. You may use freely information that you retrieve from public (electronic) libraries or texts, but you must properly reference your source.

Late submissions: All programs must be submitted on time. The following penalties are given for (unexcused) late submissions:

Alleged cheating incidents: I will not decide any penalty myself, but refer all such cases to the proper judiciary procedures.

©1999 Erich Kaltofen. Permission to use provided that copyright notice is not removed.