CS 182: Foundations of Computer Science

Prerequisite:

CS 18000 (Problem Solving and Object-Oriented Programming)

Detailed Syllabus:

1. Logic and Proofs: Propositional equivalences, predicates, quantifiers. Introduction to proofs.

2. Sets, functions, relations, sequences and summations. Sets (finite, countable, uncountable, operations). Functions (properties, special classes). Relations (binary relations, composition, closure, equivalence relations). Sequences and sums. Uses and applications in computer science.

3. Number representations. Number systems and representation of numbers. Floating point numbers and directed rounding. Arithmetic operations. Precision versus accuracy.

4. Counting. Basics of Counting. Pigeon-hole principle. Permutations and combinations.

5. Analysis of algorithm fundamentals. Growth and complexity of functions. Big-O notation and manipulations. Analyzing performance of algorithms.

6. Graphs and trees. Basic properties of trees, directed, and undirected graphs. Traversal strategies for trees and graphs. Modeling problems using graphs and trees.

7. Proof techniques. Proofs by contradiction, construction, and diagonalization. Include proofs related to properties of trees. Mathematical and structural induction.

8. Recursion. Recursive definitions. Recurrence relations. Recursive programs: design and implementation. Pitfalls of recursion.

9. Basic Number Theory, RSA Public Key Cryptosystems.

10. Basic probability.

11. Boolean Logic. Boolean logic and algebraic properties of Boolean functions. Logic circuits. Minimization of logic expressions.

12. Finite state machines. Equivalence of regular languages and regular expressions. State minimization. Closure properties. Nondeterministic machines. Applications and uses in Computer Science.

13. Pushdown automata. Languages and strings. Informal description of a PDA. Context-free languages. Introduction to parsing.

14. Computability and undecidability. Limits of computation, Turing machines, Church-Turing thesis, Classes P and NP, Undecidability (Halting problem).