ENEE: 641 Mathematical Foundations for Computer Engineering
Course Goals:Mathematical modeling, design, analysis, and proof techniques related to computer engineering. Probability, logic, combinatorics, set theory, and graph theory, as they pertain to the design and performance of computer engineering systems. Techniques for the design and analysis of efficient computational methods from graph theory and networks. Understanding of the limits on the efficiency of such computational methods. Translation from mathematical theory to actual programming. The course emphasizes mathematical rigor.
Topics Prerequisite(s):Properties of functions and counting principles, relations, equivalence relations, partial orders and related topics, asymptotic notation and recurrences, elementary sorting methods, knowledge of C, and basic calculus.
Core Topics:- Growth of functions.
- Propositional and predicate logic.
- Counting and probability.
- State machines and automata.
- Recursion and recursive descriptions.
- Organizations of data.
- Computational methods: Dynamic programming and the greedy approach.
- Graph theory and computational methods.
- Uses of randomization.
- Combinatorial optimization.
- Apparent hardness of problems; practical ways for proving apparent hardness; heuristics and other approaches for coping with apparent hardness.
- Pattern matching (optional topic).
- Geometry computations (optional topic).
The presentation will provide computer engineering context to the core topics covered.
October 16, 2001, Professor Uzi Vishkin.