ENEE 759F: Mathematical Foundations for Computer Systems

Course Goals:

Mathematical modeling, design, analysis, and proof techniques related to computer systems. Probability, logic, combinatorics, set theory, and graph theory, as they pertain to the design and performance of computer systems. Techniques for the design and analysis of algorithms and data structures. Study of efficient algorithms from areas such as graph theory and networks. Translation from mathematical theory to actual programming. Understanding of the inherent complexity of problems: polynomial time, NP-completeness and approximation algorithms. The course emphasizes mathematical rigor.

Course Prerequisite(s):

ENEE 450, or permission of instructor.

Topics Prerequisite(s):

Properties of functions and counting principles, relations, equivalence relations, partial orders and related topics, asymptotic notation and recurrences, elementary to sorting algorithms, knowledge of C, and basic calculus.

Textbook(s)

Introduction to Algorithms, T. H. Cormen, C. E. Leiserson and R. L. Rivest, McGraw-Hill, 1990.

Reference(s):

1. Foundations of Computer Science. A.V. Aho and J.D. Ullman, Computer Science Press, 1992.
2. Elements of Discrete Mathematics, C.L. Liu, McGraw Hill, 1985.
3. Fundamentals of Algorithmics, G. Brassard and P. Bratley, Prentice Hall, 1996.

Core Topics:

- Growth of functions.
- Propositional and predicate logic.
- Counting and probability.
- State machines and automata.
- Recursion and recursive descriptions.
- Data structures, sorting and hashing.
- Dynamic programming.
- Greedy algorithms.
- Graph theory and graph algorithms.
- Uses of randomization.
- Combinatorial optimization.
- NP-completeness and approximation algorithms.

Optional Topics:

- Pattern matching algorithms (optional topic).
- Algorithms from computational geometry (optional topic).

Course Structure:

The course will be taught for the first time in Fall'99. Its structure is to be determined.

Grading Method:

Homework 10%
Project 5%
Midterm 30%
Final Exam 55%

Last Updated:

November 10, 1998, Professor Uzi Vishkin.

khodary@eng.umd.edu