Ph.D. in Computer Science (Curriculum 368-PhD)
The Ph.D. is the highest degree awarded by universities in the United States. Its primary purpose is to validate that its possessor can perform state-of-the-art research on the frontiers of human knowledge, and is able to intelligently manage the research of others. The Academic Council sets institutional rules on all the Ph.D. programs at the Naval Postgraduate School, which are delineated in the Academic Council Policy Manual, Section 5.4.The departmental rules described here supplement, but do not supplant, the institutional rules. The PhD Program Committee of the Computer Science Department oversees all aspects of the PhD program and process.
Applicants must follow the standard procedures of their sponsoring organization in applying to a graduate education program; see the Academic Council Policy Manual, Section 4.4. Applicants should have the sponsoring organization forward their letter of application to the Director of Admissions (Code 01B3) at the Naval Postgraduate School, Monterey, CA 93943. U.S. military officers, foreign military officers, U.S. Government civilians and employees of foreign governments may apply. The application should include certified transcripts of all courses taken at the university level, including both undergraduate and graduate courses. Students not currently at the Naval Postgraduate School must include the results of a recent GRE general test. Foreign students who are not native speakers of English must provide scores on the TOEFL examination. Since the Ph.D. is a research degree, the applicant should also include any material demonstrating ability to perform research, such as Master's theses and research papers. Reference letters are helpful only if the writer can report direct knowledge of the candidate's technical and research abilities.
An applicant should have a Master's Degree in Computer Science or in a closely related field. Generally, an acceptable Ph.D. applicant must have above-average grades in a typical Master's degree program. The Committee will also take other evidence of research or academic ability into account in making a recommendation as to whether to admit an applicant.
The Ph.D. Program Committee will evaluate each applicant to gauge the minimum amount of time the applicant will need to complete the program (normal time is three years). The Computer Science Department may impose the condition that the applicant obtain authorization for at least four years to complete the Ph.D.
Applicants are cautioned that admission to the Ph.D. program does not guarantee successful completion of the program. It is significantly more difficult to assess the qualifications of a student for a Ph.D. admission than for other degrees. This is because the research work required for the Ph.D. requires significant creativity and independence. Past experience suggests that not all of the students admitted will successfully complete the program. The purpose of the Written Qualifying Examination (see below) in our department is to give students early warning if they are likely to have trouble in our Ph.D. program. For self-assessment, prospective applicants can obtain copies of previous examinations together with solutions by contacting the Computer Science Ph.D. Program Committee at the Naval Postgraduate School.
Rules of the Naval Postgraduate School require only a minimum one-year residency at the School for a Ph.D. degree. Examinations may be taken during travel to the School from a full-time job elsewhere. Some or all of the one-year residency may possibly be satisfied by previous residency at the School for another degree program, to be decided by petition to the Academic Council. Nonetheless, we expect it will require the equivalent of at least three years of full-time work to complete a Ph.D. degree, and chances of successful completion of the Ph.D. program are much higher when the student can be in residence at the School for at least three years.
Requirements for the Ph.D. Degree
The students must complete the following steps, which are detailed in the following sections.
- Form a Dissertation Committee
- Complete the Written Qualifying Examination
- Complete Requirements for a Minor
- Complete the Dissertation Proposal
- Complete the Oral Qualifying Examination
- Advance to Candidacy
- Complete the Final Examination (Dissertation Defense)
- Complete the Dissertation
A checklist on how to complete these requirements, along with recommendations on achieving them, is presented in the following paragraphs.
Forming a Dissertation Committee
The student must form a Dissertation Committee to oversee his or her program as soon as possible after admission to the Ph.D. program, but no later than at the time of scheduling the Written Qualifying Examination.
The Dissertation Committee is responsible for supervising the candidate's completion of the degree, including completion of course of study, dissertation research, and production of the dissertation document. The Dissertation Committee also administers and determines the results of the Oral Qualifying Examination and the final Dissertation Defense. The Dissertation Committee is nominated by the Ph.D. Program Committee and approved by the Academic Council.
The PhD Program Committee delegates two responsibilities to the student's Dissertation Committee:
- Writing the Written Exam as described below, and getting approval from the PhD Program Committee prior to the PhD Program Committee administering the exam to the student.
- Grading the questions and submitting the graded exams to the PhD Program Committee for its approval. The PhD Program Committee reports the results of the Written Exam to the Chair of the CS Department.
One of the members of the Committee from the Computer Science Department must be designated as the Dissertation Supervisor, and will be the student's primary technical contact; the Dissertation Supervisor must be knowledgeable about the area of the proposed dissertation and should have prior personal experience on Dissertation committees. The student must therefore choose the general area for the proposed dissertation prior to forming the Dissertation Committee.
Each Dissertation Committee must have a Chairman, who can be the same as the Dissertation Supervisor except when the Dissertation Supervisor has not previously served on a dissertation committee. The Dissertation Committee must contain at least four members of the Computer Science faculty with expertise relevant to the proposed dissertation topic, plus one additional NPS faculty member from outside the Department. The Computer Science Ph.D. Program Committee must approve any doctoral committee proposal before its submission to the Academic Council.
The subfields of Computer Science relevant to the proposed dissertation can be any academically recognized major sub-field of Computer Science for which there is a Computer Science faculty member whose interest is in that sub-field. Examples of subfields are software engineering, database systems, artificial intelligence, computer architecture, robotics, graphics, algorithms, data structures, programming languages, operating systems and computer networks.
At the time of approval of the Dissertation Committee, the student must also formulate a Study Plan, which includes a list of courses to be validated and a timetable of when he or she expects to pass the various milestones of his/her Ph.D. program. The Study Plan should be developed in consultation with the proposed Dissertation Supervisor. The Dissertation Committee members must agree that the Study Plan is acceptable when agreeing to serve on the Committee. The Written Exam may be scheduled at any time in the student’s Study Plan. The PhD Program Committee must be notified 30 days in advance of the student's intention to take the Written Exam.
Written Qualifying Examination
The purpose of the Written Qualifying Examination is to check each student's analytical ability in computer science and his or her ability to solve problems in computer science. These abilities are crucial for success in Ph.D. dissertation work.
This is an open-book examination prepared and graded by the student's Dissertation Committee with oversight by the Ph.D. Program Committee. The Computer Science Ph.D. Program Committee administers it. There are two possible outcomes of the Written Qualifying Examination: Passed and Failed. If the student fails his or her first Written Qualifying Examination, the Computer Science Ph.D. Program Committee may grant the privilege of a second examination opportunity. If the student fails a portion of the exam but passes other portions, the student's Ph.D. Dissertation Committee may recommend to the Ph.D. Program Committee that the student be re-examined over only the failed portion. If granted, the second examination (in part or whole) must be within one year of the first, and only two opportunities for passage are allowed (see Academic Council Policy Manual, Section 5.4.8).
The Written Qualifying Examination consists of two parts:
- Mathematical Foundations
The Mathematical Foundations of Computer Science Requirement
As part of the Written Qualifying Examination the student must have completed the Mathematical Foundations of Computer Science requirement. The student must demonstrate mastery of fundamental topics of computer science including: finite automata, regular grammars and expressions, pushdown automata, context-free grammars, deterministic context-free languages, Turing machines, universal Turing machines, Church's Hypothesis, tractability, undecidability, mathematical induction, complexity analysis, P/NP completeness, graphs, greedy algorithms, divide-and-conquer methods, backtracking, and predicate calculus.
All students must pass a written qualifying exam in mathematical foundations. A student who has an A in all three of MA3025, CS3601, and CS3650 satisfies this requirement without a further written exam. This requirement may also be satisfied by transfer of equivalent course credit (as determined by the PhD Program Committee) from an accredited graduate or undergraduate program, as documented by official transcripts from said institutions.
The following texts may assist the student in preparing for the Mathematical Foundations of Computer Science requirement.
References: Ralph Grimaldi, Discrete and Combinatorial Mathematics, 3rd edition, Addison-Wesley, 1994, ISBN 0-201-54983-2, sections 2, 3, 4.1-4.2, and 15; and Patrick Winston, Artificial Intelligence, 3rd edition, Addison-Wesley, 1992, ISBN 0-201-53377-4, chapter 13.
Reference: Thomas A. Sudkamp, Languages and Machines, Addison-Wesley, 0-201-15768-3 1988, all chapters.
Reference: Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Algorithms, The MIT Press and McGraw-Hill Book Company, ISBN 0-262-03141-8 1989, chapters 1-13 (minus 13.4), 15-17 (minus 17.4+17.5), 19-26, and 36.
Specialization Requirement of the Written Qualifying Examination
The Written Qualifying Examination is seeking evidence of depth of understanding of foundational concepts, insight, and the ability to solve unfamiliar problems in two selected areas of computer science, chosen by the student with guidance from the dissertation committee.
Topics of questions for the Written Qualifying Examination are selected from the 5 areas listed below. The exam on each area consists of at least four questions and no more than eight questions and is expected to take from 4 to 6 hours to complete.
Software Engineering: Predicate calculus, proof of algorithms, programming languages, operating systems, software design, software metrics, software architectures, formal requirements specification, and tools.
Computer Graphics and Visual Simulation: methodologies and techniques required in real-time, three-dimensional, interactive, visual simulations for military applications, human-computer interaction, usability engineering.
Database and Knowledge Engineering: data retrieval and processing, advanced symbolic computation, AI languages and expert system shells, robotics for military applications. Representation of knowledge, equivalences, normal forms, proof, resolution principle, refutation.
Computer Systems, Networks and Architecture: computer architecture, networks and system software for real-time and multi-computer systems with emphasis on military applications to embedded computers and secure systems.
Computer Systems and Security: Information Security (INFOSEC) and secure computer systems.
The student's contact in preparing for the Written Examination should be the Chairman of the Computer Science Ph.D. Program Committee.
Breadth Requirement and Minor Requirements
To satisfy the Ph.D. Breadth Requirement, Computer Science students must complete a set of three graduate-level courses that form a coherent topic of study distinct from the student's major concentration, approved by the student's Dissertation Committee. These courses are not restricted to a single department and may be in the form of directed study, subject to the approval of the student's Dissertation Committee. The student’s Dissertation Committee certifies completion of the Breadth Requirement. Courses taken in preparation for the Mathematical Foundations of Computer Science requirement may be applied towards the breadth requirement.
The Ph.D. Program Committee of that other Department determines the minor requirements for students from other departments seeking a minor in Computer Science. In the absence of such requirements, the Computer Science policy applies: students from other departments can obtain a Minor in Computer Science by completing three graduate-level courses in Computer Science that form a coherent topic of study distinct from the student's major concentration, which must be approved by the student's Dissertation Committee. These courses may be in the form of directed study, subject to the approval of the student's Dissertation Committee. The student's Dissertation Committee certifies completion of a Minor in Computer Science.
A dissertation proposal must be submitted to the Dissertation Committee at least one week before the Oral Qualifying Examination. The purpose of the dissertation proposal is to provide the Dissertation Committee with the information needed to determine whether the proposed research topic is suitable for a Ph.D. dissertation. The proposal should describe the student's best current estimate of his/her research plan. The details in the proposal may be changed later, when the research subject is understood in more detail.
Usually one month, but no more than one year after the successful completion of the Written Qualifying Examination, the student must successfully complete the Oral Qualifying Examination. The courses in the study plan must be successfully completed before the student can take the Oral Qualifying Examination. The student gets only two chances to pass the Oral Qualifying Examination (see Academic Council Policy Manual, Section 5.4.9).
The Oral Qualifying Exam is administered by the student's Dissertation Committee. The Dissertation Committee Chairman schedules the oral portion of the Qualifying Examination and the student submits a dissertation proposal to the Dissertation Committee.
The Dissertation Committee members ask any questions that they feel may help decide whether the student has a sufficiently broad knowledge of computer science and sufficient analytic capability to begin full-time Ph.D. research. Typically, students are asked to apply basic concepts of computer science to new or unfamiliar areas of application with emphasis on the selected areas chosen for the written examination. Time permitting, the other faculty members in attendance may also ask questions of the student. The questions need not be confined to computer science.
When the Dissertation Committee is satisfied that the student has been questioned sufficiently thoroughly, the student leaves the room, the Dissertation Committee discusses their concerns, and votes whether the student passes the Qualifying Exam. A unanimous vote of the student's PhD Dissertation Committee is required for the student to pass.
Advancement to Candidacy
The following requirements must be satisfied before a student can be advanced to candidacy for the PhD degree:
- Approval of the dissertation subject.
- Completion of the minor.
- Passing the Written Qualifying Examination
- Passing the Oral Qualifying Examination
Upon successful completion of all requirements listed above, the student must petition the Academic Council for "advancement to candidacy for the doctorat". A memo must be prepared stating that the requirements for advancement to candidacy have been successfully completed.
At least six months after passing the Qualifying Examination, when the dissertation research is almost complete, and a draft of the dissertation has been finished and is available, the final oral examination (also known as the dissertation defense) occurs. This examination is administered by the Dissertation Committee and consists of the following.
1. An open (public) presentation of the findings of the research by the candidate, including response to questions from the audience within an allotted time period.
2. A question and comment phase open to all NPS faculty and the Dissertation Committee, but not to other students.
3. A closed session involving only the members of the student's Dissertation Committee and the Academic Council Representative. A unanimous vote of the student's PhD Program Committee is required for the student to pass.
The dissertation is the major portion of the work involved in earning a PhD. Every Ph.D. dissertation must contain a validation of the research. It is the primary method to validate that the candidate can perform state-of-the-art research on the frontiers of human knowledge and intelligently manage the research of others. After the student has successfully defended the dissertation at the Final Examination and has revised and clarified the dissertation to the satisfaction of each member of the Dissertation Committee, each member signs it. The Registrar checks the format of the dissertation, and finally the Department Chairman and the Dean sign it.