Discrete Mathematics II (COS 280/Fall 2024)

Department of Computer Science at the University of Southern Maine

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:

Learning Outcomes

By the end of this course, students will be able to:

Textbook

Epp Textbook Epp, S. S. (2020). Discrete Mathematics with Applications (5th ed.). Cengage. ISBN: 978-1-337-69419-3.

Additional Resources

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:

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

Last modified Tue Sep 3 2024 05:54:23 PM EDT Quinlan