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 27 | Graphs and digraphs: basic set theoretic definitions | DMM §2 | |||||
3. Aug 29 | (Di)Graphs continued: toric mesh, hypercube | Class notes | |||||
Mon, Sep 2 | Labor Day, no class | ||||||
4. Sep 3 | Paths, reachability, connectedness | DMM §2.2 | |||||
5. Sep 5 | Vertex basis, strong components | DMM §2.3 | |||||
6. Sep 10 | Matrix representation, transitive closure | DMM §2.4 | |||||
7. Sep 12 | Strong components via transitive closure |
|
|
||||
8. Sep 17 |
Chromatic number, planarity
|
|
DMM §3.6
|
||||
9. Sep 19 | Fair division and apportionment |
Class notes (in pdf)
|
TA §3 and 4
|
||||
10. Sep 24 | Review for first exam |
|
|
||||
11. Thur, Sep 26 | First Exam | Counts 17.5% | |||||
12. Oct 1 | Basic definition and examples of trees; rooting a tree |
|
DMM §2.2, Ex 22
|
||||
13. Oct 3 | Return of first exam; Catalan numbers |
wikipedia article on Catalan
|
|
||||
14. Oct 8 | Expression trees, parenthesized strings |
Class notes;
biography of Lukasiewicz.
|
|
||||
Thurs-Fri, Oct 10-11 | Fall Break, no class | ||||||
15. Oct 15 | Depth-first-seach trees; strongly connected orientation in a graph |
|
DMM§3.3
|
||||
16. Oct 17 | Testing for cycles in a digraph by DFS |
|
DMM §3.3
|
||||
Fri, Oct 18, 11:59pm | Last day to drop the course |
||||||
17. Oct 22 | Expression grammars and parse trees |
Class notes
|
|
||||
18. Oct 24 |
Linearization of parse trees;
MathML and XML
|
|
|
||||
19. Oct 29 |
Lindenmeyer systems;
fractals
|
Online notes
|
TA §12
|
||||
20. Oct 31 🎃 |
More fractals
|
Definition
of Mandelbrot and Julia sets
|
|
||||
21. Nov 5 | Review for exam; catch-up |
||||||
22. Thur, Nov 7 | Second exam | Counts 17.5% | |||||
23. Nov 12 | Return of exam; Boolean expressions |
|
|||||
Wed, Nov 13 | Topic for term paper must be declared at 5pm | ||||||
24. Nov 14 |
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
|
|
|
||||
Wednesday-Friday, Nov 27-29 🦃 | Thanksgiving, no class | ||||||
28. Dec 3 | Markov chains | DMM §5 | |||||
29. Dec 5 |
Presentations start:
Helena B.,
Ghin C.,
Breanna G.,
Jimmy Z.,
Abbey E.
|
||||||
Wed Dec 11, 10h00-12h00 and 14h00-16h00, Location NEW SAS 4201 | Presentations continue | ||||||
Presentation titles
|
|||||||
Thur Dec 12, 10h00-12h00 and 14h00-16h00, Location NEW SAS 4201 | Presentations continue | ||||||
|
|||||||
Friday, December 20, 11:59am | 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 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.
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.
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 2018.
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 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:
©2010, 2016, 2017, 2018 Erich Kaltofen. Permission to use provided that copyright notice is not removed.