Understanding and Constructing Proofs - CS 1050B

Instructor: Edyta Szymanska

Class: MWF 12:05-12:55 in room CoC 17.

Office Hours: Wednesday 10:00-11:00 and by appointment;

Teacher Assistants:

Trask Rogers
Yi Ma
Ziru Zhu
Office hours: M 6-8pm Commons area M 1-3 Commons area Th 1-3 Commons area
Phone:

Textbook:

Discrete Mathematics and Its Applications by Kenneth H. Rosen, Fifth Edition, Mc Graw-Hill, 2003

Grading:

Homeworks: 20%, two Mid-terms: 40%, Final exam: 40%.

Important Dates:

    Mid-term 1: Monday, February 10
    Mid-term 2: Monday, March 24
    Final exam: Thursday, May 1, 8:00-10:50 am

Class newsgroup: git.cc.class.cs1050b

To see your grades go to: WebCT


No. Date Material covered Homework[DueDate] Comments, handouts
1 01/06 Propositional Calculus (1.1) syllabus
2 01/08 Propositional Equivalences (1.2)
3 01/10 Predicates and Quantifiers (1.3) 4hf, 10ef, 12b /16, 22a, 30/18, 8c/26, 24/27, 54/28, 6, 10a/40 [01/15] AssignmentGuide
4 01/13 Nested Quantifiers (1.4)
5 01/15 Fuzzy logic. Rules of Inference.
6 01/17 Methods of proof. 6ef/51, 12no/53, 28gi/54, 32bc/55, 6/73, 12ab/74, 22, 26, 30, 36/75 [01/22]
7 01/22 Methods of proof (cont.).
8 01/24 Methods of proof (cont.). 34, 40, 42, 46/75, 50, 52, 64, 68/76, 28, 30/116 [01/29]
9 01/27 Sets.
10 01/29 Sets operations.
11 01/31 Functions. 10, 12d, 14b, 30b/95, 40/96, 4ab/108, 8gh, 10ac, 16a, 18ab/109 [02/05]
12 02/03 Algorithms. MidtermExamInfo
13 02/05 Complexity. SampleExamProblems
14 02/07 Review. No homework this week.
15 02/10 MIDTERM EXAM #1
16 02/12 Sequences. Summations. Cardinality.
17 02/14 Cardinality. 8ac/142, 8/236, 10e/236, 28/237, 20/237, 16bd/237, 38/238, 2/253, 4/253, 6/253[02/19]
18 02/17 Diagonalization method. Mathematical induction.
19 02/19 Mathematical induction.(cont.)(3.3)
20 02/21 Strong induction.(3.3) 12/253,14/253,20/254,24/254,32/254,40/254,6ac/271,8/271,12/271,60/273[02/26]
21 02/24 Recursive definitions. (3.4)
22 02/26 Structural induction.
23 02/28 Mathematical induction - exercises. Bonus (ExtraCredit) [03/12]
24 03/10 Recursive algorithms.
25 03/12 Basics of counting.(4.1)
26 03/14 Pigeonhole principle.(4.2) 40/272, 16/283, 12/310, 18/310, 24/311, 36/311, 44/312, 4/319, 10/319, 14/319 [03/19]
27 03/17 Permutations and combinations.
28 03/19 Combinations. The binomial theorem. Exam2SampleProblems
29 03/21 REVIEW. Convert_ps2pdf
30 03/24 MIDTERM EXAM #2
31 03/26 Relations.
32 03/28 Equivalence relations. 4/480, 6/480, 24/480, 6/495, 8/495, 32/495, 8/513, 24/514,32/514,36ad/515, (44/515 BONUS+3points)[04/02]
33 03/31 Reprezenting Relations. Graphs.
34 04/02 Midterm problems solutions.
35 04/04 Graph isomorphism. 22/555, 26/555, 34a/556, 28/564, 38/565, 44/565, 6/589, 10/589, 34/590, 50/591, (60/592 BONUS+2points)[04/09]
48 04/07 Euler and Hamilton paths and circuits.
49 04/09 Trees.
50 04/11 Properties and applications of trees. 4/642,12/642,16/642,22/643,4/656,42/659,14/697,16/697,4cd/708,6/708[Friday, 04/18] NOTE about Problem 14 & 16/697: there is a typo in the description of the recursive definition of binomial trees: Should be "... by adding an edge that makes the root of the first copy of B_k the leftmost child of the root of the second copy of B_k."
51 04/14 Game Trees. Boolean algebra.
52 04/16 Boolean functions and expressions.
53 04/18 Boolean circuits.
54 04/21 Minimization of circuits: K-maps and the Quine-McCluskey method. Suggested practise (not for credit): 3,6/p.732, 9,12/p.733, 23/p.734
55 04/23 REVIEW.
56 04/25 REVIEW.

Course Outline:

  1. Logic. Sets and Functions. (Chapter 1)
  2. The Fundamentals of Algorithms. (Chapter 2)
  3. Mathematical Reasoning. Induction and Recursion. (Chapter 3)
  4. Counting. The Pigeonhole Principle. (Chapter 4)
  5. Discrete Probability. (Chapter 5)
  6. Recurrence Relations. (Chapter 6)
  7. Relations and Their Properties. (Chapter 7)
  8. Graphs. (Chapter 8)
  9. Trees. (Chapter 9)
  10. Boolean Algebra. (Chapter 10)

Contact

Edyta Szymanska
room 123 CoC
(404)385-2272
College of Computing
Georgia Institute of Technology
Atlanta, Georgia