Math 245-24 Discrete Structures (Spring 2007)
- Thursday 6:30-9:00 pm
- Schaumburg Campus, SCH 372
Dr. Evgeny Dantsin
- Schaumburg Campus: SCH 616, Wed/Thu
4:15-6:15 pm
- Chicago Campus: AUD 401, Mon/Thu 2:00-5:45
pm, Tue 1:00-5:45, Sat 1:00-5:00 pm
Sets, logic and Boolean algebras. Basic counting techniques; number systems;
elementary probability; graphs and trees with applications to elementary data
structures. Emphasis on algorithms.
- Susanna S. Epp.
- Discrete Mathematics with Applications.
- 3rd Edition. Brooks/Cole, 2004.
|
Date |
Topics |
Home works |
Textbook |
|
Jan 25 |
Syllabus. Introduction to logic. Statements and truth tables. Logical
equivalences. Tautologies and contradictions. Implications. |
|
1.1-1.2 |
|
Feb 1 |
Arguments. Deductions. Introduction to predicates and quantifiers.
Quantified statements. |
HW-1 |
1.3, 2.1-2.2 |
|
Feb 8 |
Elementary number theory. Methods of proofs. Argument by contraposition.
Argument by contradiction. Examples of classical theorems. |
|
3.1-3.3, 3.7 |
|
Feb 15 |
Sequences. Summations and products. Proofs by mathematical induction. |
HW-2 |
4.1–4.3 |
|
Feb 22 |
Sets: basic definitions and notation. Operations on sets. Countable and
uncountable sets. Application: computability and uncomputability. |
|
5.1-5.2, 7.5 |
|
Mar 1 |
Introduction to probabilities. Counting: multiplication rule,
permutations. |
HW-3 |
6.1-6.2 |
|
Mar 8 |
Counting: inclusion/exclusion, subsets, combinations. |
|
6.3-6.4 |
|
Mar 22 |
Midterm test (open books) |
|
|
|
Mar 29 |
Real-valued functions and their graphs. Asymptotic notation. Growth of
functions. Application: efficiency of algorithms. |
HW-4 |
9.1-9.2, 9.4 |
|
Apr 5 |
Functions defined on sets. One-to-one functions. Inverse functions. |
|
7.1-7.2 |
|
Apr 12 |
Relations on sets. Properties of relations. |
HW-5 |
10.1-10.2 |
|
Apr 19 |
Graphs. Walks in graphs. Connectedness. Euler and Hamiltonian circuits.
|
HW-6 |
11.1-11.2 |
|
Apr 26 |
Trees. Minimum spanning trees. Algorithms for computing minimum spanning
trees. |
|
11.3-11.5 |
|
May 3 |
Review of the course. Preparation for the final exam. |
|
|
|
May 10 |
Final exam (open books). |
|
|
The final grade will be based on the total
number of points earned on six homework assignments (total maximum: 60
points), a midterm exam (maximum: 15 points), and a final exam (maximum: 25 points). Also, extra points will be given for work in class.
Overall grades will be assigned on the following scale:
|
A |
B |
C |
D |
F |
|
≥ 90% |
≥ 75% |
≥ 60% |
≥ 45% |
< 45% |
Statement on cheating and
plagiarism: Instances of academic dishonesty will be handled as described in
University policies. Depending on the severity of the violation, an instructor
may fail a student on the individual assignment or test, may lower the student’s
grade in the course, or may fail the student in the course. More details on the
University's policies on academic honesty may be found in the Student Handbook.
Lecture notes,
slides, assignments and other materials will be posted here after every lecture. |