ICS 241: Discrete Mathematics for Computer Science II
Description: Program correctness, recurrence relations and their solutions, divide and conquer relations, relations and their properties, graph theory, trees and their applications, Boolean algebra, introduction to formal languages and automata theory. Pre: 141 or consent. FS
Objectives
Course Learning Outcomes
- Students can describe an idea in the language of mathematics clearly and rigorously.
- Students can prove or disprove a given assertion by using proving techniques such as direct proof, indirect proof (proof by contradiction), proof by contrapositive, proof by induction, and proof by construction.
- Students can solve problems on a variety of topics in discrete mathematics such as recurrence systems, relations, counting, graph theory, Boolean algebra, logic circuit design, formal language theory, automata theory, and theory of computation.
- Students can read & write pseudocode of an algorithm in a given grammar expressed in BNF.
- Students can describe a trace of given pseudocode’s execution for a given input.
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
Prerequisites: 141 or consent.
Textbook(s): Kenneth H. Rosen, Discrete Mathematics and Its Applications, 7th Edition, McGraw-Hill, 2012.
Grading: 10% in-class exercises
90% midterms and final.
Schedule
- Week 1: Boolean Algebra
- Week 2: Logic Circuits
- Week 3: Linear Algebra
- Week 4: Relations
- Week 5: Graphs, Midterm
- Week 6: Graphs
- Week 7: Graphs
- Week 8: Trees
- Week 9: Trees
- Week 10: Recurrences
- Week 11: Counting
- Week 12: Formal Languages
- Week 13: Regular expressions, Midterm
- Week 14: Turing machines
- Week 15: Predicate logic
- Week 16: Review
- Week 17: Final Exam