This page contains basic general information about the qualifying exam.

Reading List

Core Topics (see below for specialty research topics)

1. Algorithms (CSCE 750): Introduction to Algorithms (2nd ed.) by Cormen, Leiserson, Rivest, and Stein
   • 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
   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.

   For further reference see Dr. Buell's website (above) and 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 and NP-Complete Problems
   • Space Complexity
   Please note: Starting Fall 2014, NP-completeness is included among potential topics covered in the Theory section.

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

Specialty research topics (Note: these are meant as as only a rough guide and are not updated regularly.)

• 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 past exams for the last 10 years

2024	Fall	Spring
2023	Fall	Spring
2022	Fall	Spring
2021	Fall	Spring
2020	Fall	Spring
2019	Fall	Spring
2018	Fall	Spring
2017	Fall	Spring
2016	Fall	Spring
2015	Fall	Spring
2014	Fall	Spring
2013	Fall

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.

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

What constitutes a pass?

There are three possible outcomes from taking the exam:

1. You perform acceptably on all three topics. This means you passed the exam.
2. 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.)
3. 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

1. 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.
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. 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.
6. 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.)
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 12 noon on the day before the exam. (The exam is always held on a Saturday.)

If you are grading answers

1. 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.
2. Grade each numbered question out of 20 points total.
3. If you take points off, make some mark indicating what was deficient.
4. 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.
5. 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.
6. 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.
7. Be prepared to answer questions from students afterwards.

This page was last updated Saturday October 26, 2024 at 15:39:02 EDT.