CSC 226 Discrete Mathematics for Computer Scientists

3 Credit Hours

Propositional logic and predicate calculus. Methods of proof. Elementary set theory. Mathematical induction. Recursive definitions and algorithms. Solving recurrences. The analysis of algorithms and asymptotic growth of functions. Elementary combinatorics. Introduction to graph theory. Ordered sets, including posets and equivalence relations. Introduction to formal languages and automata.

Prerequisites

MA 101 Intermediate Algebra or equivalent completed in high school. Previous programming experience would be helpful, but is not required.

Course Objectives

Upon satisfactory completion of this course, you should be able to:

Understand, within the framework of the propositional calculus, truth tables, logical equivalence and implication, tautologies and contradictions, rules of inference, how to do logical proofs including direct proofs, indirect proofs, and proofs of implications.
Know and understand logical predicates and the universal and existential quantifiers, and how to use them to represent English statements of quantity. Students will be able to carry out proofs containing quantified axioms.
Know basic set definitions, be able to prove elementary properties of sets using formal, set theoretic notions, and be acquainted with infinite sets and their properties. Students will understand “diagonalization arguments” as illustrated by the proof of the non-countability of the real numbers and by the “halting problem.”
Have basic knowledge of functions, 1-1 functions, onto functions, and 1-1 correspondences. Students will be acquainted with sequences and how they are different from sets.
Understand the concept of Big-O, Big-Omega and Big Theta (order) complexity, and how to solve run-time problems based on these concepts. Students will understand how to analyze simple algorithms with regard to their run-time complexity.
Have a solid working knowledge of proof by mathematical induction, and will be comfortable with inductive proofs.
Understand modular computations, algorithms for computing efficiently with huge numbers, and the theorems that underlie modern cryptography such as Fermat’s Little Theorem. Students will understand how RSA encryption works.
Understand recursive definitions of sets, strings and sequences, and be able to find closed-form solutions to simple recurrence relations, and prove the correctness of such solutions by means of mathematical induction. Students will acquire skill in finding recurrence relations that model a problem and finding recurrence relations based on the closed form of a sequence.
Understand basic combinatorics, including the rules of product and sum, permutations and combinations with and without “replacement.”
To be conversant both with ordinary numerical matrices and Boolean matrices, and the various operations that apply to them.
Comprehend the notion of a binary relations, and the accompanying definitions, expressed in logical formalism, of Reflexive, Irreflexive, Symmetric, Antisymmetric, Asymmetric and Transitive. They will also understand significant kinds of binary relations such as Partial Orders and Hasse Diagrams, and Equivalence Relations and Equivalence Classes. Students will know how to represent relations in matrices, thus allowing them to be computationally processed.
Have knowledge of elementary graph theory, including formal definitions of graphs using logic, types of graphs including simple graphs, directed graphs, multigraphs and pseudographs; isomorphisms of graphs, adjacency matrix representations of graphs, and incidence matrix representations of graphs. Students will further understand the notions of Euler circuits, Euler paths, Hamiltonian circuits, Hamiltonian paths, and how to compute whether such circuits and paths exist within a graph.
Understand trees as special types of directed graphs and how to prove properties of trees by means of inductive proofs on the heights of trees.

Course Requirements

The final grade in the course is based on:

Homework (30%)
3 Exams (15% each)
Final Exam (25%)

Textbook

Required:

FOR SUMMER 2021:

CSC226: Discrete Mathematics for Computer Scientists Zybook
1. Sign in or create an account at learn.zybooks.com
2. Enter zyBook code: NCSUCSC226WatkinsSummer 2022
3. Subscribe

Optional:

Discrete Mathematics and its Applications, 7^th Edition. Kenneth Rosen, McGraw-Hill, 2012.
Print:ISBN-10: 0-07-338309-0 / ISBN-13: 978-0-07-338309-5
eText: ISBN-10: 0-07-735347-1 / ISBN-13: 978-0-07-735347-6

Student Solutions Guide, 7th Edition. Kenneth Rosen, McGraw-Hill, 2011.
ISBN-10: 0077353501
ISBN-13: 978-0077353506

********

FOR FALL 2021:

CSC226: Discrete Mathematics for Computer Scientists Zybook
1. Sign in or create an account at learn.zybooks.com
2. Enter zyBook code: NCSUCSC226WatkinsFall2021
3. Subscribe

Optional:

Student Solutions Guide, 7th Edition. Kenneth Rosen, McGraw-Hill, 2011.
ISBN-10: 0077353501
ISBN-13: 978-0077353506

Updated 10/28/2022