# Prerequisite Knowledge

Applicants to the MSE,MBA/MSE,MSIT-SE and MSIT-ESE programs should have a solid understanding of each of
the topics listed below.

## Data Structures & Algorithms:

- Basic Data Types - Lists, Stacks, Queues, Hash Tables
- Trees - Binary Trees, Tree Traversal
- Memory Management - Storage Allocation, Garbage Collection
- Algorithms - Divide and Conquer, Backtracking, Iterative Techniques, Searching and Sorting
- Complexity - O-Notation

**Recommended Text :**Aho, Hopcroft & Ullman, Data Structures and Algorithms , Addison-Wesley, 1983.
Read all of the book except chapters 6 and 7. In Chapter 9 read only as deep as needed to understand O-notation; work problems of your choosing.

## Programming Languages:

- Abstract and Concrete Syntax
- Simple Type Systems - Arrays, Records, Variants, Recursive Types
- Name and Sructural Type Equivalence
- Lifetimes - Stack and Heap aAlocation
- Pointers, Aliasing, Parameter-Passing Mechanisms
- Lexical and Dynamic Scope
- Abstract Types

**Recommended Text :**David A. Watt, Programming Language Concepts and Paradigms , Prentice Hall International (UK) Ltd, 1990.A good and reasonably terse coverage of the required topics may be found in the first eight chapters of this text.

## Discrete Mathematics:

- Logic - Propositional and Predicate Logic
- Proofs - Inference Rules, Proof Methods
- Set theory - Operations on Sets, Induction, Set Comprehension
- Relations & Functions - Equivalence Relations, Order Relations, Classes of Functions, Composition

**Recommended Text :**Recommended Text 1 :
Stanat and McAllister, Discrete Mathematics in Computer Science , Prentice-Hall, 1977. Logic: Chapters 0, 1.0-1.3 Proofs: Chapters 1.4-1.5 Set theory: Chapter 2 Relations & functions: Chapter 3.4

Recommended Text 2 :
Discrete Mathematics for Computer Science, Saunders College, Toronto, CA ISBN 003-096-5373
This text may be difficult to locate. It can be ordered by phone at 1-800-225-5425 from Holt, Rinehart & Winston, USA. The main information number is 1-800-228-4658.
Set theory: Chapters 2.1-2.3
Logic & proofs: Chapters 3.1-3.3 3.6-3.8 Relations & functions: Chapters 4.1-4.6,5.1-5.3