Math 182 - Discrete Structures, Spring 2014 |
Instructor: Ge (Frank) Xia
Lectures:
MWF 9:00 - 9:50 am, AEC 500
Office: AEC 506
Phone: 610-330-5415
Office hours: MWF 9:50-10:30 am
|
[Announcements] [Textbook]
[Grading] [Schedule] [Overview]
Course Description
An introduction to discrete structures and algorithms and some mathematical tools and methods of reasoning that aid in their development and analysis. Topics include: sets, counting, algorithms, mathematical induction, probability, relations, graphs, and trees.
Course Objectives : At the end of the semester you should:
- understand basic definitions and properties of sets and functions,
- understand the definition of algorithms, and be able to evaluate the growth of simple functions,
- be able to construct proofs using mathematical induction,
- be able to use the basic counting methods, including permutations and combinations,
- understand the fundamentals of discrete probability theory,
including the definition of discrete probability, conditional probability, and Bayes' Theorem,
- understand basic definitions and properties of relations, and
- understand basic definitions and properties of graphs and trees.
Prerequisite: CS I (104, 105, or 106) and Math161 (or 165).
- Ronald. L. Graham, Donald E. Knuth, Oren Patashnik. Concrete mathematics : a foundation for computer sciencem, 2nd ed.
The grades will be based on a combination of assignments and exams. The distribution of the course grade is shown below:
- Homework assignments and quizzes -- 30% total
- Midterm exam 1 -- 20%
- Midterm exam 2 -- 20%
- Final exam -- 30% (comprehensive)
All assignments are to be submitted on Moodle at 11:55pm on the due date. Each student is allowed a one-time lateness of up to 48 hours. Beyond this, no exceptions will be made on late or missing assignments unless the student has an allowed excuse. An allowed excuse is an approved Dean's excuse or the instructor's permission. The final letter grades will be assigned based on criteria specified in the Student Handbook.
Academic Honesty
All students must adhere to the college academic honesty policy in the Student Handbook. Discussion of concepts with others is encouraged, but the work you submit
in this course must be your own work, unless otherwise instructed. Copying is strictly forbidden.
The Student Handbook of Lafayette College has a section on
Principles of Intellectual Honesty that defines academic dishonesty to
include:
- Use of other persons' writings without proper
acknowledgment,
- Use of reference material without properly crediting
sources used,
- Use of other students' work, with or without revision,
- Collaboration beyond the limits established by the
instructor,
- Submission of the same work in more than one course
A student who commits academic dishonesty is subject to Disciplinary
actions including suspension or expulsion.
Attendance
Students are expected to attend classes. If a quiz is given in a class and a student is absent without an allowed excuse, they will receive a zero for the quiz. An allowed excuse is an approved Dean's excuse or the instructor's prior permission.
Changes will be made according to the progress of the course.
| |
| Sunday |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
Saturday |
Week 1
|
Ch 1.1
Propositional Logic
|
|
Ch 1.3
Propositional Equivalence
|
|
Ch 1.4
Predicates and Quantifiers
|
|
Week 2 |
Ch 2.1
Sets |
|
Ch 2.2
Set Operations |
|
Ch 2.3
Functions
Deadline for Changing
Courses
|
|
Week 3
|
Ch 2.4
Sequences and Summations
|
|
Ch 2.4
Cardinality of Sets
|
|
Ch 3.1, 3.2
Algorithms and Growth of Functions |
|
Week 4
|
Ch 3.2
Growth of Functions |
|
Ch 5.1
Mathematical Induction
|
|
Ch 5.1
Mathematical Induction |
|
Week 5
|
Ch 5.2
Strong Induction and Well-Ordering
|
|
Ch 5.2
Strong Induction and Well-Ordering
|
|
Ch 6.1
The Basics of Counting
|
|
Week 6 |
Ch 6.1
The Basics of Counting |
|
Ch 6.2
The Pigon Hole Principle
|
|
Ch 6.3
Permutations and Combinations |
|
Week 7
|
Ch 6.3
Permutations and Combinations
|
|
Ch 7.1
Probability |
|
Exam I |
|
|
Spring Break
|
--
|
--
|
-- |
Spring Break
|
|
Week 8
|
Ch 7.2
Probability Theory |
|
Ch 7.3
Bayes' Theorem
|
|
Ch 7.3
Bayes' Theorem
Midterm grades due |
|
Week 9
|
Ch 7.3
Bayes' Theorem |
|
Ch 7.4
Expected Value and Variances
|
|
Ch 7.4
Expected Value and Variances |
|
Week 10
|
Ch 9.1
Relations and Their Properties
|
|
Ch 9.3
Representing Relations
|
|
Ch 9.3
Representing Relations |
|
Week 11
|
Ch 10.1
Graphs
|
|
Ch 10.1
Graphs
|
|
Ch 10.1
Graphs and Graph Models
Last Day to Withdraw from Courses |
|
Week 12
|
Ch 10.1
Graphs and Graph Models
|
|
Exam 2 |
|
Ch 10.2
Graph Terminology and Special Types of Graphs |
|
Week 13
|
Ch 10.3
Representing Graphs and Graph Isomorphism
|
|
Ch 11.1
Trees
|
|
Ch 11.1
Trees
|
|
Week 14 |
Ch 11.3
Tree Traversal
|
|
Ch 10.3
Tree Traversal
|
|
Review
Last Day of Classes |
|
|
Final Exam period begins |
|
|
|
|
|
|
Final Exam period ends
|
Final Grades Due to Registrar by 12
Noon
|
|
|
|
|
|
|
|
|
|
|
|
|