The UVa CS Graduate Program

1. Introduction

his document sets forth the departmental requirements for the Master and Doctor's degrees in Computer Science. These requirements are in addition to the requirements of the School of Engineering and Applied Science that are outlined in the graduate catalog.

Computer Science offers the degrees of Master of Science (MS), Master of Computer Science (MCS), and Doctor of Philosophy (PhD). The MS degree requires 24 hours of course work plus thesis, and the MCS requires 27 hours plus project[1]. The MS requires at least six hours of thesis research. The MCS project counts three hours toward the degree and is assigned a grade by the student's advisor. Following the 30 hours of studies required for the Master's degree, a PhD student will take whatever courses (at least six hours) are necessary to supplement his, or her, research for the dissertation.

Students in the MS program must present and defend a thesis, while students in the Master of Computer Science program must complete, document, and present a project. Doctoral candidates must pass both written and oral qualifying exams, and present and defend a dissertation topic proposal, prior to writing and defending the dissertation.

All students begin graduate studies with the status of "admitted to the graduate program". Students seeking a terminal Master's degree will retain that status throughout their association with the graduate program. Formal admission to the PhD program and admission to candidacy are further steps for students intending to complete a PhD. These steps are discussed in more detail in Section 3.

During the first week of orientation, a graduate student's record will be reviewed by a small advisory committee for the purpose of determining the student's plan of studies for the first semester. Based on this review the advisory committee may advise appropriate remedial action, such as auditing undergraduate courses. If a student has not already been assigned an advisor through the admission's process, one of the advisory committee members will serve as a temporary academic advisor.

During the first semester graduate students become associated with a research advisor. For students who were not assigned an advisor as part of the admissions process, part of the orientation course's purpose is to help a student select a research advisor. Once assigned, the research advisor then assumes the role of academic advisor as well.

2. The Master's Degree

The Department of Computer Science offers two Master's degrees. Both degrees require the completion of 30 credit hours. The Master of Computer Science (MCS) requires completion of a research project. The Master of Science (MS) requires completion of a thesis describing research of publishable quality. The thesis must be defended before a committee consisting of the advisor and at least two other faculty members in Computer Science.

2.1 Required Courses

The following courses are required for all graduate degrees in Computer Science:

CS 696 - Computer Science Perspectives
CS 654 - Computer Organization
CS 660 - Computability and Complexity
CS 656 - Operating Systems
One graduate-level mathematics course
Three 600-level or higher elective courses (excluding advanced seminar courses)

All courses must be approved by the student's graduate advisor.

Students pursuing the MCS degree must complete two advanced seminar courses (non-lecture style courses) and CS 895 (Supervised Projects) under the direction of a faculty advisor. Students pursuing the MS degree must complete one advanced seminar course and six hours of CS 898 (Masters Research) under the direction of their thesis advisor.

As a rule,500-level CS courses cannot be taken as a part of the plan of studies for graduate degrees. However, from time to time a specific 500-level CS course (primarily the occasional 500-level special topic course) may be acceptable for graduate credit. In all cases the course must be approved by the student's advisor or advisory committee ahead of time.

2.3 Master's Degree Thesis or Project

Every Master of Science (MS) candidate must write a thesis describing research of publishable quality. The thesis must be defended before a committee consisting of the advisor and at least two other faculty members in Computer Science.

Every Master of Computer Science (MCS) candidate must complete a research project. The research required is typical of a Master's thesis but not as extensive, reflecting the fact that the project carries only three hours of credit versus six hours for a thesis. The research project must be presented in both oral and written form. The written part may range from a scholarly paper that includes comprehensive references to the literature, to a suitably documented computer program.

Both the MS thesis defense and the MCS oral presentation are open to the public, including all interested faculty and students.

2.4 Funding for Students in the Master's Degree Programs

Students who are receiving financial aid for a master's degree are subject to the following guidelines. Students terminating with a master's degree will normally be funded for no more than 4 semesters (plus, possibly, an intervening summer).

2.5 Master's Students and the PhD

