Ph.D. Reading List

Prospective Ph.D. students will be responsible for taking the three "core" exams as well as "one" exam from the application areas. The reading material associated with these exams is listed below.

Study material for the three "core" Ph.D. exams:

• Systems
• Programming Languages
• Theory

Study material for the application areas:

• Data Management
• Software Engineering

Books

• Abel, Peter. IBM PC Assembly Language and Programming, Fifth Edition, Prentice Hall, 2001.
  • Basic Features of the IBM PC System Architecture
  • Instruction Addressing and Execution
  • Examining Computer Memory and Executing Instructions with a Debugger
  • Assembly Language Directives
  • Assembling, Linking, and Executing Process
  • Memory Management - Real vs. Protected Addressing
  • Program Logic and Control
  • Video System Components and Modes
  • Processing String Data with Mov Instruction
  • Processing Binary Data with Add/Sub and Mul/Div
• Tanenbaum, Andrew S. Structured Computer Organization, Fourth Edition, Prentice Hall, 1999.
  • Processor Memory Switch Notation
  • Bus Protocol and Organization
  • Digital Logic Design
  • Microarchitecture Design
  • Instruction Set Architecture
  • Operating System Machine
  • Assembly Language
• Tanenbaum, Andrew S. Modern Operating Systems, Second Edition, Prentice Hall, 2001.
  • Processes and Threads
  • Deadlocks
  • Memory Management
  • Input/Output
  • File Systems
  • System Abstrations
  • Multiple Processor Systems
  • Security
  • Case Study 1: UNIX and Linux
  • Case Study 2: Windows 2000
  • Operating System Design

Articles

• Scheifler, R. and Gettys, J. The X Window System. ACM Transactions on Graphics 5, 2(April, 1986) pages 79-109.
• Scheifler, R., Gettys, J., and Newman R. X Windows System, 2nd Edition. Digital Press, 1990.
• Thompson, Ken. Reflections on Trusting Trust. CACM 27, 8 (August 1984) pages 761-763. http://www.acm.org/classics/sep95/
• Lampson, B.W. Hints for Computer System Design, Proceedings of the 9^th Symposium on Operating Systems Principles, October 1983, pp. 33-48. http://research.microsoft.com/~lampson/33-Hints/WebPage.html

Sample Exam Questions

Books

• Pratt, Terrance W. and Zelkowitz, Marvin V. Programming Languages Design and Implementation, Third Edition, Prentice Hall, 1996.
• Linz, Peter. An Introduction to Formal Languages and Automata, Second Edition, Jones and Bartlett, 1977.
  • Introduction to the Theory of Computation (pp. 14-36)
  • Finite Automata (pp. 37-64)
  • Regular Expressions and Regular Grammars (pp. 73-100)
  • Indentifying Non-regular Languages (pp. 117-127)
  • Context-Free Languages (pp. 129-154)
  • Push Down Automata (pp.181-206)
  • Turing Machines (pp.229-256)

Articles

History and Paradigms

• Wirth, N. "Programming Languages: What to demand and how to access them." Paper presented at the Symposium on Software Engineering, Belfast, Ireland, 8-9 April 1976.
• Hanson, David R. "Is Block Structure Necessary?", Software Practice and Experience, 11,1981, (pp. 853-866).
• Denning, Peter J. "Working Sets Past and Present", IEEE Software Engineering, 6, 1 January 1980, pp. 64-82.

Paradigm

• Floyd, Robert W. "The Paradigms of Programming", Communications of the ACM, 22, 8 August 1979, pp. 455-460.

Object Oriented Paradigm

• Stefik, Marck and Bobrow, Daniel G. "Object Oriented Programming: Themes and Variations", The AI Magazine, 6, 4, 1986, pp. 40-60.
• Khan, Emdad H., Mansoor Al-A'ali, Moheb R. Girgis, "Object-Oriented Programming for Structured Procedural Programmers", IEEE Computer, 1995, pp. 48-57.
• Hamilton, Mark A., "Java and the Shift to Net-Centric Computing", IEEE Computer, August 1996, pp. 31-39.
• Wasserman and Gutz, "The Future of Programming", Communications of the ACM, 25, 3, March 1982, pp. 196-205.
• Ingals, Daniel, "Design Principles Behind SmallTalk", BYTE, August 1981, pp. 286-298.

Block Structured Paradigm

