ICS 141: Discrete Mathematics for Computer Science I

Description: Logic, sets, functions, matrices, algorithmic concepts, mathematical reasoning, recursion, counting techniques, probability theory. FS

Objectives: This course covers mathematical topics such as logic, set theory, algorithms, mathematical reasoning, counting, combinatorics, and probability theory. A strong understanding of these topics is essential for problem solving, computer programming, data structures, algorithms, language translation, networking, computer architecture, operating systems, database, and software engineering.

Course Learning Outcomes

• Understand foundations of mathematics and symbolic techniques in the context of problem solving.
• Apply formal methods of symbolic propositional and predicate logic.
• Learn about the algebra of sets, functions, sequences, and summations.
• Understand the formal metrics for measuring the growth of functions (big-O, Ω, and Ө) and apply these metrics to analyzing the complexity of algorithms (both iterative and recursive algorithms).
• Learn how numbers are represented in binary and other bases, and as a product of primes.
• Understand mathematical reasoning by understanding and exercising several proof techniques, such as direct proofs, proof by counterexample, proof by contraposition, proof by contradiction, mathematical induction, and strong induction.
• Demonstrate basic counting principles, compute permutations and combinations, and interpret the meaning in the context of the particular application.
• Understand discrete probability concepts – calculate probabilities of events and expectations of random variables, differentiate between dependent and independent events, understand and apply Bayes theorem to dependent events.

Program Learning Outcomes

• a. Students can apply knowledge of computing and mathematics appropriate to the discipline
• b. Students can analyze a problem, and identify and define the computing requirements appropriate to its solution
• c. Students can design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs

Textbook(s): K. H. Rosen, Discrete Mathematics and Its Applications, 7th Edition, McGraw Hill

Grading: Homework assignments: 20% Midterm exam I, II: 45% (22.5% for each) Final exam: 25% Recitation attendance: 10%

Policies: No makeup exams will be given unless the instructor is provided with official documented proof of an emergency that prevented you from attending the exam. In the case of an emergency, the instructor must be contacted within 48 hours after the absence. Homework assignment is due at the beginning of class on the assigned due date. If you hand in late work without approval of the instructor you may receive zero credit. Late submission may be accepted on a case by case basis for up to 24 hours after the due with 40% penalty for lateness without exception. Cooperation on Assignments Cheating and plagiarism as defined in the University Catalog will result with an F for the class and the incident will be reported to the ICS Department Chair for further action. This policy will be applied to those who copy other’s work and who allow their work to be copied. You are allowed to discuss strategies for solving homework assignments with other students, however collaboration on solutions/codes, sharing or copying of solutions/codes is not allowed. This policy will be strictly enforced. You may consult public literature (books, articles, etc.) for information, but you must cite each source of ideas you adopt. Electronic video and/or audio recording is not permitted during this class.

Schedule

• Week 1: Introduction, Propositional Logic
• Week 2: Propositional Equivalences, Predicates and Quantifiers
• Week 3: Nested Quantifiers, Rules of Inference
• Week 4: Proofs, Sets
• Week 5: Set Operators, Functions
• Week 6: Exam I, Functions
• Week 7: Sequences and Summations, Matrices
• Week 8: Algorithms, Growth of Functions
• Week 9: Complexity of Algorithms
• Week 10: Divisibility, Integers and Algorithms, Primes and GCD
• Week 11: Mathematical Induction, Exam II
• Week 12: Recursive Definitions
• Week 13: Recursive Algorithms, Basics of Counting
• Week 14: Permutations and Combinations
• Week 15: Discrete Probability, Bayes’ Theorem,
• Week 16: Expected Value and Variances
• Week 17: Final Exam