Discrete Mathematics II (COS 280/Fall 2024)
Instructor:
James Quinlan
Course description
Discrete math is the mathematics of computing. This course lays the foundation for students to succeed in upper-level computer science courses, most of which require understanding of concepts from discrete mathematics. This course is designed for students to learn how to think logically and mathematically, as well as practice fundamental techniques for solving problems in computer science. Topics include: sequences, mathematical induction, recursion, set theory, graphs, trees, analysis of algorithms, and regular expressions. COS 280 is required for the Computer Science major (see all
requirements for Computer Science).
In the realm of computer science, several fundamental topics serve as the building blocks of the discipline. Sequences, for instance, provide an ordered structure for elements, offering a basis for mathematical analysis and algorithm design. Mathematical induction, a powerful proof technique, establishes the validity of statements across infinitely many cases, making it invaluable for understanding recursive algorithms and mathematical structures. Speaking of recursion, it stands as a fundamental problem-solving approach where complex problems are broken down into smaller, similar subproblems. This technique lies at the heart of elegant and efficient recursive algorithm design. It is central to functional programming paradigms.
On the other hand, set theory plays a vital role in understanding collections of objects and their relationships, forming the bedrock for various aspects of computer science. It finds applications in data structure design, database management, and the fundamental principles of computation. Graphs and trees, with their nodes and edges, provide versatile models for organizing and representing data, underpinning algorithms for pathfinding, network analysis, and hierarchical data storage. Analyzing algorithms involves the systematic study of the efficiency and performance characteristics, enabling us to make informed choices when designing and implementing software systems.
Regular expressions, a concise and expressive notation for pattern matching, are pivotal in text processing, parsing, and search operations. These topics collectively form a rich tapestry of knowledge that equips computer scientists with the essential tools and concepts to tackle complex problems and build innovative solutions in computing.
Course Syllabus (pdf)
Prerequisites
Grade of C or higher in:
- MAT 145 - Discrete Mathematics I
- COS 160 - Structured Problem Solving Java
Learning Outcomes
By the end of this course, students will be able to:
- Read, comprehend, and construct mathematical proof arguments.
- Solve sequential, recursive, set and number theoretic problems.
- Discuss graphs, trees, and finite-state machines relate to real-world computational problems.
- Illustrate mathematical techniques for specifying, verifying, and analyzing computer algorithms.
- Identify a variety of natural and relevant uses of discrete math in computer science (and the real world).
Textbook
Additional Resources
- Discrete Mathematics and its Applications by Kenneth H. Rosen: One of the most widely used textbooks for Discrete Mathematics (besides Epp). It covers a broad range of topics and provides clear explanations, examples, and exercises. The book is known for its accessible writing style and comprehensive coverage.
- Concrete Mathematics: A Foundation for Computer Science by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik: This book is a bit more advanced and suited for students with advanced mathematical background, it’s highly regarded for its deep exploration of mathematical concepts relevant to computer science. It’s a great choice for students interested in the mathematical foundations of algorithms and computer programming.
- Discrete Mathematics: An Open Introduction by Oscar Levin: This textbook takes a more open and interactive approach. It’s available for free online and covers the core topics of Discrete Mathematics. It includes exercises, examples, and interactive components that engage students in the learning process.
- Mathematics for Computer Science by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer: While this textbook is not exclusively focused on Discrete Mathematics, it provides a strong foundation in mathematical concepts relevant to computer science. It covers discrete mathematics topics and more, making it a suitable resource for students interested in both discrete math and computer science.
Meetings
Communication
Please communicate through
Brightspace.
Grading
Grades will be based on assignments, quizzes, attendance/participation, a midterm, and a final exam with the following percentages:
- 10%: Attendance and Participation
- 30%: Exercises and assignments
- 10%: Project
- 20%: Quizzes
- 15%: Midterm Exam
- 15%: Final Exam
LaTeX Template
Assignments must be prepared in LaTeX and submitted through Brightspace under the associated assignment.
You may use this
LaTeX template. For comprehensive list of LaTeX symbols, see Pakin, S. (2020).
LaTeX Symbol List.
Late policy
Unless otherwise noted, weekly homework assignments will be due on Monday by 11:59pm.
Late submissions will
not be accepted.
In recognition of the fact that there may unforeseen circumstances that prevent you from submitting some assignments, the three lowest homework grades will be dropped.
Tips for Success
- attend all class meetings
- read the material before coming to class
- complete assignments by the due dates specified
- create a study and/or assignment schedule to stay on track
- read announcements
- communicate regularly with your instructor and peers
- read and respond to course email messages as needed
- utilize USM's Online Student Support Services