• Wirth, N. "The Design of a Pascal Compiler", Software - Practice and Experience, 4, 1971, pp. 309-333.
• Hoare, Charles, "The Emperor's Old Clothes", Communication of the ACM, 24, 2 February 1981, pp. 75-83.

Functional Paradigm

• Hudak, Paul, "Conception Evolution, and Application of Functional Programming Languages'", Computing Surveys, Vol. 21, No. 3, September 1989.
• Winograd, Terry, "Beyond Programming Languages", Communications of the ACM, 22, 7 July 1979, pp. 391-401.
• Backus, John, "Is Computer Science Based on the Wrong Fundamental Concept of 'Program'? An Extended Concept", IFIP, 1981, pp. 133-165.

Logic Paradigm

• Davis, Ruth E., "Logic Programming and Prolog: A Tutorial", IEEE Software, 2, 5 September 1985, pp. 53-62.

• Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis. Prentice Hall, 1997. (C++)
            OR
• Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis, Java Edition. Prentice Hall, 1998.
  • Chapter 1: Data Structures and Algorithms
  • Chapter 2: Mathematical Preliminaries
  • Chapter 3: Algorithm Analysis
  • Chapter 4: Lists, Stacks and queues
  • Chapter 5: Binary Trees
  • Chapter 6: General Trees
  • Chapter 7: Graphs
  • Chapter 8: Internal Sorting
  • Chapter 9: File Processing and External Sorting
  • Chapter 10: Searching
  • Chapter 11: Indexing
  • Chapter 14: Analysis Techniques
• Aho, Alfred V., Hopcroft, John E., and Ullman, Jeffrey D. Data Structures and Algorithms. Addison-Wesley, 1983.
  • Chapter 10: Algorithm Design Techniques (pp. 306-346)
• Garey, Michael R. and Johnson, David S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
  • Chapter 1: Computers, Complexity, and Intractability (pp. 1-15)
  • Chapter 2: The Theory of NP-Completeness (pp. 17-44)
• Meyer, Bertrand. Object-Oriented Software Construction, Second Edition. Prentice Hall, 1997.
  • Chapter 6: Abstract Data Types, Sections 6.1-6.6 (pp. 121-148).
  • Chapter 11: Design by contract: Building Reliable Software, Sections 11.1-11.12 (pp.331-388)
  • Chapter 16: Inheritance Techniques. Section 16.1 (pp. 569-580)
• Harel, David. Algorithmics: The Spirit of Computing, Second Edition. Addison Wesley, 1992.
  • Chapter 8: Noncomputability and undecidability (pp. 195-222)

Articles

• J. Bentley. "Programming Pearls: Little Languages," Communications of the ACM, Vol. 29, No. 8, pp. 711-721, August 1986. Also appears in J. Bentley, More Programming Pearls: Confessions of a Coder, Addison Wesley, 1988.
• B. Blum. "The Process," Chapter 1 in Software Engineering, Oxford University Press, New York, 1992.
• B. W. Boehm. "A Spiral Model of Software Engineering," IEEE Computer, Vol. 21, No. 4, pp. 61-72, May 1988.
• Selections from F. P. Brooks, Jr. The Mythical Man Month: Essays on Software Engineering, Anniversary Edition, Addison Wesley, 1995.
  • (Chapter 2) F. P. Brooks, Jr. "The Mythical Man-Month," pp. 13-28.
  • (Chapter 4) F. P. Brooks, Jr. "The Second-System Effect," pp. 53-60.
  • (Chapter 16) F. P. Brooks, Jr. "No Silver Bullet--Essence and Accident in Software Engineering," pp. 177-204. Also appeared in IEEE Computer, Vol. 20, No. 4, pp. 10-19, April 1987.
  • (Chapter 17) F. P. Brooks, Jr. "'No Silver Bullet' Refired," pp. 205-226.
  • (Chapter 19) F. P. Brooks, Jr. "The Mythical Man-Month After 20 Years," pp. 253-289.
