| Outline | People | Reading | Grading | Academics | Homepage |
Course Outline* | |||||||
| Lecture | Topic(s) | Notes | Book(s) | ||||
|---|---|---|---|---|---|---|---|
| 1. Aug 22 | What are discrete models: Fibonacci's rabbits | DMM §1 | |||||
| 2. Aug 24 | Graphs and digraphs: basic set theoretic definitions | DMM §2 | |||||
| 3. Aug 29 | (Di)Graphs continued: toric mesh, hypercube | Class notes | |||||
| 4. Aug 31 | Paths, reachability, connectedness | DMM §2.2 | |||||
| Mon, Sep 4 | Labor Day, no class | ||||||
| 5. Sep 5 | Vertex basis, strong components | DMM §2.3 | |||||
| 6. Sep 7 | Matrix representation, transitive closure | DMM §2.4 | |||||
| 7. Sep 12 | Strong components via transitive closure |
transitive_closure.pdf,
transitive_closure.mw
|
|
||||
| 8. Sep 14 | Basic definition and examples of trees; rooting a tree |
|
DMM §2.2, Ex 22
|
||||
| Tue, Sep 19 | Wellness Day, no class | ||||||
| 9. Sep 21 | Catalan numbers; parenthesized strings |
wikipedia article on Catalan
|
|
||||
| 10. Sep 26 | Review for first exam |
|
|
||||
| 11. Thursday, Sep 28, 8am | First Exam on Moodle | Counts 17.5% | |||||
| 12. Oct 3 | Return of first exam; fair division and apportionment |
Class notes (in pdf)
|
TA §3 and 4
|
||||
| 13. Oct 5 | Expression trees; postfix notation |
Class notes;
biography of Lukasiewicz.
|
|
||||
| Mon-Tue, Oct 9-10 | Fall Break, no class | ||||||
| 14. Oct 12 | Depth-first-seach trees; strongly connected orientation in a graph |
|
DMM§3.3
|
||||
| 15. Oct 17 | Testing for cycles in a digraph by DFS |
|
DMM §3.3
|
||||
| 16. Oct 19 | Expression grammars and parse trees |
Class notes
|
|
||||
| Thursday, Oct 19, 11:59pm | Last day to drop the course |
||||||
| 17. Oct 24 |
Linearization of parse trees;
MathML and XML
|
wikipedia article on MathML
|
|
||||
| 18. Oct 26 |
Lindenmeyer systems;
fractals
|
Online notes
|
TA §12
|
||||
| 19. Oct 31 🎃 |
More fractals
|
Definition
of Mandelbrot and Julia sets
|
|
||||
| 20. Nov 2 |
Chromatic number, planarity
|
|
DMM §3.6
|
||||
| 21. Nov 7 | Review for exam; catch-up |
||||||
| 22. Thursday, Nov 9, 8am | Second exam on Moodle | Counts 17.5% | |||||
| 23. Nov 14 | Boolean expressions |
|
|||||
| Wednesday, Nov 15 | Topic for term paper must be declared at 5pm | ||||||
| 24. Nov 16 |
Return of exam;
Boolean expressions and propositional calculus continued
|
Class notes
|
|
||||
| Mon, Nov 20 | Approvals of topics for term papers by me are posted | ||||||
| 25. Nov 21 |
Computing a k-element clique
in a graph is as hard as factoring
an integer
|
Class notes
|
|
||||
| Wednesday-Friday, Nov 22-24 🦃 | Thanksgiving, no class | ||||||
| 26. Nov 28 |
Arrows axioms, impossibility
|
Arrow's autobio
|
DMM §7.2
|
||||
| 27. Nov 30 |
Fair elections continued
|
Borda count wikipedia page
|
|
||||
| 28. Dec 5 | Markov chains | DMM §5 | |||||
| Presentation titles | |||||||
| Fri Dec 8, 14h00-14h15: Zoe M., on Zoom |
Presentation
|
||||||
| Mon Dec 11, 10h00-12h00 and 14h00-16h00, On Zoom | Presentations | ||||||
|
|||||||
| Tue Dec 12, 10h00-12h00 and 14h00-16h00, On zoom | Presentations continue | ||||||
|
|||||||
| Tue Dec 12, 4pm | Term paper due to be uploaded to Moodle | Counts 10% | |||||
| Friday, December 15, 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 2022.
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 Erich Kaltofen. Permission to use provided that copyright notice is not removed.