Carnegie Mellon University Website Home Page
 
Back

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