ECE Course Outline

ECE3020

Mathematical Foundations of Computer Engineering (3-0-3)

Prerequisites
(ECE 2035 or ECE 2036) and (Math 2401/2411/24X1 or Math 2403/2413/24X3) [all courses min C]
Corequisites
None
Catalog Description
Fundamental concepts in discrete mathematics and their efficient realization via algorithms, data structures, computer programs, and hardware. Discussion of engineering and computational applications.
Textbook(s)
Aho & Ullman, Foundations of Computer Science, C Edition (C edition edition), Freeman, 1994. ISBN 0716782847, ISBN 978-0716782841 (required) (comment: available free online at http://infolab.stanford.edu/~ullman/focs.html )

Topical Outline
1.	Iteration and Recursion
   a.	Iteration
   b.	Mathematical induction
   c.	Recursion
   d.	Recurrence equations
   e.	Computational complexity.
   f.	Example applications: parity coding, fast Fourier transform, complexity analysis of recursive programs.

2.	Combinatorics and Probabilistic Methods
   a.	Permutations
   b.	Selections
   c.	Inclusion-exclusion
   d.	Probability spaces
   e.	Conditional probability
   f.	Independence
   g.	Expectation.
   h.	Example applications: expected running time, Monte Carlo methods, randomized algorithms.

3.	Data abstractions
   a.	Trees
   b.	Lists
   c.	Sets
   d.	Relational data
   e.	Graphs
   f.	Example applications: network flow, circuit partitioning and routing, Huffman codes, decoding of error control codes.

4.	Advanced Topics
   a.	Automata theory
   b.	state minimization
   c.	regular expressions
   d.	context-free grammars.
   e.	Example applications: state machine design, pattern matching, parsing for compilation.