Mathematical Foundations for Computer Engineering -- ENEE 641, Fall 2013


Dr. Uzi Vishkin
Telephone: 301-405-6763
E-mail: last name at
Office: AVW 2365
Office hours: M 5:00--6:00. By appointment.


Tingyue Gan
Office hours: Tuesday and Thursday 4-5pm in AVW 1145

Course web site:

Dry Homework

Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8

Programming assignment

Programming Assigment
Input graph 1, Input graph 2, Input graph 3, Input graph 4, Input graph 5, Input graph 6, and Input graph 7.


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):


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.


Introduction to Algorithms, T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, McGraw-Hill. Either Second Edition, 2002, ISBN 0-262-03293-7, or Third Edition, 2009, ISBN 978-0-262-03384-8.

Core Topics:

- Growth of functions.
- Propositional and predicate logic.
- Counting and probability.
- 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.
- Parallel algorithms (optional topic).
- Pattern matching (optional topic).
- Geometry computations (optional topic).
The presentation will provide computer engineering context to the core topics covered.


Grading Method:

Homework 10%
Project(s) 5%
Midterm 30%
Final 55%. If your grade in the final is higher than your grade in the midterm, the final grade can be up to 85% of your final grade.

Documented Disability:

If you have a documented disability and wish to discuss academic accommodations with me, please contact me as soon as possible.


Academic dishonesty will not be tolerated. The University Code of Academic Integrity, which can be found at prohibits students from committing the following acts of academic dishonesty: cheating, fabrication, facilitating academic dishonesty, and plagiarism. Academic dishonesty in this class includes outright copying on homework; however, discussing homework problems and exchanging tips is permissible and also encouraged. If there are any take-home exams, discussing the material with anyone, inside or outside of the class, is considered academic dishonesty. Instances of academic dishonesty will be referred to the Office of Judicial Programs.

Last Updated:

August 30, 2013, Professor Uzi Vishkin.