: Mathematical Foundations for Computer Systems -- ENEE 759F
Dry Homework
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Programming Assignments
Programming Assignment 1
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.
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 (2nd edition), T. H. Cormen, C. E. Leiserson and
R. L. Rivest, McGraw-Hill, 2002. ISBN: 0-07-013151-1
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).
Grading Method:
Homework 10%
Project 5%
Midterm 30%
Final Exam 55%.
If your grade for the final exam is higher than your
midterm grade, the final exam grade can be up to 85% of your final grade.
Last Updated:
September 1, 2001, Professor Uzi Vishkin.
khodary@eng.umd.edu