• J. Coplien, D. Hoffman, and D. Weiss. "Commonality and Variability in Software Engineering," IEEE Software, Vol. 15, No. 6, pp. 37-45, November/December 1998.
• D. Garlan, R. Allen, and J. Ockerbloom. "Architectural Mismatch: Why Reuse is So Hard," IEEE Software, Vol. 12, No. 6, November 1995.
• C.A.R. Hoare. "An Axiomatic Basis for Computer Programming," Communications of the ACM, Vol. 12, pp. 576-580, 1969. Also reprinted in Vol. 26, No. 1, pp. 53-56, January 1983.
• R. E. Johnson and B. Foote. "Designing Reusable Classes," Journal of Object-Oriented Programming, Vol. 1, No. 12, pp. 22-35, June/July 1988. Also available as http://www.laputan.org/drc/drc.html.
• N. G. Leveson and C. S. Turner. "An Investigation of the Therac-25 Accidents," IEEE Computer, Vol. 26, No. 7, pp. 18-41, July 1993.
• B. Liskov and S. Zilles. "Specification Techniques for Data Abstractions," IEEE Transactions on Software Engineering, Vol. SE-1, No. 1, pp. 7-19, March 1975.
• D. L. Parnas papers from: D. M. Hoffman and D. M. Weiss, editors. Software Fundamentals: Collected Papers of David L. Parnas, Addison Wesley, 2001.
  • (Chapter 7) D. L. Parnas. "On the Criteria to Be Used in Decomposing Systems into Modules," Communications of the ACM, Vol. 15, No. 12, pp. 1053-1058, December 1972.
  • (Chapter 10) D. L. Parnas. "On the Design and Development of Program Families," IEEE Transactions on Software Engineering, Vol. SE-2, No. 1, pp. 1-9, March 1976.
  • (Chapter 14) D. L. Parnas. "Designing Software for Ease of Extension and Contraction," IEEE Transactions on Software Engineering, Vol. SE-5, No. 1, pp. 128-138, March 1979.
  • (Chapter 15) K. H. Britton, R. A. Parker, and D. L. Parnas. "A Procedure for Designing Abstract Interfaces for Device Interface Modules," Proceedings of the Fifth International Conference on Software Engineering, pp. 195-204, March 1981.
  • (Chapter 16) D. L. Parnas, P. C. Clements, and D. M. Weiss. "The Modular Structure of Complex Systems," IEEE Transactions on Software Engineering, Vol. SE-11, No. 3, pp. 259-266, March 1985.

• D. S. Rosenblum. "A Practical Approach to Programming with Assertions," IEEE Transactions on Software Engineering, Vol. 21, No. 1, pp. 19-31, January 1995.
• M. Shaw. "Prospects for an Engineering Discipline of Software," IEEE Software, Vol. 7, No. 6, pp. 15-24, November 1990.
• J. Vlissides. "Designing with Patterns," In Pattern Hatching: Design Patterns Applied, Addison-Wesley, 1998.
• J. A. Whittaker. "What is Software Testing? And Why Is It So Hard?" IEEE Software, Vol. 17, No. 1, pp. 70-79, January/February 2000.
• J. M. Wing. "A Specifier's Introduction to Formal Methods," IEEE Computer, Vol. 23, No. 9, pp. 8-24, September 1990.
• N. Wirth. "Program Development by Stepwise Refinement," Communications of the ACM, Vol. 14, No. 4, April 1971.

top

---

Data Management

Books

• Date, C.J. An Introduction to Database Systems, Addison-Wesley, Seventh edition, 2000, ISBN 0-201-38590-2 This is a standard introduction to database management systems, especially relational systems.
• Manning, C.D., Raghavan, P., Schutze, H., Cambridge University Press, 2008, ISBN 0521865719. Chapters 6 and 8.

Articles

• Comer, D. "The Ubiquitous B-Tree", Computing Surveys, 11(2):121-137, June 1979.
• Gray, J.N, Lorie, R.A., Putzolu, G.R., and Traiger, I.L. "Granularity of Locks and Degrees of Consistency in a Shared Data Base", IFIP Working Conference on Modelling of Data Base Management Systems, pp. 1-29, AFIPS Press, 1977.
• Gray, J., Chaudhuri, S., Bosworth, A., Layman, A., Reichard, D., and Venkatrao, M. "Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab and Sub-Totals", Data Mining and Knowledge Discovery 1(1):29-53. Kluwer Academic Publishers, 1997.
• Hellerstein, J., Haas, P., and Wang, H. "Online Aggregation", Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, pp. 171-182, ACM, 1997.
• Hellerstein, J., Koutsoupias, E., and Papadimitriou, C. "On the Analysis of Indexing Schemes", International Conference on Management of Data and Symposium on Principles of Database Systems (PODS), 1997.
• Lamb, C., Landis, G., Orenstein, J., and Weinreb, D. "The ObjectStore Database System", Communications of the ACM, 34(10):50-63, ACM, 1991.

top

[ Home | Site Map ]

Last Updated: Wednesday, September 9, 2009, 11:59:06 CST