Term: 2019 Spring
Instructor: Dr. Chengjiang Long
Email: clong2@albany.edu
Office Hour: Wed 12:45 PM – 3:45 PM at UAB 412E (by appointment).
Teaching Assistant: Siqian Zhao (szhao2@albany.edu) and
Ronke Osipitan (iosipitan@albany.edu)
Student Assistant: Mehrdad Mirzaei (mmirzaei@albany.edu) and Shalin Alfred (salfred@albany.edu)
Lecture Time: Monday, Wednesday and Friday, 11:30 AM – 12:25 PM
Lecture Building/Room: Lecture Center 25, University at Albany, SUNY.
TA Office Hour:
- Siqian, Zhao, Thu 2:50 PM – 5:50 PM at UAB 434.
- Ronk Osiptan, Tue 1:20 PM - 2:20 PM at UAB 412D.
- Ronk Osiptan, Thu 1:30 PM - 3:30 PM at UAB 412D.
Lab/Discussions:
- Monday 9:20 AM - 10:15 AM, BB B010, by Siqian Zhao.
- Wednesday 10:25 AM - 11:20 AM, ED 125, by Siqian Zhao.
- Friday, 10:25 AM - 11:20 AM, BB B012, by Ronke Osipitan.
- Friday, 12:35 PM - 1:30 PM, BB B012, by Ronke Osipitan.
Course Website:
www.chengjianglong.com/teaching_UAlbanyDS2.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”, 7-th Edition, Mc Graw Hill, 2012.
Grading:
The students will be graded based on course/discussion participation (5%), homework assignments (50%), two midterm exams (15%), one final exam (30%).
Extra points: 20% for each homework. Note that this is optional, the purposes of this design is to encourage the self-motivated students to challenge themselves and give them more chances to get a higher score.
Attendance bounus: I would like to give the bonus to reward those students whose attendance is less than 3. For those who never miss any class, I will give them 5 extra points on the final grade. For those who miss only 1 class, I will give them 2 extra points. And for those who miss 2 classes, I will give them 1 extra point on the final grade.
Final grade: A(>=92), A-(>=90), B+(>=87), B(>=82), B-(>=80), C+(>=77), C(>=72), C-(>=70) and F (<70).
Late submission policy:
Exponential penalty -- late for one day loses 25%, two days loses 50%, 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/Exam | Slides |
|---|
| 1 | 1/23/2019 | Introduction | | | Lecture_1 |
| 2 | 1/25/2019 | Propositional Logic | Ch 1.1-1.2 | | Lecture_2 |
| 3 | 1/28/2019 | Predicate Calculus and Quantifiers | Ch 1.3-1.4 | Homework_1 | Lecture_3 |
| 4 | 1/30/2019 | Quantifiers and Rules of Inference | Ch 1.4-1.5 | | Lecture_4 |
| 5 | 2/1/2019 | Proofs | Ch 1.5-1.8 | | Lecture_5 |
| 6 | 2/4/2019 | Introduction to Sets | Ch 2.1 | Homework_2 | Lecture_6 |
| 7 | 2/6/2019 | Set Operations and Introduction to Functions | Ch 2.2-2.3 | | Lecture_7 |
| 8 | 2/8/2019 | Functions | Ch 2.3 | | Lecture_8 |
| 9 | 2/11/2019 | Sequences and Summation (1) | Ch 2.4 | Homework_3 | Lecture_9 |
| 10 | 2/13/2019 | Sequences and Summation (2) | Ch 2.4 | | Lecture_10 |
| 11 | 2/15/2019 | Cardinality of Sets | Ch 2.5 | | Lecture_11 |
| 12 | 2/18/2019 | Matrices | Ch 2.6 | Homework_4 | Lecture_12 |
| 13 | 2/20/2019 | Algorithms | Ch 3.1 | | Lecture_13 |
| 14 | 2/22/2019 | Growth of Functions and Complexity | Ch 3.2-3.3 | | Lecture_14 |
| 15 | 2/25/2019 | Review for Mideterm 1 | | Homework_5 | Lecture_15 |
| 16 | 2/27/2019 | Integers and Division | Ch 4.1 | | Lecture_16 |
| 17 | 3/1/2019 | Modular Arithmetic | Ch 4.1 | | Lecture_17 |
| 18 | 3/4/2019 | Integer Representations | Ch 4.2 | Homework_6 | Lecture_18 |
| 19 | 3/6/2019 | Primes and Greatest Common Divisors | Ch 4.3 | | Lecture_19 |
| 20 | 3/8/2019 | Midterm Exam 1 | Ch 1.1 - Ch 3.3 | Midterm Exam 1 | |
| 21 | 3/11/2019 | Cryptograph | Ch 4.6 | Homework_7 | Lecture_20 |
| 22 | 3/13/2019 | Mathematical Induction | Ch 5.1-5.2 | | Lecture_21 |
| 23 | 3/15/2019 | Strong Induction and Well-Ordering | Ch 5.2 | | Lecture_22 |
| 3/18/2019 | Class Suspended -- Spring Break | | | |
| 3/20/2019 | Class Suspended -- Spring Break | | | |
| 3/22/2019 | Class Suspended -- Spring Break | | | |
| 24 | 3/25/2019 | Structural Recursion and Induction | Ch 5.3 | Homework_8 | Lecture_23 |
| 25 | 3/27/2019 | Recursive Algorithms | Ch 5.4 | | Lecture_24 |
| 26 | 3/29/2019 | Recursive Algorithms and Basic Counting Rules | Ch 5.4 and Ch 6.1 | | Lecture_25 |
| 27 | 4/1/2019 | Pigeonhole Principle, Permutations and Combination | Ch 6.2-6.3 | Homework_9 | Lecture_26 |
| 28 | 4/3/2019 | Binomial Coefficients and Identities | Ch 6.4 | | Lecture_27 |
| 29 | 4/5/2019 | Inclusion-exclusion Principle | Ch 8.5-8.6 | | Lecture_28 |
| 30 | 4/8/2019 | Discrete Probability | Ch 7.1-7.2 | Homework_10 | Lecture_29 |
| 31 | 4/10/2019 | Conditional Probability | Ch 7.2-7.3 | | Lecture_30 |
| 32 | 4/12/2019 | Review for Midterm Exam 2 | | | |
| 32 | 4/15/2019 | Bayes Rules, Expected Value, Variance and Binorminal Distribution | Ch 7.3-7.4 | Homework_11 | Lecture_31 |
| 33 | 4/17/2019 | Midterm Exam 2 | Ch 4.1 - Ch 6.4 | Midterm Exam 2 | |
| 35 | 4/19/2019 | Relations (1) | Ch 9.1-9.3 | | Lecture_32 |
| 4/22/2019 | Class Suspended -- Easter | | | |
| 36 | 4/24/2019 | Relations (2) | Ch 9.4-9.5 | | Lecture_33 |
| 37 | 4/26/2019 | Graph Theory (1) | Ch 10.1-10.5 | | Lecture_34 |
| 38 | 4/29/2019 | Graph Theory (2) | Ch 10.1-10.5 | Homework_12 | Lecture_35 |
| 39 | 5/1/2019 | Trees | Ch 11.1-11.5 | | Lecture_36 |
| 40 | 5/3/2019 | Recap and Review (1) | | | |
| 41 | 5/6/2019 | Recap and Review (2) | | | |
| 42 | 5/8/2019 | Recap and Review (3) | | | |
| 43 | 5/13/2019 (3:30pm – 5:30pm) | Final Exam | Ch 1-Ch 11 | Final Exam | |
Note: The above course schedule may be subject to change. Please do check the latest update.
|
