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 QExam Committee Chair
This page contains basic general information about the qualifying
exam.
Reading List
Core Topics (see below for specialty research topics)

Algorithms (CSCE 750): Introduction to Algorithms (2nd ed.) by
Cormen, Leiserson, Rivest, and Stein

Foundations: chapters 14, 59 recurrences, sorts and order statistics

Trees: chapters 1213, search trees, redblack trees

Dynamic Programming and Greedy Algorithms: chapters 1516

Graph Algorithms: chapters 2224

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.)
Please note: Starting Fall 2014, NPcompleteness
will no longer be tested in the Algorithms section of the exam; it
will be tested in the Theory section.
For further reference see Dr. Buell's website (above) and Dr. Fenner's
CSCE 750 website
(http://www.cse.sc.edu/~fenner/csce750/index.html).

Architecture (CSCE 513): Computer Architecture: A Quantitative Approach,
3rd ed. Hennessey and Patterson, Morgan Kaufman, Chapters 15,
8.18.5, Appendix A

Fundamentals of Computer Design

Instruction sets

Instruction Level parallelism

Loop unrolling and static techniques

Memory Hierarchy design

Interconnection networks

Pipelining

Compilers (CSCE 531): Compilers: Principles, Techniques, &
Tools (2nd ed.) by Aho, Lam, Sethi, and Ullman, AddisonWesley,
Chapters 18.

Lexical analysis

Syntax Analysis

SyntaxDirected Translation

Type Checking

RunTime Environments

Intermediate Code Generation

Code Generation
For further information see
Dr.
Fenner's CSCE 531 website

Theory (CSCE 551): Introduction to the Theory of
Computation (1st, 2nd, or 3rd ed.) by M. Sipser, PWS, Chapters
1,35,78. 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.

Finite Automata, Regular Expressions, Properties of Regular Languages

Turing Machines, Decidability, Reductions

Time Complexity and NPComplete Problems

Space Complexity
Please note: Starting Fall 2014, NPcompleteness
is included among potential topics covered in the Theory section.
For further information see
Dr.
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
this link.

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:
 your choice of either Compilers (CSCE 531) or Architecture (CSCE
513),
 your choice of either Algorithms (CSCE 750) or Theory (CSCE 551),
and
 your chosen research area.
The first two items above are called core topics, and questions
from these topics in some past exams are given through the links
above.
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
arbitrarily.
The exam is closedbook, 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:
 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
page.
 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.
For core topics at least, your exam will be graded by two faculty
members.
What constitutes a pass?
There are three possible outcomes from taking the exam:

You perform acceptably on all three topics. This means you passed the
exam.

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.
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.
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
be.

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
information.

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 markedup hardcopy of student
answers.

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.