COT 3100
Applications of Discrete Structures
Fall 1999, Section #7094X

Check back with this page frequently. Important course news, information, and lecture notes will be posted here.

Announcements:

You can view or download the archive of all announcements that have been sent to the class mailing list, as a Unix-standard format mail file. (If you're not using Unix, it should still be readable as plain text.) This may not always be perfectly up-to-date, so check your email as well.

Recent course news (newest items first):

Course info:

Instructor: Dr. Michael P. Frank. Office: CSE E442. Email: mpf@cise.ufl.edu. Office phone: 392-6888. Office hours: WF 5th period, F 8th period.

Teaching assistants: William Valella wvalella@cise.ufl.edu, office CSE E429, office hours MT 7th & 8th period.
Prajakta Ugrankar ugrankar@ufl.edu, office CSE E429, office hours W 7th & 8th, Thu. 6th & 7th.

Class hours and location: Section #7094X: MWF, 6th period (12:50 am to 1:40 pm) in Turlington room 2319.

Catalog description: Sets, relations, functions and cardinality. Propositional logic and applications. Predicate logic. Induction and recursion. Finite state machines, grammar and languages. Graphs and trees. Elements of groups, semigroups, lattices and boolean algebra. [Gray items may not actually be covered this semester.]

Pre-requisite: MAC 2311, Analytical Geometry and Calculus I (or MAC 2233 or MAC 3472).

Co-requisite: CIS 3020, Introduction to CIS.

Required textbook: Kenneth H. Rosen, Discrete Mathematics and its Applications, 4th ed., McGraw-Hill, 1999. Associated web site http://www.mhhe.com/rosen has additional information.

Optional textbooks: Student Solutions Guide for Discrete Mathematics and its Applications, 4th edition. Contains solutions to odd-numbered problems, in more detail than the solutions given in the primary text. Concrete Mathematics by Donald E. Knuth is another good textbook that covers number-related discrete math concepts in more depth. Also, for a very fun, whimsical, and Pulitzer-prize-winning introduction to many of the concepts in this course, I highly recommend the popular book Gödel, Escher, Bach: The Eternal Golden Braid, by Douglas Hofstadter, which can be found in paperback in most bookstores.

Grading:

The final grade for the course will be based on the following components, weighted as shown: Grading will be absolute, not relative or curved, and the point ranges are as follows: A+ = 95-100%. A = 90-95%. B+ = 85-90%. B = 80-85%. C+ = 75-80%. C = 70-75%. D+ = 65-70%. D = 60-65%. E = 0-60%.

Handouts

Student Information Form
This was handed out, filled out, and turned in during the first class meeting. If you didn't turn it in yet, print it out, fill it in, and bring it to the next class!
Daily Student Feedback Form
Fresh copies of this form will be handed out every day, for you to write anonymous constructive comments on during lecture, which you drop off at the end of the lecture.
TAs and Office Hours
Office hours and contact info for all 12 staff members from all 4 sections of the course.
General Homework Guidelines and Tips
Here are some general homework guidelines and tips, from the teaching assistants.
Lecture notes:
  • Lecture #1 - Basic propositional logic.
  • Lecture #2 - More propositional logic.
  • Orders of Growth
  • How to Write Good Proofs (PostScript format)
    Homework assignments:
  • Homework #1 (due 8/30) - Propositional logic.
  • Homework #2 (due 9/10) - Predicate logic and set theory.
  • Homework #3 (due 9/24) - Functions, summations, orders of growth.
  • Homework #4 (due 10/6) - Algorithms & complexity.
  • Homework #5 (due 10/11) - Basic number theory & Matrices.
  • Homework #6 (due 10/22) - Mathematical Proof Techniques.
  • Homework #7 (due 10/27) - Combinatorics.
  • Homework #8 (due 11/10) - Recurrence relations.
  • Homework #9 (due 11/19) - Relations.
  • Homework #10 (due 12/6) - Graphs.
  • Homework #XC (extra credit) (due 12/8) - More Proofs and Algorithms.
    Quizzes:
  • Quiz #1 (given 8/30) - Propositional logic.
  • Quiz #2 (given 9/13) - Predicate logic and set theory.
  • Quiz #3 (given 10/8) - Algorithms & Complexity.
    Sample Problems for Exam 1
    These are problems similar to the ones that will be on the exam. Here are example solutions.
    Exam 2 solutions (Postscript format).
    Download a postscript viewer for Windows.
    Proof Guidelines (Postscript format).
    Some extra guidelines for how to write good proofs.

    • Planned List of Topics:

    The following are the core book sections as suggested by Rosen, slightly regrouped, renamed, and reordered by myself. A tenative guess is given as to the number of lecture days that will be spent each topic. This list can be adjusted based on student needs... Depending on available time and student interest, more topics (or additional depth on these topics) may be interspersed with these as the course proceeds.
    1. Course introduction - 1 day
    2. Fundamentals of Logic (§1.1-1.3) - 3 days
    3. Sets (§1.4-1.5) - 2 days
    4. Functions (§1.6) - 1 day
    5. Summations (§1.7) - 1 day
    6. Order of Growth (§1.8) - 1 day
    7. Algorithms (§2.1) - 1 day
    8. Computational Complexity (§2.2) - 1 day
    9. Properties of Integers (§2.3) - 1 day
    10. Matrices (§2.6) - 2 days
    11. Formal proofs (§3.1-3.2) - 4 days
    12. Combinatorics (§4.1-4.3) - 7 days
    13. Probability (§4.4) - 1 day
    14. Recursion (§3.3) - 1 day
    15. Recurrence Equations (§5.1-5.2) - 2 days
    16. Relations (§6.1,6.3,6.5) - 5 days
    17. Graphs (§7.1-7.5) - 7 days
    18. Trees (§8.1) - 2 days

    Class Calendar: (Tentative, subject to change!)

    Week #Mon.Wed.Fri.
    Wk. #1 Aug. 23 - Lec. #1
    Intro, Logic§1.1
    HW1 out     		Aug. 25 - Lec. #2
    Logic §1.1     		Aug. 27 - Lec. #3
    Logic §1.2
    Wk. #2 Aug. 30 - Lec. #4
    HW1 due
    Quiz 1
    Logic §1.3     		Sep. 1 - Lec. #5
    Logic §1.3
    HW2 out     		Sep. 3 - Lec. #6
    Sets §1.4
    Wk. #3 Sep. 6 -
    Labor Day     		Sep. 8 - Lec. #7
    Sets §1.5     		Sep. 10 - Lec. #8
    HW2 due
    Funcs §1.6
    Wk. #4 Sep. 13 - Lec. #9
    Quiz 2
    Funcs §1.6
    HW3 out     		Sep. 15 - Lec. #10
    Canceled -
    Hurricane Floyd!         		Sep. 17 - Lec. #11
    Funcs §1.6
    Sums §1.7
    Wk. #5 Sep. 20 - Lec. #12
    Sums §1.7     		Sep. 22 - Lec. #13
    HW2+Qz2 ret'd
    Growth §1.8     		Sep. 24 - Lec. #14
    Growth §1.8
    Wk. #6 Sep. 27 - Lec. #15
    HW3 due
    Algs §2.1     		Sep. 29 -
    Exam #1
    Ch. 1     		Oct. 1 - Lec. #16
    HW4 (2.1+2.2) out
    Algs §2.1
    Cmpxty §2.2
    Wk. #7 Oct. 4 - Lec. #17
    Ints §2.3     		Oct. 6 - Lec. #18
    HW4 (2.1+2.2) due
    HW5 (2.3+2.6) out
    Ints §2.3
    Mats §2.6     		Oct. 8 - Lec. #19
    Quiz 3
    Mats §2.6
    Wk. #8 Oct. 11 - Lec. #20
    HW5 (2.3+2.6) due
    Proofs §3.1     		Oct. 13 - Lec. #21
    Proofs §3.1
    Proofs §3.2     		Oct. 15 - Lec. #22
    Quiz 4 (2.3+2.6)
    HW6 (3.1-3.3) out
    Proofs §3.2
    Wk. #9 Oct. 18 - Lec. #23
    Recur §3.3
    Comb §4.1     		Oct. 20 - Lec. #24
    HW7 (4.1-4.3) out
    Comb §4.1
    Comb §4.2     		Oct. 22 - Lec. #25
    HW6 (3.1-3.3) due
    Comb §4.3
    Wk. #10 Oct. 25 - Lec. #26
    Quiz 5 (3.1-3.3)
    HW8 (5.1+5.2) out
    Comb §4.3     		Oct. 27 - Lec. #27
    HW7 (4.1-4.3) due
    Prob §4.4     		Oct. 29 - Lec. #28
    Quiz 6 (4.1-4.3)
    Recur §5.1
    (TA lecture)
    Wk. #11 Nov. 1 - Lec. #29
    Recur §5.2     		Nov. 3 -
    Exam #2
    Chs. 2-4     		Nov. 5 -
    Homecoming
    Wk. #12 Nov. 8 - Lec. #30
    Recur §5.2     		Nov. 10 - Lec. #31
    HW8 (5.1+5.2) due
    HW9 (Ch. 6) out
    Rels §6.1     		Nov. 12 - Lec. #32
    Quiz 7 (5.1+5.2)
    Rels §6.1
    Wk. #13 Nov. 15 - Lec. #33
    Rels §6.3
    Rels §6.5     		Nov. 17 - Lec. #34
    Rels §6.5
    Graphs §7.1     		Nov. 19 - Lec. #35
    HW9 (Ch. 6) due
    Graphs §7.2
    Wk. #14 Nov. 22 - Lec. #36
    Quiz 8 (Ch. 6)
    HW10 (Ch. 7) out
    Graphs §7.2     		Nov. 24 - Lec. #37
    Graphs §7.3     		Nov. 26 -
    Thanksgiving
    Wk. #15 Nov. 29 - Lec. #38
    HW-XC out
    Proofs & Algs
    Extra Lecture     		Dec. 1 - Lec. #39
    Quiz 9 (7.1-7.3)
    Graphs §7.4     		Dec. 3 - Lec. #40
    Graphs §7.5
    Wk. #16 Dec. 6 - Lec. #41
    HW10 (Ch. 7) due
    XC exam
    Trees §8.1     		Dec. 8 - Lec. #42
    HW-XC due
    Review Sess.
    Course Evals
    Wk. #17 Dec. 15 -
    5:30-7:30 pm
    Final Exam
    Chs. 1-8

    Additional information:

    Fellow instructor Tim Davis already has quite a bit of info about his section of COT 3100 (section #1098X), including a syllabus, on-line. For my section, much of this information (except for the lecture time, place, instructor, and TAs) will still apply.

    Fellow instructor Meera Sitharam also has extensive material on-line for her section of COT 3100 as well. We may borrow good policies and ideas from either of these other sites for use in our own section as the semester progresses.

    Mark Schmalz, who taught a section of COT 3100 last Spring, has a web page from that class in which he has written extensive lecture notes for many of the topics in the course. You may find these to be helpful study aids.

    Michael Frank 8/20/99