Those students planning to go on to a PhD degree should become familiar with the requirements of the PhD program (see the next section) as soon as possible. In particular, it is possible to bypass the master's degree altogether and proceed directly to PhD. Alternatively, it is possible to obtain a MCS rather easily while primarily pursuing the PhD.

3. The PhD Program

he primary requirement for the PhD program is not accumulation of coursework but research leading ultimately to a dissertation. Each student's program of study is tailored by the student and advisor with the goal of enabling high-quality research.

3.1 Coursework

Although specific course requirements are minimal, students in the PhD program are expected to develop the mathematical skills necessary for serious scientific research and to participate in the ongoing intellectual life of the department by regular attendance at colloquia and seminars.

No minor outside the CS Department is required. However, courses in mathematics, electrical engineering, psychology, and so on, are strongly recommended when appropriate to the student's area of study. The student's research advisory committee (see next subsection) is responsible for approving a program of studies that incorporates suitable breadth and depth.

3.2 Advancement to Candidacy

There are a number of checkpoints along the way; each designed to ensure that students have sufficient talent and background to perform their research in a satisfactory and timely fashion.

Advancement to candidacy for the PhD is a status granted to graduate students, regardless of whether they have a master's degree, by the faculty after evaluation of criteria that include:

outstanding performance in graduate coursework
satisfactory performance on the PhD qualifying examination
demonstrated evidence of research ability, including a positive recommendation from the student's research advisor.

We discuss each of these requirements in more detail.

The minimum GPA requirement to remain a graduate student is 3.0, a B average. For prospective PhD students, the faculty desires to see at least as many A's as B's in coursework. Only in special circumstances will a student be admitted to the PhD program with weaker grades.

The purpose of the PhD qualifying exam is to verify that students who are about to move into advanced work have mastered the basic material and techniques of Computer Science and are able to reason about them in a coherent, integrated fashion. The qualifying exams are administered twice a year, typically in January and May. Students desiring a PhD should take the qualifying exams as soon as possible. Students entering with a master's degree should take the exam no later than the end of their second semester. Students entering with a bachelor's degree should ideally take the exam by the end of their second semester, but no later than the end of the third semester. For example, students entering in Fall 2000 with a bachelor's degree must take the exam no later than January 2002, unless there are extenuating circumstances. (The exam should not be postponed in order to finish a master's degree first.) A separate document that describes the qualifying exam and includes a syllabus is widely circulated in the department well before the exam is given. In general, this exam will be at the level of the graduate core courses, plus a little more.

The PhD qualifying exam consists of both written and oral parts. Pass/fail grades will be assigned blind to the written part. Both parts of the exam must be passed but if one part is failed only that part need be retaken. If either part of the exam is failed, it must be retaken at the next regular time.

Superior performance in graduate coursework and on the PhD qualifying examination is necessary but not sufficient conditions for advancement to candidacy to the PhD program. Some students perform well in the classroom, but still lack the ability to do the research necessary for a PhD. Thus, it is necessary to demonstrate research ability, and to attract the enthusiastic support of a research advisor. Sufficiently good overall performance in coursework, research and the exam will be required for a second chance on the qualifying exam if it is not passed on the first try. If, in the judgment of the faculty, a student is unlikely to complete the PhD in a timely manner, it is in the best interests of both student and faculty that the student not be advanced to candidacy. This decision will be made as early as possible.

Upon advancement to candidacy, a research advisory committee for the student will be established. This committee will consist of at least four faculty members including the research advisor and at least one member from outside the department, and will approve a program of studies that incorporates suitable breadth as well as depth. It will also perform the functions described in the next subsection.

3.3 Dissertation Proposal

Each PhD student must present an acceptable dissertation proposal done under the guidance of the student's advisor. This proposal should be presented prior to any extensive research, in order to receive early faculty approval of the suitability of the proposed research. The written proposal document should be prepared according to the following guidelines:

The proposal must be limited to 15 single-spaced (or 30 double-spaced) pages exclusive of bibliography.
The document should succinctly describe:
- the problem;
- relationship to other work in the field;
- the research plan including specific research activities;
- expected contributions.
An example of an organization that meets these four requirements is:
- what's the problem
- why is it important
- what's the "shape" of a solution
- what's the research agenda
- why will the agenda work (produce a solution)
A comprehensive literature review (not subject to page limitations) may be included as an appendix.

