Yale CS的Reading List
看看你都读过那些
Comprehensive Exam Reading List
Programming Languages and Systems:
1. "Computer architecture: a quantitative approach" Patterson & Hennessy
1 Fundamentals of Computer Design
2 Performance and Cost
3 Instruction Set Design
5 Basic Processor Implementation Techniques
6-6.5 Pipelining
8-8.8 Memory-Hierarchy Design
9-9.8 Input/Output
10 Future Directions
2. One of the following three books would be sufficient to prepare for
the Operating Systems component of the exam.
"Applied Operating System Concepts" A. Silberschatz, P. Galvin, and G. Gagne.
John Wiley & Sons, Inc., 2000.
"Modern operating systems" Tanenbaum
1 What is an Operating System?
2 Processes
3-3.6 Memory Management
4 Files Systems
5-5.2 Input/Output
6 Deadlock
7 Case Study: UNIX
(This is an alternative.)
"Operating Systems, Design and Implementation" Tanenbaum
(This is an alternative.)
3. "Essentials of programming languages" Friedman, Wand & Haynes
1 Tools for Symbolic Programming
2 Induction, Recursion, and Scope
3 Syntactic Abstraction and Data Abstraction
4 Reduction Rules and Imperative Programming
5 Interpreters
6 Parameter Passing
7 Object-Oriented Languages
4. "Compilers: principles, techniques, and tools" Aho, Sethi & Ullman
1 Introduction to Compiling
2 A Simple One-Pass Compiler
3 Lexical Analysis
4 Syntax Analysis
6 Type Checking
7 Run-Time Environments
9.1 Code Generation
10-10.2 Code Optimization
5. "Semantics with Applications: A Formal Introduction." Hanne Riis Nielson,
Flemming Nielson
1 Introduction
2 Operational Semantics
4 Denotational Semantics
(Available at:
http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html
***
Scientific Computing:
Introduction to Scientific Computing. 2nd Edition. Charles Van Loan,
Prentice Hall
Scientific Computing. An Introductory Survey. Second Edition. Michael
Heath. McGraw Hill.
*** AI:
Stuart Russell and Peter Norvig {\it Artificial Intelligence, A Modern
Approach}
A Guided Tour of Computer Vision
V. Nalwa
Addison Wesley, 1993
***
Theory:
Algorithms:
Topics:
analysis of algorithms: proving correctness and running time.
sorting and selection algorithms
data structures: hash tables, binary search trees, $k-{D}$ trees,
union-find, etc.
graph algorithms
combinatorial optimization: greedy algorithms, shortest paths,
dynamic programming, branch-and-bound
References:
Cormen, Leiserson, and Rivest. _Introduction to Algorithms_, MIT
Press, 1990.
Automata and computability theory:
Topics:
regular expressions and languages
finite automata
context-free grammars and languages
pushdown automata
recursive and r.e. languages
Turing machines
computability and undecidability (including diagonalization, the
halting problem, reductions, and Rice's theorem)
References:
Davis, Sigal, and Weyuker. _Computability, Complexity, and Languages_,
Academic Press, Harcourt, Brace & Company, 1994.
or
Floyd and Beigel, _The Language of Machines_, Computer Science Press,
1993.
Complexity theory:
Topics:
NP-completeness (Cormen et al, ch. 36; Davis et al, ch. 15; Floyd
et al, ch. 9; or Papadimitriou, ch. 9)
References:
any one of:
Papadimitriou. _Computational Complexity_, Addison-Wesley, 1994.
Cormen, Leiserson, and Rivest. _Introduction to Algorithms_, MIT
Press, 1990.
Davis, Sigal, and Weyuker. _Computability, Complexity, and Languages_,
Academic Press, Harcourt, Brace & Company, 1994.
Floyd and Beigel, _The Language of Machines_, Computer Science Press,
1993.
Enumeration (counting):
Topics:
permutations, Pascal's triangle, Stirling numbers
Fibonacci numbers, linear recurrences
sieve formulas
asymptotics, order of magnitude
References:
Graham, Knuth, and Patashnik. _Concrete Mathematics; a Foundation
for Computer Science_, Addison-Wesley, 1989.
or
Lovasz. _Combinatorial Problems and Exercises_, North-Holland,
1993 (chapters 1-4).
Graph Theory:
Topics:
graphs, trees, connectivity
flows and matchings
adjacency matrices
References:
or
Bondy and Murty. _Graph Theory with Applications_,
North-Holland, 1976.
