Term: 2018 Fall
Instructor: Dr. Chengjiang Long
Email: clong2@albany.edu
Time: Monday, Wednesday and Friday, 9:20am – 10:15am
Building/Room: Lecture Center 25, University at Albany, SUNY.
Office Hour: Friday 10:30 am  12:00 pm at UAB 412 B (by appointment).
TA Office Hour: Thursday 12:003:00 pm at UAB 412 E.
Teaching Assistant: Sourav Dutta (sdutta2@albany.edu)
Student Assistant: Jonathan P Mulhern（jmulhern@albany.edu) and Prachi D Vachhani（pvachhani@albany.edu)
Course Website: www.chengjianglong.com/teaching_UAlbanyDS.html
Course Overview: The course is to introduce students to the techniques that may be used and enhanced later in professions related to Computer Science. Computer Science specialists could choose a career of developer, analyst, manager, etc. It is important for all of them to understand or to create formal (most often mathematical) description of the problem to be solved. This course covers a wide range of different aspects of discrete mathematics that are applicable to solving programming problems: proofs by induction; mathematical reasoning, propositions, predicates and quantifiers; sets; relations, graphs, and trees; functions; counting, permutations and combinations.
Prerequisites: Students should have a fundamental understanding of mathematical reasoning as well as be competent in solving applied algebra problems.
The most important prerequisites are interest in the subject, willingness to dedicate necessary resources in terms of time and intellectual effort, and willingness to actively participate in the learning process.
No programming skills are required to pass the course.
Text Books: Kenneth Rosen, “ Discrete Mathematics and Its Applications”, 7th Edition, Mc Graw Hill, 2012.
Grading: The students will be graded based on course/discussion participation (10%), homework assignments (40%), two midterm exams (20%), one final exam (30%).
Final grade: A(>=92), A(>=90), B+(>=87), B(>=82), B(>=80), C+(>=77), C(>=72), C(>=70), D+(>=67), D(>=62), D(>=60) and F (<60).
Late submission policy: Exponential penalty  late for one day loses half, two day loses another half of the remaining, and so on and so forth.
Topics:
 Introduction to Discrete Structures.
 Logic Inference, Predicates, Qualifiers.
 Boolean Algebra, Logic Gates, Logic Minimization.
 Sets, Functions, Sequences, Sums, Matrices, Matrix Algebra.
 Algorithms, Searching, Sorting, Complexity of Algorithms.
 Number Theory, Cryptography, Modular Arithmetic.
 Induction and Recursion.
 Counting.
 Relations.
 Graphs.
 Trees.
Course schedule:
Class  Date  Topic  Reading  Homework  Slides 
1  8/27/2018  Introduction    Lecture_1 
2  8/29/2018  Propositional Logic  Ch 1.11.2   Lecture_2 
3  8/31/2018  Predicate Calculus and Quantifiers  Ch 1.31.4   Lecture_3 
 9/3/2018  Class Suspended  Labor Day    
4  9/5/2018  Quantifiers and Rules of Reference  Ch 1.41.5   Lecture_4 
5  9/7/2018  Proofs  Ch 1.51.8  Homework 1 Assigned.  Lecture_5 
 9/10/2018  Class Suspended  Rosh Hashanah    
6  9/12/2018  Introduction to Sets  Ch 2.1   Lecture_6 
7  9/14/2018  Set Operations and Introduction to Functions  Ch 2.22.3   Lecture_7 
8  9/17/2018  Functions  Ch 2.3  Homework 1 Due.  Lecture_8 
 9/19/2018  Class Suspended  Yom Kippur    
9  9/21/2019  Sequences and Summation (1)  Ch 2.4   Lecture_9 
10  9/24/2019  Sequences and Summation (2)  Ch 2.4   Lecture_10 
11  9/26/2018  Cardinality of Sets  Ch 2.5   Lecture_11 
12  9/28/2018  Matrices  Ch 2.6  Homework 2 Assigned  Lecture_12 
13  10/1/2018  Algorithms  Ch 3.1   Lecture_13 
14  10/3/2018  Growth of Functions and Complexity  Ch 3.23.3   Lecture_14 
15  10/5/2018  Integers and Division  Ch 4.1   Lecture_15 
16  10/8/2018  Midterm Exam 1  Ch 1.11.8, Ch 2.12.6  Homework 1 Due and Midterm Exam 1  
17  10/10/2018  Modular Arithmetic  Ch 4.1   Lecture_16 
18  10/12/2018  Integer Representations  Ch 4.2   Lecture_17 
19  10/15/2018  Primes and Greatest Common Divisors  Ch 4.3   Lecture_18 
20  10/17/2018  Cryptograph  Ch 4.6   Lecture_19 
21  10/19/2018  Cover Midterm Exam 1 and Homework    
22  10/22/2018  Proof by Mathematical Induction  Ch 5.15.2   
23  10/24/2018  Proof by Strong Induction  Ch 5.2   
24  10/26/2018  Some Aspects of Proof by Inductions  Ch 5.2   
25  10/29/2018  Recursive/Inductive Definitions  Ch 5.3   
26  10/31/2018  Structural Recursion and Induction  Ch 5.3   
27  11/2/2018  Recursive Algorithms and Algorithm Correctness  Ch 5.4   
28  11/5/2018  Counting  Ch 6.1   
29  11/7/2018  Pigeonhole Principle  Ch 6.2   
30  11/9/2018  Permutations and Combination  Ch 6.3   
31  11/12/2018  Midterm Exam 2    
32  11/14/2018  Number of Permutations and Combinations  Ch 6.3   
33  11/16/2018  Binomial Coefficients. Pascal’s Triangle  Ch 6.4   
34  11/19/2018  Generalized Permutations and Combinations  Ch 6.5   
35  11/21/2018  Relations  Ch 9.19.5   
 11/23/2018  Class Suspended  Thanksgiving Break    
 11/26/2018  Class Suspended  Thanksgiving Break    
36  11/28/2018  Relations  Ch 9.19.5   
37  11/30/2018  Graphs  Ch 10.110.5   
38  12/3/2018  Graphs  Ch 10.110.5   
39  12/5/2018  Trees  Ch 11.111.5   
40  12/7/2018  Trees  Ch 11.111.5   
41  12/10/2018  Recap and Review    
42  TBA  Final Exam    
