Mathematical Foundations

Fall 2000 (01-1)
CRN: 40483

Instructor: Dr. Stephen Hirtle

    Office: 736 IS Building
    Office Phone: 624-9434
    Office Hours: Wednesdays, 3:00 - 5:00pm, or by appt
GSA: Li Diao
    Office: A206 IS Building
    Office Hours: Tuesday, 1:00 - 4:00pm, or by appt
Class Meets: Thursday, 6:00-8:50pm, CHVRN 12B



Overview and Purpose

Basic concepts of theoretical mathematics needed to understand theoretical work in information science, with exception of probability and statistics. In particular, concepts from set theory, graph theory, combinatorics, logic, abstract algebra, topology, and mathematical analysis.

Course Requirements

Grading will be based on combination of homework, midterm and final exam. Exams will review material covered in the homework. The final exam will not be culmulative, beyond the inherent dependence of the material. All exams will be closed book. Particulars on the use study guides and calculators during the exams will be given two weeks before the midterm.

Point System

    [40%] Homeworks:
      There will be 10 homework assignments, each worth 10 points. The lowest two scores will be thrown out, leaving 8 scores for a maximum of 80 points.
    [30%] Midterm
      The midterm exam will be worth 60 points.

      Examination Difficulties. For those who had difficulty with the midterm examination and got a score of 50 or less points, you may score extra credits points by redoing the exam on separate answer sheets. The re-examination must be turned in by Nov 20 at 5pm. You will be eligible for a bonus of up to 50% of the missed points. That is to say, if on your original score was 40, you are eligible to gain up to 10 additional points to a maximum of 50 points by redoing the midterm exam. If your original score was 30, you eligible to gain up to 15 additional points to maximum of 45 points.

    [30%] Final Exam
      The final exam will be worth 60 points. See the Final Study Guide for notes that will distributed with the exam.

    Total Points
      There will be a total of 200 possible points. 180 points (90%) or higher will result in a grade in the set {A+, A, A-}. 160 points (80%) or higher will result in a grade in the set {A+, A, A-, B+, B, B-}. 140 points (70%) or higher will result in a grade in the set {A+, A, A-, B+, B, B-, C+, C, C-}.
Late Homework Policy. Homework assignments are due at the beginning of the class on the due date, since we will go over the homework at that time. Late homework assignments will be given half credit. Exceptions to this policy will be made only in extreme circumstances.

All homework assignments must be produced individually, in your own words. However, you are free to consult with other students on approaches and tactics used to solve problems, in order to facilitate your own learning. Any assistance that is designed to avoid learning the material is strongly discouraged, and may result in a failing grade on that week's assignment.

Required Readings

    Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 4th Edition ISBN 0-201-19912-2

Weekly Schedule

Week 1 *** August 31
Week 2 *** September 7
  • Principles of Counting (Grimaldi, Chapters 1, Sections 1.1-1.4)
  • Homework Set 1 due September 14

Week 3 *** September 14
  • Logic (Grimaldi, Chapters 2, Sections 2.1-2.3)
  • Homework Set 2 due September 28

*** NO CLASS September 21 -- Instructor out of town
Week 4 *** September 28
Week 5 *** October 5
  • Mathematical Induction (Chapter 4, Sections 4.1, 4.3)
  • Homework Set 4 due October 12

Week 6 *** October 12
  • Computational Complexity (Chapter 5, Section 5.1, 5.2, 5.3, 5.7, 5.8)
  • Homework Set 5 due October 19

Week 7 *** October 19
  • Languages and Finite State Machines (Chapter 6)
  • Review for Midterm
  • Homework Set 6

Week 8 *** October 26 MIDTERM EXAM
Week 9 *** November 2
  • Languages and Finite State Machines, continued (Chapter 6)
  • Homework Set 7 due November 9

Week 10 *** November 9
  • Introduction to Graph Theory (Chapter 11)
  • Homework Set 8 due November 16

Week 11 *** November 16
*** NO CLASS November 23 -- THANKSGIVING
Week 12 *** November 30
Week 13 *** December 7
  • Review for Exam and Catchup

Week 14 *** December 14 FINAL EXAM

Last Update: December 7, 2000