## Mathematical Foundations of Computer Engineering

(3-0-0-3)

**CMPE Degree:** This course is Required for the CMPE degree.

**EE Degree:** This course is Elective for the EE degree.

**Lab Hours:** 0 supervised lab hours and 0 unsupervised lab hours.

**Technical Interest Group(s) / Course Type(s):** BSCmpE core (2012-13 curriculum), Computer Systems and Software

**Course Coordinator:**

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

Foundations of Computer Science, C Edition### Course Outcomes

- Use proof techniques, such as induction, to prove mathematical lemmas,
- Analyze the running times of iterative and recursive algorithms
- Solve counting problems involving permutations, combinations, and selections
- Apply probabilistic methods to the design and analysis of randomized algorithms
- Design algorithms and write programs for constructing and manipulating common data abstractions, e.g. lists, trees, and graphs
- Analyze the running times of common algorithms for trees, graphs, and networks,
- Use a context-free grammar to define the syntax of a simple programming language
- Choose appropriate data abstractions and apply discrete math concepts in solving multiple types of electrical and computer engineering problems

### Student Outcomes

In the parentheses for each Student Outcome:"P" for primary indicates the outcome is a major focus of the entire course.

“M” for moderate indicates the outcome is the focus of at least one component of the course, but not majority of course material.

“LN” for “little to none” indicates that the course does not contribute significantly to this outcome.

1. ( P ) An ability to identify, formulate, and solve complex engineering problems by applying principles of engineering, science, and mathematics

2. ( LN ) An ability to apply engineering design to produce solutions that meet specified needs with consideration of public health, safety, and welfare, as well as global, cultural, social, environmental, and economic factors

3. ( LN ) An ability to communicate effectively with a range of audiences

4. ( LN ) An ability to recognize ethical and professional responsibilities in engineering situations and make informed judgments, which must consider the impact of engineering solutions in global, economic, environmental, and societal contexts

5. ( LN ) An ability to function effectively on a team whose members together provide leadership, create a collaborative and inclusive environment, establish goals, plan tasks, and meet objectives

6. ( P ) An ability to develop and conduct appropriate experimentation, analyze and interpret data, and use engineering judgment to draw conclusions

7. ( M ) An ability to acquire and apply new knowledge as needed, using appropriate learning strategies.

### Strategic Performance Indicators (SPIs)

Not Applicable

### Course Objectives

### 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.