List of Topics :
1. Basic mathematical objects (3 lectures)
Sets (finite, countable, uncountable, operations)
Functions (properties, special classes)
Relations (binary relations, composition, closure, equivalence relations)
Uses and applications in computer science
2. Logic (4 lectures)
Propositional equivalences, predicates, quantifiers
Boolean logic and algebraic properties of boolean functions
Logic circuits
Minimization of logic expressions
3. Number Representations (3 lectures)
Number systems, representation of integers
Floating point numbers and directed rounding
Operations on integers, rational arithmetic
4. Discrete probability (3 lectures)
Sample space, events
Probability distributions
Conditional probability, expectation
Average case analysis of programs
5. Recursion (6 lectures)
Big-O notation and manipulations
Recursive definitions
Recurrence relations
Recursive programs: design and implementation
6. Proof techniques (6 lectures)
Mathematical and structural induction
Contradiction
Construction
Pigeon-hole principle
Diagonalization
7. Finite state machines (5 lectures)
Equivalence with regular languages and regular expressions
State minimization
Closure properties
Nondeterministic machines
Pumping lemma for regular languages
Applications and uses in Computer Science (involves programming)
8. Languages and strings (2 lectures)
Operations
Properties
9. Pushdown automata (3 lectures)
Informal description
Context-free languages
Ambiguous and unambiguous grammars and languages
Introduction to parsing (involves programming)
10. Asymptotics and complexity (3 lectures)
Important complexity classes
Classes P and NP, NP-complete
11. Computability and Undecidability (4 lectures)
Limits of computation
Turing machines
Cellular automata
Church-Turing thesis
Undecidability (Halting problem)
12. Future Computing Trends (1 lecture)
Distributed/networked computing
DNA computing
Quantum computing
2001.03
