Course Description
Introduction to analysis of finite collections and mathematical foundations of sequential machines, computer system design, data structures, and algorithms. Includes sets and logic, subscripts, arrays, number systems, counting, recursion, graph theory, trees, nets, and Boolean algebra. IAI: M1 905. IAI: CS 915.
Prerequisite(s)
MATH 1814 with a grade of C or better or appropriate assessment score - Must be completed prior to taking this course.
At the end of this course, students will be able to:
- Apply classical problem-solving strategies in varying circumstances
- Use mathematical theory of discrete systems as it applies to computer programming
- Manipulate sets, sequences, and matrices and perform corresponding operations
- Solve basic counting and probability problems
- Apply various methods of proof (including induction)
- Solve problems using recursive and explicit algorithms
- Identify the costs and benefits of recursion
- Represent the concept of relations in various ways (matrix, ordered pairs, digraphs)
- Apply the concept of function growth to compute and compare the complexity of simple algorithms
- Apply several classical algorithms related to applications of trees and graphs
Topical Outline
1. First Examples of Puzzles and Patterns
2. Number Puzzles and Sequences
3. Truth-Tellers, Liars, and Propositional Logic
4. Predicates
5. Implications
6. Validity of Arguments
7. Mathematical Writing
8. Proofs about Numbers
9. Mathematical Induction
2. Number Puzzles and Sequences
3. Truth-Tellers, Liars, and Propositional Logic
4. Predicates
5. Implications
6. Validity of Arguments
7. Mathematical Writing
8. Proofs about Numbers
9. Mathematical Induction
10. Contradiction and the Pigeonhole Principle
11. Representation of Numbers
12. Set Definitions and Operations
13. More Operations on Sets
14. Proving Set Properties
15. Boolean Algebra
16. Logic Circuits
17. Introduction to Combinatorics
18. Basic Rules for Counting
19. Combinations and the Binomial Theorem
20. Binary Sequences
21. Recursive Counting
22. Solving Recurrence Relations
23. Introduction to Probability
24. Sum and Product Rules for Probability
25. Probability in Games of Chance
26. Expected Value in Games of Chance
27. Graph Theory
28. Isomorphism and Planarity
29. Graphs in Puzzles and Games
30. Binary Trees
31. Hamilton Cycles and the TSP