Carnegie Mellon University

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