CS 275 - Discrete Mathematics
Credits: 4
Course Description
Topics in discrete math aimed at applications in Computer Science. Fundamental principles: set theory, induction, relations, functions, Boolean algebra. Techniques of counting: permutations, combinations, recurrences, algorithms to generate them. Introduction to graphs and trees.
Prereqs: MA-113 and CS-115
Needed Skills
Students need to be familiar with basic algebra and calculus, basic programming techniques in a general purpose programming language, data structures including lists, elementary algorithms such as searching and basic sorting, and basic concepts of recursion.
Learning Outcomes
Students will develop knowledge of a variety of mathematical tools applicable in computer science. Specifically, students will be able to
1. construct inductive proofs
2. apply set algebra
3. apply elementary logic
4. enumerate combinatorial objects
5. solve recurrence relations
Measures
These five specific outcomes will be evaluated on the basis of student work (homeworks and exams) that will contain problems specifically addressing these outcomes. They will also be evaluated on the basis of student self-assessment of their mastery of the five outcomes performed at the end of the semester.
CAC Categories
Topic
|
Core
|
Advanced
|
Math
Fundamentals
|
38
|
12
|
Data
Structures
|
2
|
0
|
Algorithms
& Software Design
|
5
|
0
|
Computer
Organization and Architecture
|
0
|
0
|
Concepts
of Programming Languages
|
17
|
0
|
Social
and ethical issues
|
1
|
0
|
Total
|
30
|
0
|
Math Fundamentals (50): Core (38): Functions, relations, and sets (6); Basic logic (6); Proof techniques (8); Basics of counting (8) Graphs and trees (6) Discrete probability (4); Advanced (12): Advanced counting techniques (recurrences, generating functions) (8); Advanced graph topics (4)
Data structures (2): Core (2): Fundamental data structures (graphs and trees)
Algorithms and Software (7): Core (7): Basic algorithmic analysis (algorithm analysis, tree and graph algorithms) (3); Fundamental computing algorithms (generating combinations, permutations Grey codes) (4)
Social and Ethical Issues (1): Discussion of professional and academic integrity
Oral Communication (presentations)
none
Written Communication
8-10 homeworks and projects, 2 pages/assignment
Content
Theoretical content: 50%
· Set theory
· Mathematical proofs
· Mathematical induction and recursive definitions
· Counting elements in unions and products of sets, counting permutations, combinations
· Enumeration algorithms
· Binomial theorem
· The inclusion/exclusion principle
· Discrete probability, relations
· Partial orders and equivalence relations
· Functions
· One-to-one and onto functions
· Compositions and inverses
· The Pigeonhole principle
· Boolean algebra, Boolean functions, logic gates
· Recurrences, linear recurrences: divide-and-conquer
· Relation to analysis of algorithms
· Graphs, paths, cycles, colorings, trees, spanning trees
· Discrete probability
Problem analysis: 25%
· Formulate and study properties of counting structures, of functions and relations, of graphs and trees
Solution design: 25%
· Construct proofs of properties of discrete structures; construct inductive proofs of properties of integers, trees and graphs
· Find solutions to counting problems
Student evaluation and feedback
Students are evaluated on their work (homeworks, exams). Students receive back their homework and exams. These papers are marked to indicate problems and they point out correct or better solutions. Problems that turn out to be especially difficult are discussed in class during lectures or during recitations.
NOTE: 75% lecture - 25% recitations
Course Evaluation Questions
The course has taught me:
37. how to construct proofs by mathematical induction
38. how to apply laws of set algebra
39. how to apply elementary logic
40. how to enumerate combinatorial objects
41. how to solve recurrence relations
42. to understand the relevance of discrete
43. to understand the relevance of discrete mathematics to CS curriculum
Possible Textbooks
Discrete Mathematics and its Applications
K. Rosen
McGraw Hill, 1994
Discrete and Combinatorial Mathematics
R.P. Grimaldi