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 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
|
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 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.
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% |
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:
©2009 Erich Kaltofen. Permission to use provided that copyright notice is not removed.