: Mathematical Foundations for Computer Engineering -- ENEE 641
Introduction:
The evolving discipline of computer engineering requires increasing
mathematical knowledge and sophistication.
Electronic design needs efficient computational methods, and its verification
a high level of mathematical rigor. More specifically,
computer aided design of digital systems and their verification are heavily
based on mathematical
computational methods and requires profound understanding of their efficiency a
nd
apparent hardness
concepts. Layout, logic, and architectural-level synthesis are
almost entirely based on computational techniques.
Compilers are playing a dominant role in computing systems in general
including the embedded systems area.
Compilers must be correct and should be efficiently implemented.
Insuring correctness and efficiency require profound mathematical
understanding.
Communication networks is another electrical and computer engineering
domain where the understanding of mathematical computational methods and their
efficiency is important.
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.
Course Prerequisite(s):
None.
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.
Textbook
Introduction to Algorithms, T.H. Cormen,
C.E. Leiserson, R.L. Rivest and C. Stein,
McGraw-Hill, Second Edition, 2001. ISBN 0-07-013151-1
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.
Last Updated:
October 16, 2001, Professor Uzi Vishkin.
khodary@eng.umd.edu