| Outline | People | Reading | Grading | Academics | Homepage |
Course Outline* | |||||||
| Lecture | Topic(s) | Notes | Book(s) | ||||
|---|---|---|---|---|---|---|---|
| 1. Aug 20 | What are discrete models: Fibonacci's rabbits | DMM §1 | |||||
| 2. Aug 22 | Graphs and digraphs: basic set theoretic definitions | DMM §2 | |||||
| 3. Aug 27 | (Di)Graphs continued: toric mesh, hypercube | Class notes | |||||
| 4. Aug 29 | Paths, reachability, connectedness | DMM §2.2 | |||||
| Mon, Sep 2 | Labor Day, no class | ||||||
| 5. Sep 3 | Vertex basis, strong components | DMM §2.3 | |||||
| 6. Sep 5 | Matrix representation, transitive closure | DMM §2.4 | |||||
| 7. Sep 10 | Strong components via transitive closure |
transitive_closure.pdf,
transitive_closure.mw
|
|
||||
| 8. Sep 12 | Basic definition and examples of trees; rooting a tree |
|
DMM §2.2, Ex 22
|
||||
| Tue, Sep 17 | Wellness Day, no class | ||||||
| 9. Sep 19 | Catalan numbers; parenthesized strings |
wikipedia article on Catalan
|
|
||||
| 10. Sep 24 | Review for first exam |
|
|
||||
| 11. Thursday, Sep 26, 8am | First Exam online, posted and uploaded on Moodle | Counts 17.5% | |||||
| 12. Oct 1 | Expression trees; postfix notation |
Class notes;
biography of Lukasiewicz.
|
|
||||
| 13. Oct 3 | Return of first exam; fair division and apportionment |
Class notes (in pdf)
|
TA §3 and 4
|
||||
| 14. Oct 8 | Depth-first-seach trees; strongly connected orientation in a graph |
|
DMM§3.3
|
||||
| 15. Oct 10 | Testing for cycles in a digraph by DFS |
|
DMM §3.3
|
||||
| Mon-Tue, Oct 14-15 | Fall Break, no class | ||||||
| 16. Oct 17 | Expression grammars and parse trees |
Class notes
|
|
||||
| Thursday, Oct 17, 11:59pm | Last day to drop the course |
||||||
| 17. Oct 22 |
Linearization of parse trees;
MathML and XML
|
wikipedia article on MathML
|
|
||||
| 18. Oct 24 |
Lindenmeyer systems;
fractals
|
Online notes
|
TA §12
|
||||
| 19. Oct 29 |
More fractals
|
Definition
of Mandelbrot and Julia sets
|
|
||||
| 20. Oct 31 🎃 |
Chromatic number, planarity
|
7-Color Theorem on torus,
Kuratowski's Theorem
|
DMM §3.6
|
||||
| 21. Nov 5 | Review for exam; catch-up |
||||||
| 22. Thursday, Nov 7, 8am | Second exam online posted and uploaded on Moodle | Counts 17.5% | |||||
| 23. Nov 12 | Boolean expressions |
|
|||||
| Wednesday, Nov 13 | Topic for term paper must be declared at 5pm | ||||||
| 24. Nov 14 |
Return of exam;
Boolean expressions and propositional calculus continued
|
Class notes
|
|
||||
| Mon, Nov 18 | Approvals of topics for term papers by me are posted | ||||||
| 25. Nov 19 |
Computing a k-element clique
in a graph is as hard as factoring
an integer
|
Class notes
|
|
||||
| 26. Nov 21 |
Arrows axioms, impossibility
|
Arrow's autobio
|
DMM §7.2
|
||||
| 27. Nov 26 |
Fair elections continued
|
Borda count wikipedia page
|
|
||||
| Wednesday-Friday, Nov 27-29 🦃 | Thanksgiving, no class | ||||||
| 28. Dec 3 | Markov chains | DMM §5 | |||||
| Presentation titles | |||||||
| Fri Dec 6, 14h00-14h30, On Zoom, counts 10% |
Presentation
|
||||||
|
|||||||
| Mon Dec 9, 10h00-12h00 and 14h00-16h00, On Zoom counts 10% | Presentations | ||||||
|
|||||||
| Tue Dec 10, 10h00-12h00 and 14h00-16h00, On Zoom counts 10% | Presentations continue | ||||||
|
|||||||
| Tue Dec 10, 4pm | Term paper due to be uploaded to Moodle | Counts 10% | |||||
| Friday, December 13, 5pm | Fall grades due | ||||||
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
There will be five homework assignments of with the last two of lesser weight, two mid-semester examinations during the semester, and a term paper and a short presentation of it at the end of the semester.
I will check who attends class. You get credit by either A. signing the attendance sheet in class or B. go to Moodle and mark your attendance ``P'' (present). You have until 11:59pm on each day of each lecture to do so for that lecture. If you sign the attendance sheet, I will mark you "P". 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.
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.
Form of term paper:
The term paper is a 3-5 page summary and review (typed, single spaced),
with a title, author, page numbers and the citation to your selected
material (paper, book chapter, internet document). The citation
style can be any, like AMS alpha.
You can include figures, tables and displayed mathematical formulas.
Content of term paper:
Your text should not only be a transcript of your talk. You can
assume that your reader knows the material. After summarizing
the topic by pointing to the main new ideas in the material (1-2 pages),
your paper reviews the content and writing (1 page):
how well the ideas are described;
what is done well and what might have been done better.
You may also give your impression on what you have learned: eg, whether the
ideas are surprising.
Due date of term paper:
please uploaded on Moodle by Tue Dec 12 at 4pm.
Presentation: Your talk will be on Zoom at the
time reserved (see above). My Zoom meeting ID is a the top
of the Moodle class site. You should speak 10-12 minutes with 3 minutes for
questions and transition to the next talk.
In your presentation, you should assume that your audience
has undergraduate mathematical knowledge but has not
seen the material. Your talk should explain the modeling problem
and how it is solved. You may leave out some material.
Your explanation should give sufficient detail, like my
lectures in class.
My evaluation of your talk takes into account the manner of your speech,
but also the form of your document (proper title page and end page, etc.).
Please rehearse your talk with another
person for feedback and try to speak somewhat freely.
Due date of talk document (powerpoint, pdf, ...):
Please upload your talk document (powerpoint, pdf, ...) on Moodle before
your talk. You will screen-share your document on Zoom; if there is a
problem, I can screen-share your document and you can tell me when to
forward please uploaded on Moodle before your talk.
| Grade split up | |
| Accumulated homework grade | 40% |
| Term paper + presentation | 20% |
| First mid-semester exam | 17.5% |
| Second mid-semester exam | 17.5% |
| Class attendance | 5% |
| Course grade | 100% |
Grade distribution of Fall 2023.
If you need assistance in any way, please let me know (see also the University's policy).
Collaboration on homeworks: I expect every student to be their 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: The following penalties are given for (unexcused) late submissions:
©2010, 2016, 2017, 2018, 2022, 2023, 2024 Erich Kaltofen. Permission to use provided that copyright notice is not removed.