Any departure from these guidelines must be approved in advance by the student's proposal examining committee.

As discussed in the previous subsection, the faculty's judgment of a student's research potential is an important part of the decision for advancement to candidacy. However, this judgment will be based on limited experience since the student will not have had time to undertake extensive research. During the period between advancement to candidacy and the research presentation, much more time for research will be available and the faculty will be able to make a much better assessment of research potential. Thus, one outcome of the research presentation might be that, in the judgment of the faculty, the student does not have sufficient research potential to complete a dissertation in a timely fashion; in this case the student will be subject to dismissal from the program.

In the event that a suitable proposal is not presented but the faculty believes the student has sufficient research potential, another research presentation will be scheduled within 6 months. If a suitable proposal is still not presented, the student is subject to dismissal from the program.

3.4 The Dissertation

The culmination of the PhD program is the defense of the dissertation. This dissertation will be the result of the final research outlined in the dissertation proposal and should be completed within a year or so after the proposal is approved. It is expected that the work be of sufficient quality to warrant journal publication. The dissertation defense, which is announced publicly, is an oral defense before the student's advisory committee (minimum of 5 members), as well as any other interested faculty, students or other persons.

3.5 Funding of PhD Students

For those students who have been awarded financial aid, the following policies will apply. Funding for master's degree students remains constant (except for possible cost-of-living increases). PhD students, however, are paid according to the following four-step scale.

Incoming Bachelor's degree
Completion of Master's (or entered with Master's)
Advancement to Candidacy
Successful presentation of a dissertation proposal

Graduate Courses in Computer Science

