Discrete structures syllabus (fall 2020)
Course instructor
TBD
Office hours and course communications
TBD
Course description
This course provides an accelerated introduction to the essentials of discrete structures, combinatorics, graph theory, automata, and algorithms.
Course teaching assistant
TBD
Reference books
- Epp, S. S. (2019). Discrete Mathematics with Applications (5th ed.). Cengage Learning.
- Graham, R. L., Knuth, D. E., & and Oren Patashnik. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley Professional.
- Lewis, H., & Zax, R. (2019). Essential Discrete Mathematics for Computer Science. Princeton University Press.
- Lehman, E., Leighton, F. T., & Meyer, A. R. (2018). Discrete Mathematics for Computer Science. Creative Commons Attribution-ShareAlike 3.0 license. https://courses.csail.mit.edu/6.042/spring18/mcs.pdf
- Liben-Nowell, D. (2017). Discrete Mathematics for Computer Science. Wiley.
- Rosen, K. H. (2018). Discrete Mathematics and its Applications (8th ed.). McGraw-Hill.
Student learning outcomes
After successful completion of the course, the students will be able to do the following:
-
Model computational problems and solve them using sets, relations, and functions.
-
Solve counting problems using combinatorial techniques.
-
Apply concepts of graph theory to model and solve graph-theoretic problems.
-
Solve different types of recurrence relations exactly and asymptotically.
-
Prove lemmas and theorems using mathematical induction.
-
Algebraically manipulate asymptotic expressions.
-
Solve a class of computational problems using finite state automata.
-
Critique capabilities and limitations of finite state automata.
Major course topics
-
Logic and proof techniques
-
Essential discrete structures: sets, functions, sequences, sums, matrices, and relations
-
Algorithms and asymptotic notations - Big-O, Big-Omega and Big-Theta
-
Induction and recursion
-
Counting principles, permutations and combinations, and binomial coefficients.
-
Discrete probability
-
Techniques for solving recurrence relations
-
Graph terminology and concepts, basic graph theory and algorithms, modeling real life problems using graphs
-
Trees and tree traversals
-
Analysis and design of finite state automata
-
Capabilities, limitations and applications of finite state automata
Respect for Diversity
It is my intent to serve well in this course all students from diverse backgrounds and perspectives. Students’ learning needs will be addressed both in and out of class. The diversity that students bring to this class be viewed as a resource, strength and benefit. I will strive to present the course content and learning activities that are respectful of diversity: gender, sexuality, disability, age, socioeconomic status, ethnicity, race, and culture. Your suggestions are encouraged and appreciated. Please let me know ways to improve the effectiveness of the course for you personally or for other student groups.
Course assessment and grading scale
Undergraduate students
- Assignments (30%)
- Midterm exam (30%)
- Final exam (40%)
| Score range | Letter grade |
|---|---|
| 93 - 100 | A |
| 90 - 92 | A- |
| 87 - 89 | B+ |
| 83 - 86 | B |
| 80 - 82 | B- |
| 77 - 79 | C+ |
| 73 - 76 | C |
| 70 - 72 | C- |
| 67 - 69 | D+ |
| 63 - 66 | D |
| 60 - 62 | D- |
| 59 or below | F |
Graduate students
- Assignments (30%)
- Midterm exam (30%)
- Final exam (35%)
- Innovative contribution to online course content (5%)
| Score range | Letter grade |
|---|---|
| 90.0 - 100 | A |
| 80.0 - 89.9 | B |
| 70.0 - 79.9 | C |
| < 69.9 | F |
Extra credit (up to 5%) assignments are available to both graduate and undergraduate students. Those who wish to seek extra credit, check with the course instructor.