CIS1871 - DISCRETE STRUCTURES I
3 Credit Hours
Student Level:
This course is open to students on the college level in either the Freshman or Sophomore year.
Catalog Description:
CIS1871 - Discrete Structures I (3 hrs.)
This course introduces foundational mathematical concepts essential for computer science, including logic, proof techniques, set theory, functions, number theory, matrices, and counting principles. Students will develop problem-solving skills through recursion, induction, and algorithm analysis while applying mathematical reasoning to real-world computational challenges.
Course Classification: Lecture
Prerequisites:
MTH4435 Calculus I
Co-requisites:
None
Controlling Purpose:
This course provides students with a foundational understanding of discrete mathematics and its applications in computational problem-solving. Through the study of propositional and predicate logic, proof techniques, set theory, functions, number theory, matrices, and counting principles, students will develop the mathematical reasoning skills necessary for algorithm design and analysis. The course emphasizes problem-solving strategies, including recursion, induction, and cryptographic functions, preparing students to apply these concepts to real-world computing challenges. By integrating mathematical principles with software development, students will gain proficiency in translating abstract concepts into practical implementations, fostering a deeper comprehension of computational theory and its role in computer science.
Learner Outcomes:
Upon completion of the course, the student will:
- Exhibit proficiency in propositional and predicate logic by translating between natural language statements and symbolic representations, including operators and quantifiers.
- Utilize various proof techniques and strategies to verify mathematical statements.
- Demonstrate a strong understanding of Naïve Set Theory, including set representations, operations, and the cardinality of both finite and infinite sets.
- Illustrate and describe the properties of functions, sequences, and series.
- Perform operations involving matrices and zero-one matrices.
- Show competence in Number Theory concepts such as the division algorithm, divisibility rules, and modular arithmetic.
- Work with integer representations and operations, and establish key properties of prime numbers through proofs.
- Apply cryptographic functions in problem-solving and encryption techniques.
- Develop a solid grasp of recursion and mathematical induction, demonstrating their applications in computational problems.
- Use mathematical induction effectively in proofs and problem-solving scenarios.
- Implement fundamental and advanced counting principles, including the pigeonhole principle, permutations, combinations, and the Binomial Theorem.
- Design, analyze, and implement algorithms using mathematical reasoning, applying them to real-world computational challenges by developing software solutions.
Unit Outcomes for Criterion Based Evaluation:
The following outline defines the minimum core content not including the final examination period. Instructors may add other material as time allows.
UNIT 1: Propositional and Predicate Logic
Outcomes: Upon completion of this unit, students will be able to:
- Translate natural language statements into symbolic representations using propositional and predicate logic.
- Apply logical operators and quantifiers to construct well-formed logical expressions.
- Analyze logical statements for validity and equivalence.
UNIT 2: Proof Techniques and Mathematical Reasoning
Outcomes: Upon completion of this unit, students will be able to:
- Utilize direct, indirect, and contradiction-based proof techniques to verify mathematical statements.
- Construct and evaluate proofs using mathematical logic.
- Apply proof strategies to solve abstract and applied mathematical problems.
UNIT 3: Naïve Set Theory
Outcomes: Upon completion of this unit, students will be able to:
- Define and represent sets using different notations.
- Perform operations such as union, intersection, complement, and Cartesian products.
- Analyze the cardinality of finite and infinite sets.
UNIT 4: Functions, Sequences, and Series
Outcomes: Upon completion of this unit, students will be able to:
- Define and analyze properties of functions, including injectivity, surjectivity, and bijectivity.
- Illustrate and compute terms in arithmetic and geometric sequences.
- Evaluate series and apply convergence criteria.
UNIT 5: Matrix Operations and Zero-One Matrices
Outcomes: Upon completion of this unit, students will be able to:
- Perform basic matrix operations such as addition, multiplication, and inversion.
- Apply zero-one matrices in relational problems and graph representations.
- Use matrices to model and solve computational problems.
UNIT 6: Number Theory and Modular Arithmetic
Outcomes: Upon completion of this unit, students will be able to:
- Apply the division algorithm and divisibility rules in integer arithmetic.
- Perform operations using modular arithmetic.
- Prove key number theory concepts related to prime numbers and integer properties.
UNIT 7: Integer Representations and Prime Numbers
Outcomes: Upon completion of this unit, students will be able to:
- Represent integers in different numeral systems.
- Establish key properties of prime numbers using formal proofs.
- Apply number theory concepts in computational applications.
UNIT 8: Cryptography and Encryption Techniques
Outcomes: Upon completion of this unit, students will be able to:
- Apply cryptographic functions such as hashing and encryption.
- Utilize modular arithmetic in cryptographic algorithms.
- Analyze real-world applications of encryption in data security.
UNIT 9: Recursion and Mathematical Induction
Outcomes: Upon completion of this unit, students will be able to:
- Define and implement recursive solutions for computational problems.
- Use mathematical induction to prove mathematical and algorithmic statements.
- Apply recursion and induction in algorithm design.
UNIT 10: Advanced Counting Principles
Outcomes: Upon completion of this unit, students will be able to:
- Apply the pigeonhole principle to problem-solving scenarios.
- Compute permutations and combinations for counting problems.
- Utilize the Binomial Theorem in algebraic expansions.
UNIT 11: Algorithm Design and Mathematical Reasoning
Outcomes: Upon completion of this unit, students will be able to:
- Design and analyze algorithms using mathematical reasoning.
- Implement algorithms that solve real-world computational challenges.
- Develop software solutions that integrate mathematical problem-solving techniques.
Projects Required:
Varies, refer to syllabus.
Textbook:
Contact Bookstore for current textbook.
Materials/Equipment Required:
None
Attendance Policy:
Students should adhere to the attendance policy outlined by the instructor in the course syllabus.
Grading Policy:
The grading policy will be outlined by the instructor in the course syllabus.
Maximum class size:
Based on classroom occupancy
Course Time Frame:
The U.S. Department of Education, Higher Learning Commission and the Kansas Board of Regents define credit hour and have specific regulations that the college must follow when developing, teaching and assessing the educational aspects of the college. A credit hour is an amount of work represented in intended learning outcomes and verified by evidence of student achievement that is an institutionally-established equivalency that reasonably approximates not less than one hour of classroom or direct faculty instruction and a minimum of two hours of out-of-class student work for approximately fifteen weeks for one semester hour of credit or an equivalent amount of work over a different amount of time. The number of semester hours of credit allowed for each distance education or blended hybrid courses shall be assigned by the college based on the amount of time needed to achieve the same course outcomes in a purely face-to-face format.
Refer to the following policies:
402.00 Academic Code of Conduct
263.00 Student Appeal of Course Grades
403.00 Student Code of Conduct
Accessibility Services Program:
Cowley College, in recognition of state and federal laws, accommodates all students with a documented disability. If a student has a disability that will impact their ability to be successful in this course, please contact the Student Accessibility Coordinator for the needed accommodations.
DISCLAIMER: THIS INFORMATION IS SUBJECT TO CHANGE. FOR THE OFFICIAL COURSE PROCEDURE CONTACT ACADEMIC AFFAIRS.
|