CS 551 Special Topics in Computer Science: Prerequisite: Admission by consent of instructor.
Course content varies from year to year and depends on the interest and needs of our students. See CS 751 for possible topics.
CS 571 Translation Systems (3) (Y): Prerequisite: Completion of CS 333 with a grade of C- or higher.
This course studies the theory, design, and specification of translation systems. Translation systems are the tools used to translate a source language program to a form that can be executed. Using rigorous specification techniques to describe the inputs and outputs of the translators and applying classical translation theory, working implementations of various translators are designed, specified and implemented.
CS 616 (Same as SYS 616) Knowledge-Based Systems (3) (Y): Prerequisite: Graduate Standing.
This course introduces the fundamental concepts for research, design, and development of knowledge-based systems. Emphasis is on theoretical foundations of artificial intelligence, problem solving, search, and decision making with a view toward applications. Students are required to develop a working knowledge-based system in a realistic application domain. (Cross-listed as SYS 616)
CS 644 Introduction to Parallel Computing (3) (Y): Prerequisites: CS 308, CS 414 and CS 415 or consent of instructor.
The purpose of the course is to introduce the student to the basics of parallel computing. The course covers parallel computation models, systems, languages, compilers, architectures, and algorithms. This course will provide a solid foundation on which advanced seminars on different aspects of parallel computation can be abased. There will be an emphasis on the practical application of parallel systems. There will be several programming assignments.
CS 645 (Same as EE 645) Computer Graphics (3) (Y): Prerequisite: Knowledge of C.
Display devices, line and circle generators; clippings and windowing; data structures; 2D picture transformations; hidden line and surface algorithms; shading algorithms; free form surfaces; color graphics; 3D picture transformations. (This course, which is cross-listed with Electrical Engineering, may be taught by either department).
CS 650 Designing Complex Software Systems (3) (Y): Designing new computational systems and the software that drives them is both hard and interesting. One important style of computer science research, often called experimental systems research, revolves around such design activities. Research in this style seeks to advance our understanding of, and our ability to create, general computer systems that support the development and use of more domain-specific applications.
CS 651 Special Topics in Computer Science (3) (SI): Prerequisite: Admission by consent of instructor.
The material that varies from year to year is selected to fill special needs of graduate students.
CS 654 Computer Organization (3) (Y): Prerequisite: CS 308 or proficiency in assembly language programming.
Study of representative digital computer organization with emphasis on control unit logic, input/output processors and devices, asynchronous processing, concurrency and parallelism. Memory hierarchies.
CS 655 Programming Languages (3) (Y): Prerequisite: CS 415 or equivalent.
Comparative study of the organization and implementation of a variety of programming languages and language features. Design principles are explored and applied in a historical review of major languages. Procedural, functional, logic-based, object-oriented and parallel languages. Research issues such as polymorphism, formal semantics and verification explored in depth.
CS 656 Operating Systems (3) (Y): Prerequisite: CS 654 or consent of instructor.
Supervisory and control software for contemporary multiprogrammed computer systems. Processes, synchronization, interprocess communication, scheduling, memory management, resource allocation, security, system performance evaluation, virtual machines, object-oriented systems, case studies (usually including UNIX).
CS 660 Theory of Computation (3) (Y): Prerequisite: CS 302 or equivalent.
Formal languages, the Chomsky hierarchy, formal computation and machine models, finite automata, pushdown automata, Turing machines, Church's thesis, reductions, decidability and undecidability, NP-completeness.
CS 661 Design and Analysis of Algorithms (3) (Y): Prerequisite: CS 332 or equivalent.
Concepts in algorithm design, problem solving strategies, complexity and bounds, sorting and searching, graph algorithms, geometric algorithms, probabilistic algorithms, intractability and NP-completeness transformations, approximation algorithms.
CS 662 Database Systems (3) (Y): Prerequisite: CS 462 or equivalent.
Comparative study of hierarchical, CODASYL, and relational database models, with emphasis on the latter. Readings in theoretical database issues. Implementation of a practical database using one of the standard models. Introduction to implementation issues.
CS 682 Digital Picture Processing (3): Prerequisite: Graduate Standing.
Basic concepts of image formation and image analysis: imaging geometry, sampling, filtering, edge detection, Hough transforms, region extraction and representation, extracting and modeling three-dimensional objects. Students will be assigned analytical and programming assignments to explore these concepts. (Same as EE 682)
CS 685 Software Engineering (3) (Y): Prerequisite: CS 340 or equivalent.
Project management, software tools, requirements and specification methods; top-down, bottom-up, and data-flow design. Structured programming, information hiding, programming language issues, and coding standards. Software development environments, fault tolerance principles, and testing.
CS 693 Independent Study (Credit as arranged): Detailed study of graduate course material on an independent basis under the guidance of a faculty member.
CS 695 SUPERVISED PROJECT RESEARCH (Credit as arranged): Formal record of student commitment to project research under the guidance of a faculty adviser. Registration may be repeated as necessary.
CS 696 Computer Science Perspectives (1): Prerequisite: CS Graduate Student or Consent of Instructor.
Students will attend semi-weekly sessions, which will consist of both lecture and hands-on experience. Lectures will be given by the computer science faculty and visitors on a variety of research topics. Hands-on sessions will give students experience with the wide variety of tools available to researchers. These tools include but are not limited to: programming languages, software development systems, parallel computing devices and models, user interface management systems, and various operating systems.
CS 715 Performance Analysis of Communication Networks (3): Prerequisites: EE 611 - Probability and Stochastic Processes, or consent of the instructor.
Topologies arising in communication networks; queuing theory; Markov Chains and ergodicity conditions; theory of regenerative processes; routing algorithms; multi-access and random- access transmission algorithms; mathematical methodologies for throughput and delay analyses and evaluations; performance evaluation; performance monitoring; local area networks (LANs); interactive LANs. (Cross-listed as EE 715)
CS 716 Artificial Intelligence (3) (Y): Prerequisite: CS 616 or SYS 616.
In depth study of a few major areas historically considered to be part of artificial intelligence. In particular, detailed coverage will be given to the design considerations involved in the following applications: automatic theorem proving, natural language understanding and machine learning. (Cross- listed SYS 716)
CS 751, 752 Selected Topics in Computer Science (3,3) (SI): Prerequisites: Admission by consent of instructor.
Course content varies from year to year and depends on the interest and needs our students. Topics could be advanced combinatorics and graph theory, parallel processing, information retrieval, data communications, computer networks, etc.
CS 756 Models of Computing Systems (3) (O): Prerequisites: CS 656 and either SYS 605 or EE 611.
Studies of user behavior, program behavior, and selected aspects of computer systems such as scheduling, resource allocation, memory sharing, paging, or deadlocks. Mathematical models and simulation. Use of measurements in the formulation and validation of models. Performance evaluation and prediction.
CS 757 Computer Networks (3) (Y): Prerequisite: CS 656 or consent of instructor.
Network topologies, backbone design; performance and queuing theory; datagrams and virtual circuits; technology issues; layered architecture, standards; survey of commercial networks, local area networks, and various communication protocols; encryption; security. (Cross- listed as EE 757).
CS 771 Compilers (3) (Y): Prerequisite: CS 660, CS 655, or equivalents.
Study of techniques used in the implementation of assemblers, compilers, and other translator systems. Analyzes the relationship of available techniques to the syntactic and semantic specification of languages.
CS 782 Advanced Computer Vision (3) (Y): Prerequisite: CS 682.
Analysis of advanced topics in automated reconstruction of imaged objects and computer interpretation of imaged objects; techniques for three-dimensional object reconstruction; computing motion parameters from sequences of images; computational frameworks for vision tasks such as regularization, and stochastic relaxation; approaches for autonomous navigation. Depth image analysis; novel imaging techniques and applications; and parallel architectures for computer vision.
CS 851 Advanced Topics in Computer Science (3) (SI): Prerequisite: Permission of instructor.
The exact syllabus for the seminar depends on the interests of the participants. Quick review of the fundamental technologies: parsing, generating IR or bytecodes, interpretive systems in general, and run-time support, especially memory management. Analysis and classification of existing embedded languages according to the language paradigms used and the features included, without reference to the implementations. Analysis of the implementations of existing embedded languages.
CS 854 Topics in Computer Architecture (3) (Y): Prerequisite: CS 654 or consent of instructor.
Study of selected advances in the architecture of computer systems. Possible areas of study include distribution processor systems, memory hierarchies, and secondary storage management schemes.
CS 855 Topics in Programming Languages (3) (Y): Prerequisite: CS 655 or permission of instructor.
Study of selected advanced topics in design, definition, and implementation of programming languages. Typical recent topics: parallel language design; formal semantics of programs. May be repeated for credit when the topics vary.
CS 856 Topics in Operating Systems (3) (Y): Prerequisite: CS 656 or permission of instructor.
Topics covered are generally chosen from one or more of the following operating system research areas: detailed case studies, distributed systems, global computing, distributed shared memory, real-time systems, object-oriented systems, security, multimedia, and mobile computing.
CS 860 Topics in Theoretical Computer Science (3) (O): Prerequisite: CS 660 or permission of instructor.
Study of selected formal topics in computer science, including computational geometry, advanced searching techniques, proximity and intersection problems, interconnection problems, VLSI CAD, amortized complexity analysis, approximation algorithms, zero-knowledge proofs, biological computing, and quantum computing.
CS 862 Topics in Database Systems (3) (Y): Prerequisite: CS 662 or permission of instructor.
Analyzes the implementation of database systems, concurrent and distributed access, backup, and security; query languages and optimization of query access; multi-attribute dependencies and retrieval.
CS 882 Special Topics in Computer Vision/Image Processing (3) (Y): Prerequisite: Permission of instructor.
For MS and PhD students conducting research in image processing and machine vision. The contents vary with each semester and each instructor. An in-depth study of recent research in narrowly defined areas of computer vision / image processing. Readings from recently published articles in journals and conference proceedings are assigned. Cross-listed as EE 882.
CS 885 Topics in Software Engineering (3) (O): Prerequisite: CS 685 or permission of instructor.
A special topics course in software engineering. Topics covered are determined by the individual instructor, but might include: software reliability; engineering real-time systems; managing large software projects; resource estimation; validation and verification; or advanced programming environments.