Prerequisite knowledge

Applicants to the MSE program should have a solid understanding of each of the topics listed below. For each topic, a list of suggested readings is provided.

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 structural type equivalence
  • Lifetimes - Stack and heap allocation
  • 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
There are many texts that cover this material. Here are two:

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
© 2003 Carnegie Mellon
Webmaster		 Home   General Information   Admission   Plans Of Study   Curriculum   People   Facilities   Contacts   Login