Discrete Structures CSC102¶
| Course Title | Discrete Structures |
| Corse Code | CSC102 |
| Credit Hours | 3(3, 0) |
| Pre-requisite(s) | - |
Intro¶
Discrete structures underlie the areas of data structures, formal methods, artificial intelligence, automata theory, computational complexity and the analysis of algorithms. Continuing advances in technology - particularly in applications of computing and software engineering, have enhanced the importance of discrete mathematics for understanding not only the foundations of computer science but also the basis of a wide variety of applications.
Prior Knowledge¶
It is assumed that students entering have already taken the course of computer science or programming. They have a strong background in mathematics.
Education Aim¶
Subject Specific: Knowledge, Understanding and Skills¶
- To understand the logic.
- To understand the different theorem proof techniques and methodological expertise
- To apply the theoretical and mathematical understanding of discrete structures used in computer science
- To apply the problem solving and analytical skills
- To apply algorithmic and computational skills
Transferable Skills¶
- To provide the mathematical skills necessary for understanding computer science
- Help students develop their general ability to think abstractly
- Helps the students to the general development of problem-solving skills
Subject Specific: Knowledge, Understanding and Skills¶
This course provides overview of different discrete structures and proof techniques to develop analytical and design skills such that they can understand correct mathematical arguments and their design. At the end of the course students should be able to have:
- Solve problems which involve discrete data structures such as sets, relations and functions.
- Construct valid mathematical arguments (proofs) and understand/apply mathematical statements (theorems)
- Solve problems which require computation of permutations and combinations of a set
- Analyze a problem to create relevant recurrence functions
- Apply basic counting principles to solve a variety of problems
- Apply the mathematical concepts learned to various areas of computer science
- Solve problems which involves discrete structures tree and graphs
General and Transferable Skills¶
- Apply a wide range of principles of discrete mathematics, such as problem solving, good thinking, choice of algorithm, and mathematical proofs.
- Interact with problems using different methods of thinking and problem solving.
Course Content¶
- Logic: Formal Logic and Logical forms, Logical Equivalence and Logical Connectives, Statements and their symbolic representations, Compound statements, Contradictions and Tautologies, Conditional Statements and their Logical Equivalence, Application of Logic, Valid and Invalid Arguments
- Predicate Logic: Quantifiers and Predicates, Predicate Logic, Multiple Quantifies Statement and Arguments with Quantifies Statements
- Proof Techniques: Direct Proof, Indirect Proof, Mathematical Induction, Rules of Inferences
- Elementary Number Theory: Sequences, Summation, Product and Factorial Notations, Recursion
- Set Theory: Basic Set, Power Sets, Set operations, Set Identities, Venn diagram
- Counting Techniques: Sum and Product rule, Inclusion Exclusion Principle, Pigeon hole principle, Permutation and Combinations
- Relations: Relations Properties, representation, Equivalence Relation
- Functions: Valid and Invalid functions, function types and its application
- Graphs and Trees: Graph types, Problems and representations, Rooted tree, Tree traversal, Spanning Trees
Text Book¶
- Discrete Mathematics and its applications, Kenneth H. Rosen, McGraw-Hill.
Reference Book¶
- Discrete Mathematics with Applications 3rd Ed. by Susanna S., Thomson Learning, Inc.
- Discrete Mathematics with Applications, Thomas Koshy, Elsevier.