USC Computer Science and Engineering Department
Qualifying Examination Information Page

This page contains basic general information about the qualifying exam.

IMPORTANT: Starting in Fall 2025, the options for the qualifying exam have changed.
Ph.D. candidates will now have two options to pass the exam:

• Option A -- Written Exam from Core Courses. This is much like how the exam has conducted through Spring 2025, except that there will be no research topic, and 2.5 hours will be allotted for each of the two core topics chosen (either 513 or 531 and either 551 or 750): For each core topic, students have 2.5 hours to answer their choice of two out of three numbered questions on that topic. The exam is closed book and notes, no electronic devices. (See "Guidelines for Students," below.)
• Option B -- Research-Based Exam. The student will submit either a research paper or a high-quality survey paper and present it to a committee of at least three faculty members from the department and optionally one outside the department.

Time Limit for Completing the Qualifying Exam

The following rules will be strictly enforced:

• All components of the qualifying exam must be passed within the first two years of the student's enrollment in the Ph.D. program.
• A student may switch between the course-based (Option A) and research-based (Option B) exam options between attempts; however, the total number of attempts across both formats may not exceed two.

Transitions from the Old Rules to the New

• If you have already passed the qualifying exam, you can ignore all of the above; it does not apply to you.
• If you have conditionally passed the qualifying exam, then you have two options:
  1. You may retake the topic you missed in the new Option A format (2.5 hours), and you must pass it on a single attempt no later than Spring 2026.
  2. You may choose Option B, in which case you will be allowed two attempts to pass the exam.
  For either option, you must pass the exam no later than Spring 2026.

Reading List

Core Topics (research topics will no longer be required)

1. Algorithms (CSCE 750): Introduction to Algorithms (4th ed.) by Cormen, Leiserson, Rivest, and Stein
   • Foundations: chapters 1-5, 6-9 recurrences, sorts and order statistics
   • Trees: chapters 12-13, binary search trees, red-black trees
   • Dynamic Programming and Greedy Algorithms: chapters 14-15
   • Augmenting Data Structures: chapter 17
   • Graph Algorithms: chapters 20-22

   These topics are also covered in the 2nd and 3rd editions of the textbook, but the chapter numbers may be different. For further reference see Dr. Fenner's CSCE 750 website (https://cse.sc.edu/~fenner/csce750/index.html).

2. 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 sets
   • Instruction Level parallelism
   • Loop unrolling and static techniques
   • Memory Hierarchy design
   • Interconnection networks
   • Pipelining

3. Compilers (CSCE 531): Compilers: Principles, Techniques, & Tools (2nd ed.) by Aho, Lam, Sethi, and Ullman, Addison-Wesley, Chapters 1-8.
   • Lexical analysis
   • Syntax Analysis
   • Syntax-Directed Translation
   • Type Checking
   • Run-Time Environments
   • Intermediate Code Generation
   • Code Generation
   Talk to Dr. Valtorta, who has taught CSCE 531 several times recently. For further (rather dated) information see Dr. Fenner's CSCE 531 website.

4. 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.
   • Finite Automata, Regular Expressions, Properties of Regular Languages
   • Turing Machines, Decidability, Reductions
   • Time Complexity, P, NP, NP-Complete Problems, and Polynomial Reductions
   • Space Complexity

   For further information see Dr. Fenner's CSCE 551 website.

Core areas of past exams for the last 10 years

2024	Fall (Answers: 551, 750)	Spring
2023	Fall	Spring (Answers: 551, 750)
2022	Fall (Answers: 750)	Spring
2021	Fall	Spring
2020	Fall	Spring
2019	Fall	Spring
2018	Fall	Spring
2017	Fall	Spring
2016	Fall	Spring
2015	Fall	Spring
2014	Fall

Guidelines for Students

Option A

The qualifying exam is given once each semester. Option A is always on a Saturday.

Option A of the exam consists of two sessions, each lasting two hours and 30 minutes, on two respective topics which are considered core to the department's program:

• 9am - 11:30am: Your choice of either Compilers (CSCE 531) or Architecture (CSCE 513), and
• 1pm - 3:30pm: Your choice of either Algorithms (CSCE 750) or Theory (CSCE 551).

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 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:

• Use paper with borders (the department will provide these).
• Write your CODE IN THE 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. Place them in a separate, designated pile at the proctor's desk.

What constitutes a pass?

There are three possible outcomes from taking the exam:

1. You perform acceptably on both topics. This means you passed the qualifying exam.
2. You perform acceptably on one of the topics but not on the other. This is called a conditional pass and it means that if you stick with Option A, you must retake and do acceptably on just that topic on the next exam. You can switch your choice of equivalent topic for the retake, however; for example, if you fail Compilers the first time, you can opt to take Architecture the second time. You may also choose Option B for your second attempt.
3. You did not perform acceptably on either topic. In this case you must retake the entire exam, either with Option A or Option B.

Option B

For detailed guidelines on Option B, see the document Q-Exam-Rules.pdf.

Guidelines for Faculty (Option A)

If you are supplying questions for Option A

1. Submit three numbered questions, numbered 1, 2, and 3. Students have 2 hours and 30 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.
2. 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.
3. 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.
4. 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.
5. Please limit your questions to the topics on the established reading lists, above.
6. Each topic is graded by two people. Be prepared to provide solutions to the other grader(s). (Solutions may be communicated in writing or orally.)
7. 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.
8. Please submit your questions by 5pm on the Thursday before the exam. (The exam is always held on a Saturday.)

If you are grading answers for Option A

1. Grade each numbered question out of 20 points total.
2. If you take points off, make some mark indicating what was deficient.
3. You may communicate you grades to the Chair (currently Stephen Fenner) either by email (scores only is OK) or marked-up hardcopy of student answers.
4. Please include with your grades a pass/fail recommendation for each student you grade.
5. 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.
6. Be prepared to answer questions from students afterwards.

This page was last updated Sunday June 22, 2025 at 15:22:21 EDT.