Outline People Reading Grading Academics Homepage

MA 351 Fall '09 Syllabus

Course Outline*

Lecture Topic(s) Notes Book(s)
1. Aug 20 What are discrete models: Fibonacci's rabbits
DMM §1
2. Aug 25 Graphs and digraphs: basic set theoretic definitions
DMM §2
3. Aug 27 (Di)Graphs continued: toric mesh, hypercube Class notes
4. Sep 1 Paths, reachability, connectedness
DMM §2.2
5. Sep 3 Vertex basis, strong components
DMM §2.3
6. Sep 8 Matrix representation, transitive closure
DMM §2.4
7. Sep 10 Strong components via transitive closure

8. Sep 15 Return of homework 1; catch-up

9. Sep 17 Review for first exam

10. Sep 22 First Exam Counts 17.5%
11. Sep 24 Return of first exam; fair division and apportionment
Class notes (in pdf)
TA §3 and 4
12. Sep 29 Basic definition and examples of trees; rooting a tree
DMM §2.2, Ex 22
13. Oct 1 Expression trees, parenthesized strings Class notes; biography of Lukasiewicz.

14. Oct 6 Depth-first-seach trees; strongly connected orientation in a graph
DMM§3.3
Thurs-Fri, Oct 8-9 Fall Break, no class
15. Oct 13 Testing for cycles in a digraph by DFS
DMM §3.3
16. Oct 15 Expression grammars and parse trees Class notes

Fri, Oct 16, 11:59pm Last day to drop the course
17. Oct 20 Linearization of parse trees; MathML and XML


18. Oct 22 Lindenmeyer systems; fractals
Online notes
TA §12
19. Oct 27 More fractals
Definition of Mandelbrot and Julia sets

20. Oct 29 Chromatic number; planarity
History of 4 color theorem
DMM §3.6
21. Nov 3 Review for exam; catch-up


22. Nov 5 Second exam Counts 17.5%
23. Nov 10 Return of exam; Boolean expressions

Wed, Nov 11 Topic for term paper must be declared at 5pm
24. Nov 12 Boolean expressions and propositional calculus continued
Class notes

Mon, Nov 17 Approvals of topics for term papers by me are posted
25. Nov 17 Computing a k-element clique in a graph is as hard as factoring an integer
Class notes

26. Nov 19 Arrows axioms, impossibility
Arrow's autobio
DMM §7.2
27. Nov 24 Fair elections continued


Wednesday-Friday, Nov 25-27 Thanksgiving, no class
28. Dec 1 Markov chains
DMM §5
29. Dec 3 Markov chains continued; presentations start


Thurs. Dec 10, 09h00-12h00 and 14h00-17h00, NEW SAS 4201. Presentations continue
Presentation titles
9h00-9h15: Jenny,
9h15-9h30: Amy,
9h30-9h45: Leigh,
9h45-10h00: Taylor,

14h00-14h15: Chester,
14h15-14h30: Phillip,
14h30-14h45: Kate,
14h45-15h00: Manish,
10h00-10h15: Larry,
10h15-10h30: Michele,
10h30-10h45: Alicia,
10h45-11h00: Jacquelyn,

15h00-15h15: Meaghan,
15h15-15h30: Erin,
15h30-15h45: Evan,
15h45-16h00: Ryan S,
11h00-11h15: Lindsey,
11h15-11h30: Semi,
11h30-11h45: Cameron,
11h45-12h00: Joel,

16h00-16h15: Heather,
16h15-16h30: Walt,
16h30-16h45: Ryan D
16h45-17h00: ???,
12h00-12h15: Courtney,
12h15-12h30: ???



17h00-17h15: ???,
17h15-17h30: Henry.
* 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

We will use 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 web page listing all my courses' 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 five to six 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 on Dec. 3, 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.
Swine-flu notice: If you are ill with symptoms of H1N1 influenza (i.e., fever over 100, sore throat, cough, stuffy or runny nose, fatigue, headache, body aches, vomiting and diarrhea) please do not come to class. Instead, immediately contact your medical provider or Student Health Services (515-7107) for advice or to arrange an appointment.
If you are diagnosed with H1N1, please inform your instructor immediately. You will be required to be isolated away from class until at least 24 hours after you are free of fever (100 degrees), or signs of a fever, without the use of fever-reducing medications.

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-15 minute talk. I will give more details on what I expect from the presentation and the write-up during class.

If you need assistance in any way, please let me know (see also the University's policy).

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.

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