Constructing Proofs - CS 1050 A

Instructor: Edyta Szymanska

email: edyta at cc dot gatech dot edu
Class: MWF 9:05-9:55 in CCB 101.
Office Hours: MWF 10-11am and by appointment;

Teacher Assistant:

Rohit Sud

email:rohitsud@cc.gatech.edu
Office Hours: T 1-2pm in CoC Commons area

Textbook:

Discrete Mathematics and Its Applicationsby Kenneth H. Rosen, 6th Edition, ISBN#: 0072880082

Grading:

Homeworks: 25%, three tests: 35%, Final exam: 40%.

Tentative Important Dates:

    Test 1: Friday, February 8
    Test 2: Monday, March 10
    Test 3: Monday, April 21
    Final exam: Tuesday, April 29, 2:50-5:40 pm

Announcements:

    ADDITIONAL office hours on Th 2/7 11am-1pm in Klaus 2115.
    Homework grades and solutions will be posted on T_Square
    Office hours on Tuesday 1/15 at 1-3pm in Klaus 2115

No. Date Material covered (reading) Homework[DueDate] Comments, handouts
1 01/07 Propositional Calculus (1.1-3) syllabus
2 01/09 Quantifiers. Proof by enumeration. (1.4) Berkeley notes
3 01/11 Direct proof, proof by contraposition and by contradiction.(1.5-6) H1 [1/16]+ Assignment guidePLEASE NOTE THE CORRECTION IN 5(a). h1 out
4 01/14 Proof by cases. Proof strategy.(1.7)
5 01/16 The principle of mathematical induction. (4.1) h1 due
6 01/18 More inductive proofs and strong induction.(4.2) H2 [1/23] h2 out
01/21 holiday
7 01/23 Recursive definitions and structural induction.(4.3) h2 due
8 01/25 Structural Induction. Recursive algorithms.(4.3, 4.4) H3[1/30] h3 out
9 01/28 More on recursive and iterative algorithms.(3.1,4.4) Sorting (slides 5-)
10 01/30 The analysis of insertion sort and merge sort. (3.1) and (4.4) h3 due
11 02/1 Asymptotic notation: big-O.(3.2) H4[2/6] h4 out
Test 1-Sample Problems The test will cover the material presented in the lecture till Friday 2/1(inclusive).
12 02/4 Program correctness.(4.5)
13 02/6 Review. h4 due
14 02/8 TEST #1
15 02/11 Basic counting: sum and product rules.
16 02/13 Generalized product rule, bijection rule and the principle of inclusion-exclusion.
17 02/15 Pigeonhole principle.(5.2) H5 [22/20](5d - "3 exactly once") h5 out
18 02/18 Counting selections: ordered with and without repetitions.
19 02/20 Combinations with and without repetitions. h5 due
20 2/22 Exercises in counting. H6 [2/27] h6 out
Counting Problems
21 02/25 Combinatorial proofs and the binomial theorem.
22 02/27 Introduction to probability. h6 due
23 2/29 Conditional probability. Independence and Bernoulli trials. H7 [3/5] h7 out
24 3/3 Random variables. Random hash functions.
25 03/5 Monte Carlo algorithms. h7 due Test 2- Info + Sample Problems
26 03/7 Review.
27 03/10 TEST #2
28 03/12 Expectation.
29 03/14 Applications: from Monte Carlo algrothms to Las Vegas algorithms, MAX-SAT.
03/17-21 Spring break
30 03/24 Relations. Equivalance relations.
31 03/26 Partial orders and Hasse diagrams.
32 03/28 Graphs. H8 [4/2]
In Problem 6: the relation should be defined as ad=bc . 		h8 out
33 3/31 Graph isomorphism.(9.3) Are these pairs of graphs isomorphics?
34 04/2 Connectedness: connected and strongly connected components. the Erdos number
Erdos number project
h8 due
35 04/4 Euler walks and circuits versus Hamilton paths and cycles. H9 [4/7] h9 out
36 04/7 Planar graphs.
37 04/9 Planar graphs and coloring maps. h9 due
38 04/11 Trees. Properties of trees. H10[4/16]
USmap 		h10 out
39 04/14 Rooted trees. Applications of trees.
40 04/16 Game trees. Binary search trees. h10 due
Test 3- Info + Sample Problems
41 04/18 Review.
42 04/21 TEST #3
43 04/23 Review. selected problems
44 04/25 Review. selected problems
FinalExamInfo
04/29 FINAL EXAM

Course Outline:

  1. Logic and Proofs. (Chapter 1)
  2. The Fundamentals of Algorithms. (Chapter 2 and 3)
  3. Induction and Recursion. (Chapter 4)
  4. Counting. The Pigeonhole Principle. (Chapter 5)
  5. Discrete Probability. (Chapter 6)
  6. Recurrence Relations. (Chapter 7)
  7. Graphs. (Chapter 9)
  8. Trees. (Chapter 10)
  9. Number theory. (Chapter 3)

Contact

Edyta Szymanska
Klaus 2115
(404)385-2272
College of Computing
Georgia Institute of Technology
Atlanta, Georgia