USC Computer Science and Engineering Department
Qualifying Examination Information Page
FOR FALL 2020: Dr. Fenner is on Sabbatical, and
Dr. O'Kane is the acting Q-Exam Committee Chair
This page contains basic general information about the qualifying
Core Topics (see below for specialty research topics)
Algorithms (CSCE 750): Introduction to Algorithms (2nd ed.) by
Cormen, Leiserson, Rivest, and Stein
Please note: Starting Fall 2014, NP-completeness
will no longer be tested in the Algorithms section of the exam; it
will be tested in the Theory section.
Foundations: chapters 1-4, 5-9 recurrences, sorts and order statistics
Trees: chapters 12-13, search trees, red-black trees
Dynamic Programming and Greedy Algorithms: chapters 15-16
Graph Algorithms: chapters 22-24
Parallel Computing: refer to the
lecture notes on Dr. Buell's web sites for 750. (Please note that some links
on this page may no
longer be valid due to changes in its directory structure.)
For further reference see Dr. Buell's website (above) and Dr. Fenner's
CSCE 750 website
Architecture (CSCE 513): Computer Architecture: A Quantitative Approach,
3rd ed. Hennessey and Patterson, Morgan Kaufman, Chapters 1-5,
8.1-8.5, Appendix A
Fundamentals of Computer Design
Instruction Level parallelism
Loop unrolling and static techniques
Memory Hierarchy design
Compilers (CSCE 531): Compilers: Principles, Techniques, &
Tools (2nd ed.) by Aho, Lam, Sethi, and Ullman, Addison-Wesley,
For further information see
Fenner's CSCE 531 website
Intermediate Code Generation
Theory (CSCE 551): Introduction to the Theory of
Computation (1st, 2nd, or 3rd ed.) by M. Sipser, PWS, Chapters
1,3-5,7-8. The main difference between the first two editions is that
the 2nd edition contains solutions to selected exercises and problems.
The 3rd edition adds new material in Chapter 2, which is not covered
by the exam.
Please note: Starting Fall 2014, NP-completeness
is included among potential topics covered in the Theory section.
Finite Automata, Regular Expressions, Properties of Regular Languages
Turing Machines, Decidability, Reductions
Time Complexity and NP-Complete Problems
For further information see
Fenner's CSCE 551 website
Specialty research topics
Computer Security (CSCE 522): Follow
this link. For
further information see Dr. Farkas's CSCE 522 website.
Pattern Classification (CSCE 768): Follow
Data Mining (CSCE 822): Follow this link.
Databases (CSCE 520): Chapters 1 through 8 of A First Course in
Database Systems by J. Ullman and J. Widom.
Core areas of some past exams
Guidelines for Students
The qualifying exam is given once each semester. You are expected to
have passed the exam by the end of your second year in the Ph.D. program.
The exam consists of three sessions, each lasting an hour and 45
minutes, on three respective topics:
The first two items above are called core topics, and questions
from these topics in some past exams are given through the links
- your choice of either Compilers (CSCE 531) or Architecture (CSCE
- your choice of either Algorithms (CSCE 750) or Theory (CSCE 551),
- your chosen research area.
Each topic contains three numbered questions, which are weighted
equally. You are to submit an answer to your choice of two of these
questions. Do NOT answer all three questions! If you do, the
committee reserves the right to discard one of your answers
The exam is closed-book, closed notes. No written, printed, or
electronic materials or communication of any kind is allowed.
Answering the Questions
For each topic, you will be given a code to use to identify your answers.
We will be scanning and rearranging your exam pages as part of our
archiving. To facilitate this process, we will expect you to adhere to
the following guidelines for your submitted answers:
For core topics at least, your exam will be graded by two faculty
- Use paper with borders (the department will provide these).
- Write your CODE IN BOX, Subject Area, e.g. Compilers, Question
Number, and Page number of your solution on the top of each and every
- Use a separate page for each question.
- Keep your pages together with the question you are answering, if
an answer uses multiple pages, please indicate the page number in the
blank provided at the top of each page.
- Use a dark pencil or dark ink pen for your answers.
- Do not write outside the printed border of the page (the scanner
may not pick it up).
- Do not write on the back of the page.
- PLEASE DO NOT TURN IN YOUR STRATCH PAPER along with your answers.
What constitutes a pass?
There are three possible outcomes from taking the exam:
Current department policy allows only one retake of the exam, so not
passing completely after two tries (even if you conditionally passed
the first time) means that you can no longer continue in the Ph.D. program.
You perform acceptably on all three topics. This means you passed the
You perform acceptably on two of the three topics but not on the
third. This is called a conditional pass and it means that you
must retake and do acceptably on just that topic on the next
exam. (You can switch you choice of equivalent core topic for the retake,
however; for example, if you fail Compilers the first time, you can
opt to take Architecture the second time.)
You only performed acceptably on one topic, or on no topics. This is
considered a complete failure, and in this case you must retake the entire
exam the next time it is given, including the topic on which you did
acceptably, if there is one.
Guidelines for Faculty
If you are supplying questions
Submit three numbered questions, numbered 1, 2, and 3. Students have
1 hour 45 minutes to answer their choice of two out of the three. A
numbered question may have multiple subparts if you think it
appropriate. Keep in mind that numbered questions are weighted
equally when grading.
The exam is closed book, closed notes, and no electronic devices or
printed material allowed. This includes calculators, so do not pose
questions that assume the use of a calculator.
Students put all their answers on separate sheets of paper, not on the
handout. Keep your questions flowing one after another, without a lot
of space in between. Also, do not include blanks (e.g., blank
entries in tables) that you expect students to fill in on the handout.
Submit your questions in PDF format, but also include all related
source files (e.g., LaTeX or MS Word) so that we can edit them if need
If you are supplying questions for one of the core topics (513 Architecture,
531 Compilers, 750 Algorithms, or 551 Theory), then limit yourself to
the topics on the established reading lists, above.
If someone else grades your questions (and this is always the case for
the core topics), then be prepared to provide solutions to the
grader. (Solutions may be communicated in writing or orally.)
Your questions will be printed on a laser printer in grayscale only.
Keep this in mind if you are tempted to use color to convey essential
Please submit your questions by 12 noon on the day before the exam. (The
exam is always held on a Saturday.)
If you are grading answers
If you have a conflict of interest (e.g., a student of yours took the
subject you are grading), then at least try to find someone else to
grade that topic. (We understand that this may not be feasible.) This
is less of a problem with the core topics, because each of those topics
is graded by at least two people.
Grade each numbered question out of 20 points total.
If you take points off, make some mark indicating what was deficient.
You may communicate you grades to the Chair (currently Stephen Fenner)
either by email (scores only is OK) or marked-up hardcopy of student
Please include with your grades a pass/fail recommendation for each student
you grade. This is especially important for the research areas, where
scoring is less consistent.
If you think an answer or part of an answer is missing, please let us
know immediately. A page may have been misfiled at some point.
Be prepared to answer questions from students afterwards.
This page was last updated Tuesday March 2, 2021 at 15:55:14 EST.