Graduate Student Handbook

Program Description

The Department of Computer Science (CS) offers M.S. and Ph.D. degrees. Areas of research include analysis of algorithms, artificial intelligence, pattern recognition and retrieval, machine learning, neural networks, computer graphics, computer animation, scientific visualization, computer and sensor vision, image processing, image synthesis, multimodal human-computer interaction, programming languages and environments, software engineering, Web and Internet engineering, real-time embedded systems, computer security, databases, parallel and distributed computation, operating systems, and storage systems. In cooperation with other departments on campus, CS also offers a strong research group in bioinformatics, computational biology, biomolecular engineering, and human genome mapping.

The CS department enjoys a close relationship with the Computer Engineering, Electrical Engineering, and Applied Mathematics and Statistics departments. Faculty members carry out joint research projects, supervise students, and teach courses for these departments. The M.S. degree requires either a master's thesis or an approved project and is usually completed in two years, although it is possible to complete the program in one year. The Ph.D. degree is usually completed in five years.

Additional information on the computer science graduate programs can be found on the department's web pages at www.soe.ucsc.edu.

Graduate Director:

, 831-459-5375

Department Chair:

, 831-459-3648

Requirements for the Master's Degree: Project Track

Course Requirements

Each student is required to take 50-units as follows:

• CMPS 200 (3 units)
• CMPS 201 ( Analysis of Algorithms: 5 units )
• CMPS 203 ( Programming Languages: 5 units )
• CMPS 296 (2 units; Master's project )
• A base requirement in computer architecture must be met by taking CMPE 110 or CMPE 202 or equivalent elsewhere (approval required).

• One course each from three different breadth categories for a total of 3 courses (15 units).

• All remaining units must be graduate elective courses from the list of approved graduate courses.

• At least 30 units must be in CS.

• Two upper-division undergraduate CS courses (other than CMPS 101) or a graduate course (not seminars) in related disciplines outside the list of approved graduate course list may be substituted for one graduate course when necessary to strengthen a student's preparation for graduate studies with prior approval from the student's advisor and the graduate director.

Project

Completion of a Master's Project is required for the Master's degree. In consultation with the advisor, the student forms a Master's Project Reading Committee of at least two faculty members (including the advisor), each of whom is provided a copy of the project report. The final project must be accepted by the review committee before the award of the Master of Science degree.

Master's Project Reading Committee

The members of the Master's Project Reading Committee must include the following:

• A ladder rank CS faculty member
• A ladder rank UCSC School of Engineering (SOE) faculty (may be CS as well).

Additional members may be added to the committee. Students should consult their advisors about the membership of their committee.

Requirements for the Master's Degree: Thesis Track

Course Requirements

Each student is required to take 48-units as follows:

• CMPS 200 (3 units)
• CMPS 201 ( Analysis of Algorithms: 5 units )
• CMPS 203 ( Programming Languages: 5 units )
• A base requirement in computer architecture must be met by taking CMPE 110 or CMPE 202 or equivalent elsewhere (approval required).
• One course each from three different breadth categories for a total of 3 courses (15 units).
• Up to 10 units of CMPS297 ( Independent Study ) or CMPS299 ( Thesis Research ).
• All remaining units must be graduate elective courses from the list of approved graduate courses.
• At least 28 units must be in CS.
• Two upper-division undergraduate CS courses (other than CMPS 101) or a graduate course (not seminars) in related disciplines outside the list of approved graduate course list may be substituted for one graduate course when necessary to strengthen a student's preparation for graduate studies with prior approval from the advisor and the graduate director.

Thesis

Completion of a Master's Thesis is required for the Master's degree. To fulfill this requirement, the student submits a written proposal to a faculty member, usually by the third academic quarter. By accepting the proposal, the faculty member becomes the thesis advisor. In consultation with the advisor, the student forms a Master's Thesis Reading Committee with at least two additional faculty members, each of whom is provided a copy of the proposal. The student gives a public presentation of the completed research and produces a written thesis. The final thesis must be accepted by the reading committee before the award of the Master of Science degree.

Master's Thesis Reading Committee

The members of the Master's Thesis Reading Committee must include the following:

• A ladder rank CS faculty member
• A ladder rank UCSC School of Engineering (SOE) faculty (may be CS as well)
• A UCSC SOE faculty or a recognized expert in the student's research area as judged by the Graduate Committee.

Additional members may be added to the committee. Students should consult their advisors about the membership of their committee.

Requirements for the Ph.D. Degree

Course Requirements

Each student must plan and successfully complete a coherent program of study covering the basics of Computer Science and other areas related to their research. The students's advisor has primary responsibility for ensuring the adequacy of the program, which must include at least 58 units as follows:

• CMPS 200 (3 units)
• CMPS 201 ( Analysis of Algorithms: 5 units )
• CMPS 203 ( Programming Languages: 5 units )
• A base requirement in computer architecture must be met by taking CMPE 110 or CMPE 202 or equivalent elsewhere (approval required).
• One course each from three different breadth categories for a total of 3 courses (15 units).
• Up to 10 units of CMPS297 ( Independent Study ) or CMPS299 ( Thesis Research ).
• All remaining units must be graduate elective courses from the list of approved graduate courses.
• At least 33 units must be in CS.
• Graduate courses (not seminars) in related disciplines outside the list of approved graduate course list may be substituted when necessary to strengthen a student's preparation for graduate studies with prior approval from the advisor and the graduate director. Course selection should form a coherent plan of study and requires advisor approval. Undergraduate courses may not be used to satisfy Ph.D. course requirements.
• Each student is required to complete at least one quarter of Teaching Assistantship. This requirement can be met after advancement to candidacy. Certain exceptions may be granted for students with extensive priorteaching experience or those who cannot be employed by university.

Ph.D. students who have satisfied the requirements for the master's degree are eligible to receive a master's degree.

Dissertation

Each student is required to conduct a body of research culminating in the writing of a Ph.D. dissertation. The dissertation must show the results of in-depth research, be an original contribution of significant knowledge, and include material worthy of publication. Where appropriate, research internships with companies, government labs or elsewhere are recognized (and may be required) as an integral part of the research leading to the dissertation. As the first step, a student submit a written dissertation proposal to a SOE faculty member. By accepting the proposal, the faculty member becomes the dissertation supervisor. The dissertation proposal is publicly and formally presented, in an oral qualifying examination given by a Qualifying Exam Committee approved by the graduate committee and the graduate council. The student must submit his or her written dissertation proposal to all members of the committee and the graduate assistant one month in advance of the examination.

Students are advanced to candidacy after they have completed the course requirements, passed both the preliminary and qualifying examinations (or just the qualifying examination if passed prior to the end of the student's third year in the program), cleared all Incompletes from their records, have an appointed Dissertation Reading Committee and have paid the filing fee. Students who have not advanced to candidacy by the end of their fourth year will be placed on academic probation.

In case a student changes his/her thesis supervisor after advancement to candidacy, he/she will be required to pass another qualifying examination following the same procedure by submitting a thesis proposal and having it approved by a qualifying exam committee by making a public presentation of the thesis proposal. This requirement can be waived only if the student submits a waiver request in writing stating that the thesis proposal and the scope of the project remains the same and is approved by the ex-advisor, new advisor and all the new qualifying examination committee members.

Each Ph.D. candidate submits the completed dissertation to a reading committee at least one month prior to the dissertation defense. The appointment of the Dissertation Reading Committee is made immediately after the qualifying exam and is necessary for advancing to candidacy. The candidate presents his or her research results in a public seminar sponsored by the dissertation supervisor. The seminar is followed by a defense of the dissertation to the reading committee and attending faculty, who will then decide whether the dissertation is acceptable or requires revision. Successful completion of the dissertation fulfills the final academic requirement for the Ph.D. degree.

Qualifying Exam Committee

The members of the qualifying exam committee must include the following:

• The chair of the committee must be a tenured ladder rank SOE faculty member who is not the student's advisor.
• A ladder rank CS faculty member (may be the advisor).
• A ladder rank UCSC faculty member or a recognized expert in the student's research area as judged by the Graduate Committee.
• The outside member must be a tenured ladder rank faculty member from a department other than CS at UCSC or a recognized expert in the student's research area from outside UCSC. The outside member may not be the student's advisor. In the event that the outside member is not from UCSC she/he must have credentials equivalent to a tenured faculty member as judged by the Graduate Committee and the Graduate Dean. The outside member's CV must be submitted along with the exam committee nomination form.

Additional members may be added to the committee. Students should consult their advisors about the membership of their committee.

Dissertation Reading Committee

The members of the Dissertation Reading Committee must include the following:

• The advisor or supervisor of the student. This is the chair of the committee.
• A ladder rank SOE faculty member who is not the student's advisor. This member must be from CS at UCSC if the advisor is not from CS at UCSC.
• A ladder rank UCSC faculty or a recognized expert in the student's research area with credentials equivalent to a ladder rank UCSC faculty member as judged by the Graduate Committee.

If you have two advisors you should list both as co-chairs. Additional members may be added to the committee. Students should consult their advisors about the membership of their committee. The Dissertation Reading Committee must be appointed in order to advance to candidacy.

Tips

If you are inviting someone from outside to serve on your committee and it is not clear whether their credentials will satisfy the requirements for the outside member, then it is advisable to list them either as the third member or an additional fifth member of the committee. to avoid embarassing them and delaying the appointment of the committtee.

A ladder rank faculty (Academic Senate member) holds the title of Assistant Professor, Associate Professor, or Professor. Associate Professors and Professors have tenure.

Transfer Credit

Up to 3 SOE courses fulfilling the degree requirements of either the MS or Ph.D. degrees may be taken before beginning the graduate program through the concurrent enrollment program.

Ph.D. students who have previously earned a master's degree in a related field at another institution may substitute courses from their previous university with approval of the advisor and the graduate committee. Courses from other insitutions may not be applied to the MS degree course requirements.

Petitions should be submitted along with the transcript from the other institution or UCSC extension. For courses taken at other institutions copies of the syllabi, exams, and other course work should accompany the petition. Such petitions are not considered until the completion of at least one quarter at UCSC.

A total of at most three courses may be transferred from concurrent enrollment and other institutions.

Review of Progress

Each year, the faculty reviews the progress of every student. Students not making adequate progress towards completion of degree requirements (see Graduate Handbook for policy on satisfactory academic progress ) are subject to dismissal from the program. Students with academic deficiencies may be required to take additional courses. Full-time students with no academic deficiencies are normally expected to complete the degree requirements at the rate of at least two courses per quarter. Full-time students must complete CMPS 201, CMPE 202, and CMPS 203 within two years and normally must complete the all course requirements within two years for the MS and three years for the PhD.

Students receiving two or more grades of below B or U (fail) in School of Engineering (SoE) courses are not making adequate progress and will be placed on academic probation for the following three quarters of registered enrollment. Withdrawing or taking a leave of absence does not count as enrollment. Part time enrollment is counted as a half quarter of enrollment.

Should any Computer Science graduate student fail an SoE course while on probation, the Computer Science Department may request the Graduate Dean to dismiss that student from the Graduate Program. If after being removed from probation, the student again fails an SoE course, he or she will return immediately to academic probation.

Breadth Requirements - Graduate Studies, CS

There are nine breadth categories. Only the graduate courses appearing below have been approved to be on the breadth list. If the course you want to take does not appear below, it may still count as an elective course. Check the list of approved elective courses . CS and CE courses have prefixes CMPS and CMPE in the UCSC catalog .

Computer Architecture and Networks

• CE 202. Computer Architecture
• CE 220. Parallel Processing
• CE 230. Computer Performance Evaluation
• CE 250. Multimedia Systems (also listed in Image Processing)
• CE 252A. Computer Networks
• CE 252B. Modeling of Communication Protocols
• CE 254. High-Speed Computer Networks
• CE 255. Advanced Computer Communication
• CE 257. Wireless and Mobile Networks
• CE 258. Unix Networking Internals

Computer Graphics/ Scientific Visualization

• CS 260. Computer Graphics
• CS 262. Computer Animation
• CS 290B. Advanced Topics in Computer Graphics

Machine Learning / Artificial Intelligence

• CS 240. Artificial Intelligence
• CS 241. Knowledge Engineering
• CS 242. Machine Learning
• CS 290C. Advanced Topics in Machine Learning
• CS 290D. Neural Computation

Software Engineering and Programming Languages

• CS 204. Compiler Design
• CE 220. Parallel Processing
• CS 253. Advanced Programming Languages
• CE 276. Software Engineering
• CS 279. Software Reuse and Component-Based Software Engineering
• CS 290E. Object-Oriented Programming Methodology
• CS 290G. Topics in Software Engineering

Statistics

• ENGR 205. Mathematical Statistics
• ENGR 206. Bayesian Statistics (formerly ENGR 181)
• ENGR 207. Intermediate Bayesian Statistical Modeling
• EE 262. Statistical Signal Processing I (also listed in signal processing)

Systems and Security

• CS 221. Advanced Operating Systems
• CS 223. Advanced Computer Security
• CS 229. Storage Systems
• CS 232. Distributed Systems
• CS 290S. Advanced Topics in Computer Systems
• CS 290X. Cryptography and Computer Security

Databases

• CS 277. Database Systems
• CS 278. Database Systems II
• CS 290H. Topics in Database Systems

Theoretical Computer Science

• CS 210. Computational Models and Complexity
• CS 211. Combinatorial Algorithms
• CS 217. Logic in Computer Science
• CS 290A. Topics in Algorithms and Complexity Theory

Vision, Multimedia, and Image Processing

• CE 250. Multimedia Systems (also listed in Networks)
• EE 250. Digital Signal Processing
• EE 262. Statistical Signal Processing I (also listed in statistics)
• CE 264. Image Analysis and Computer Vision
• EE 264. Image Processing and Reconstruction (formerly CE261)
• CE 263. Data Compression and Image Coding
• CE 265. Image and Video Coding
• CE 290V. Advanced Topics in Visual Computing

Approved Elective Courses

All School of Engineering graduate-level courses are approved electives with the exception of 200, 280, and in the case of MS Project, 297 & 299.

Computer Science - Graduate Courses

CMPS 200 Research and Teaching in Computer Science and Engineering (3 credits). F Basic teaching techniques for teaching assistants, including responsibilities and rights of teaching assistants, resource materials, computer security, leading discussion or lab sessions, presentation techniques, maintaining class records, electronic handling of homework, and grading. The course examines research and professional training, including use of the library and online databases, technical typesetting, writing journal and conference papers, publishing in computer science and computer engineering, giving talks in seminars and conferences, and ethical issues in science and engineering. Required for all teaching assistants. Enrollment restricted to graduate students. S. Brandt

CMPS 201 Analysis of Algorithms. F,S Rigorous analysis of the time and space requirements of important algorithms, including worst case, average case, and amortized analysis. Techniques include order-notation, recurrence relations, information-theoretic lower bounds, adversary arguments. Analysis of the key data structures: trees, hash tables, balanced tree schemes, priority queues, Fibonacci and binomial heaps. Algorithmic paradigms such as divide and conquer, dynamic programming, union-find with path compression, augmenting paths. Selected advanced algorithms. Introduction to NP-completeness. Enrollment restricted to graduate students; undergraduate students may enroll in this course if they have completed either course 102 or Computer Engineering 177 and have the consent of the instructor. P. Tantalo, A. Van Gelder, D. Helmbold

CMPS 203 Programming Languages. F Covers current issues in programming languages. Language topics include object oriented, concurrent, functional, and logic programming, and other programmable applications such as symbolic manipulators and simulation. Enrollment restricted to graduate students; undergraduate students may enroll for this course if they have completed course 112 and have the consent of the instructor. C. Flanagan, A. Van Gelder, C. McDowell

CMPS 204 Compiler Design. S A detailed study of the structure and design of a compiler. Topics include compiler structure, pushdown automata, symbol tables, regular expressions and languages, finite state automata, tokens and lexical analyzers, context-free languages, LL(1), recursive descent, LR(1) parsing, attribute grammars as a model of syntax-directed translation, addressing, register allocation, code optimization, and code generation for real machines. Enrollment restricted to graduate students. Offered in alternate academic years. The Staff, W. Mackey

CMPS 210 Computational Models and Complexity. * Finite automata and regular expressions, universal models of computation, computability and unsolvability, relations between complexity classes, hierarchy theorems, reductions, complete problems for the major complexity classes (L, NL, P, NP, PSPACE). Other topics may include complexity of counting and enumeration problems, complexity of approximation, randomized complexity classes. Prerequisite(s): course 201. M. Warmuth, P. Kolaitis, D. Helmbold

CMPS 211 Combinatorial Algorithms. W Fundamental combinatorial algorithms, graph algorithms, flow problems, matching problems, linear programming, integer programming, NP-completeness, approximation algorithms for optimization problems. Prerequisite(s): course 201. Offered in alternate academic years. P. Kolaitis, D. Achlioptas

CMPS 217 Logic in Computer Science. * The applications and uses of formal systems to computer science. Covers the syntax and semantics of propositional logic and first-order logic, normal forms, soundness and completeness theorems, Herbrand's theorem, unification and resolution, foundations of logic programming, automated theorem proving. Other topics may include deductive databases, database query languages, nonmonotonic reasoning. Enrollment restricted to graduate students. Offered in alternate academic years. A. Van Gelder, P. Kolaitis

CMPS 221 Advanced Operating Systems. F A detailed study of the issues involved in operating systems design and implementation. Readings cover current research topics and systems of historical significance. Topics include (but are not restricted to) process and memory management, protection, security, synchronization, performance evaluation, file systems, distributed systems. Enrollment restricted to graduate students; undergraduates by interview only. E. Miller, S. Brandt, D. Long

CMPS 223 Advanced Computer Security. * Overview of research topics in computer and network security. Topics may include cryptographic operations, security properties and policies, authentication and access control, attacks on computer systems and defenses against them, security in programming languages, and network protocols for security. Enrollment restricted to graduate students or consent of instructor. E. Miller, M. Abadi

CMPS 229 Storage Systems. W Topics include storage devices, storage architectures, local file systems, high-performance file systems, and next-generation storage devices and architectures; covers issues of performance, reliability, scalability, robustness, and security. Prerequisite(s): course 221 or permission of instructor. E. Miller, S. Brandt, D. Long

CMPS 232 Distributed Systems. S Overview of research topics in distributed computer systems. Topics may include communication paradigms, process management, naming, synchronization and coordination, consistency and replication, fault tolerance, and security. Examples include distributed operating systems, distributed file and object systems, distributed document systems, and peer-to-peer systems. Prerequisite(s): course 221 or permission of instructor. E. Miller, D. Long

CMPS 240 Artificial Intelligence. S Prepares students for doing research in artificial intelligence. Major topics covered are search and heuristics, knowledge representation, planning, deduction and inference, reinforcement learning, associative pattern retrieval, and adaptive search. Discussion includes current research issues in AI problem-solving methods. Individualized projects. Undergraduates may enroll in this course if they have completed course 140. Enrollment limited to 30. I. Pohl, R. Levinson

CMPS 241 Knowledge Engineering. * Introduction to the acquisition, representation, and application of knowledge in expert systems. Topics include production systems, backward and forward chaining, dependency-directed backtracking, reasoning with uncertainty, certainty factors, fuzzy systems, knowledge representation (rules, frames, and semantic nets), inference engines, and metaknowledge. Discussion includes current research issues in adaptive expert systems. Involves one major project. Undergraduates may enroll in this course if they have completed course 140. Offered in alternate academic years. R. Levinson

CMPS 242 Machine Learning. F Introduction to machine learning algorithms. Covers learning models from fields of statistical decision theory and pattern recognition, artificial intelligence, and theoretical computer science. Topics include classification learning and the Probably Approximately Correct (PAC) learning framework, density estimation and Bayesian learning, EM, regression, and online learning. Provides an introduction to standard learning methods such as neural networks, decision trees, boosting, nearest neighbor, and support vector machines. Requirements include one major experimental learning project or theoretical paper. Enrollment restricted to graduate students. Enrollment limited to 30. M. Warmuth, D. Helmbold

CMPS 244 Artificial Intelligence in Games. W Artificial intelligence has long used game-playing as a metric for progress. Key algorithms such as alpha-beta and HPA search studied. Computer algorithms for backgammon, poker, and chess examined. There will be individulalized projects. Prerequisite(s): course 201; and course 211 or 240 or 242. Enrollment limited to 20. I. Pohl

CMPS 250 Information Theory and Communication. W Physical, technological, and mathematical bases for measures of information in digital signaling and their applications. Physical and information entropies. Optimal codes. Entropy of natural languages. Channel capacity. Optimal communication. Shannon's theorems. Network information theory. Introduction to quantum information theory and computation. Prerequisite(s): Computer Engineering 107 or equivalent, or permission of instructor. Enrollment restricted to graduate students. J. Yellin

CMPS 253 Advanced Programming Languages. S Covers issues in the design, implementation, analysis, and specification of programming languages. Topics include formal semantics (including operational, axiomatic, and denotational semantics), advanced type systems, program analysis (including abstract interpretation and model checking), specification, and verification. Prerequisite(s): course 203 or equivalent. C. Flanagan

CMPS 260 Computer Graphics. * Advanced course in computer graphics. Topics may vary depending on interests of students and research directions in the field. Main topics include in-depth study of curves and surface modeling, deformations, advanced ray tracing, and radiosity methods. Enrollment restricted to graduate students; undergraduates by interview only. Enrollment limited to 20. A. Pang, S. Lodha

CMPS 262 Computer Animation. W An in-depth treatment of computer animation, including its origins in conventional animation, 2-D animation, inbetweening, motion control, morphing, graphical motion editors, animation languages, motion blur, simulation of articulated body motion, realtime animation, and special-purpose animation hardware. Enrollment restricted to graduate students. Enrollment limited to 15. J. Davis

CMPS 272 Evolutionary Game Theory. W Reviews static equilibrium concepts, games of incomplete information, and the traditional theory of dynamic games in discrete time. Develops recent evolutionary game models, including replicator and best reply dynamics, and applications to economics, computer science, and biology. Prerequisite(s): upper-division math courses in probability theory are strongly recommended. (Also offered as Biology 274 and Economics 272. Students cannot receive credit for more than one of these courses.) M. Warmuth, D. Friedman, B. Sinervo

CMPS 277 Database Systems I. * Advanced course on principles of database systems. Main topics include overview of the relational data model and relational query languages; recursive queries, datalog, and fixed-points; query processing and optimization; database design, dependencies, normal forms, and the chase procedure. Additional topics may include information integration, complex objects, semistructured data, and XML. (Formerly Database Systems. ) Prerequisite(s): course 180 (or equivalent) or consent of instructor. Enrollment restricted to graduate students. Enrollment limited to 20. Offered in alternate academic years. W. Tan, N. Polyzotis

CMPS 278 Database Systems II. S Advanced course in implementation techniques for database systems. Topics include transaction management, locking protocols for tables, and locking for index structures; query optimization, database statistics, and query processing; access methods for multidimensional data; and database recovery in centralized and distributed systems. Additional topics may include objects in databases, parallel database systems, advanced query optimization techniques, and data mining. Prerequisite(s): course 277 or 181 (or equivalent) or consent of instructor. Enrollment restricted to graduate students. Enrollment limited to 20. W. Tan, N. Polyzotis

CMPS 279 Software Reuse and Component-Based Software Engineering. * Detailed study of interlocking business, organizational, and technical issues in large-scale software reuse and component-based software engineering. Topics include architecture, design for reuse, domain engineering, model-driven development, domain-specific kits, components, frameworks, software agents, generators, problem-oriented languages, library design, reuse tools, patterns, and aspects. Assumes prior exposure to software engineering topics. Prerequisite(s): computer engineering 276 or consent of instructor. Enrollment restricted to graduate students. Enrollment limited to 20. C. McDowell

CMPS 280A Seminar in Computer Science Research (2 credits). * Weekly seminar covering topics of current research in computer science. Enrollment limited to 30. May be repeated for credit. The Staff

CMPS 280G Seminar on Software Engineering (2 credits). * Weekly seminar covering topics of current research in software engineering. Prerequisite(s): permission of instructor. Enrollment restricted to graduate students. Enrollment limited to 30. May be repeated for credit. N. Whitehead, C. Flanagan, L. De Alfaro, C. McDowell

CMPS 280J Seminar on Computer Graphics (2 credits). F,W,S Weekly seminar covering topics of curren research in computer graphics. Enrollment restricted to graduate students and by permission of instructor. Enrollment limited to 30. May be repeated for credit. J. Davis

CMPS 280S Seminar on Computer Systems (2 credits). F,W,S Weekly seminar series covering topics of current research in computer systems. Enrollment by permission of instructor. Enrollment limited to 30. May be repeated for credit. E. Miller, S. Brandt, D. Long

CMPS 290A Topics in Algorithms and Complexity Theory: Probabilistic Algorithms and Average Case Analysis. * Examines the use of probability theory both in the design and analysis of algorithms. Uses probability theory to analyze the average performance of deterministic algorithms on randomly chosen or "typical" inputs, rather than on worst case inputs. Also a look at algorithms that use randomization, such as random walk and simulated annealing techniques. Examples of specific topics include martingales, random graphs, and rapidly mixing Markov Chains. Enrollment restricted to graduate students. Enrollment limited to 15. Offered in alternate academic years. May be repeated for credit. D. Haussler

CMPS 290B Advanced Topics in Computer Graphics. F,S A graduate seminar in computer graphics on topics from recently published research journal articles and conference proceedings. Topics vary from year to year depending on interests of students. Primary areas of interest are likely to be scientific visualization, modeling, rendering, scattered data techniques, wavelets, and color and vision models. Students read technical papers and present class lectures. Guest lectures supplement the student presentations. A research project is required. Enrollment limited to 15. A. Pang, S. Lodha, J. Davis

CMPS 290C Advanced Topics in Machine Learning. S In-depth study of current research topics in machine learning. Topics vary from year to year but include multi-class learning with boosting and SUM algorithms, belief nets, independent component analysis, MCMC sampling, and advanced clustering methods. Students read and present research papers; theoretical homework in addition to a research project. Prerequisite(s): course 242. M. Warmuth, D. Helmbold

CMPS 290D Neural Computation. * An introduction to the design and analysis of neural network algorithms. Concentrates on large artificial neural networks and their applications in pattern recognition, signal processing, and forecasting and control. Topics include Hopfield and Boltzmann machines, perceptions, multilayer feed forward nets, and multilayer recurrent networks. Enrollment restricted to graduate students. Offered in alternate academic years. D. Haussler, M. Warmuth

CMPS 290E Object-Oriented Programming Methodology. S Object-oriented programming methodology is the application of abstract-data types and polymorphism to coding solution. Topics geared to beginning thesis research in this field. Prerequisite(s): courses 201 and 203. Enrollment restricted to graduate students. Enrollment limited to 20. I. Pohl, C. McDowell

CMPS 290F Applications of Combinatorics. S Combinatorial mathematics, including summation methods, working with binomial coefficients, combinatorial sequences (Fibonacci, Stirling, Eulerian, Harmonic, Bernoulli numbers), generating functions and their uses, Bernoulli processes, and other topics in discrete probability. Oriented toward problem solving, applications mainly to computer science, but also physics. (Formerly Topics in Combinatorial Mathematics .) Prerequisite(s): Computer Engineering 16 and Applied Mathematics and Statistics 27. Enrollment restricted to graduate students and upper-division undergraduates. Offered in alternate academic years. May be repeated for credit. J. Yellin

CMPS 290G Topics in Software Engineering. W Research seminar on current topics in software engineering. Topics vary from year to year depending on the current research of the instructor(s) and interests of students. Students read technical papers from relevant journals and conference proceedings. Synthesis and understanding of materials is demonstrated by a required research project. Prerequisite(s): Computer Engineering 276 recommended. Enrollment restricted to graduate students; undergraduates may enroll with permission of instructor. Enrollment limited to 35. May be repeated for credit. E. Whitehead, L. De Alfaro, C. McDowell, L. Werner

CMPS 290H Topics in Database Systems. * Focuses on current research topics in database systems. Different offerings cover different topics depending on current research of instructor(s) and the interests of students. Students read technical papers from journals and conference proceedings and present class lectures. A research project is required. Prerequisite(s): course 180 (or equivalent) or 277 or consent of instructor. Enrollment restricted to graduate students. Enrollment limited to 20. W. Tan, N. Polyzotis, P. Kolaitis

CMPS 290I Internet Technology and Policy. * Graduate seminar that explores the transforming effects of the Internet on the physical access to information, the content of communications, the security of private information, and the availability of investments. Computer engineering and computer science undergraduate students may enroll in this course if they have completed Computer Engineering 152; other graduate and advanced undergraduate students may enroll with consent of the instructor. J. Yellin

CMPS 290S Advanced Topics in Computer Systems. * Focuses on current research topics in computer systems. Topics vary from year to year depending on the current research of the instructor(s) and the interests of the students. Students read technical papers from current journals and conference proceedings, and present class lectures. A research project is required. Prerequisite(s): course 221. Enrollment restricted to graduate students; qualified undergraduates may enroll with instructor's consent. E. Miller, W. Tan, S. Brandt, D. Long

CMPS 290X Cryptography and Computer Security. * Research seminar on encryption and related technologies. Topics include theory of codes, random sequences and generators, public key cryptosystems, private key cyphers, key exchange protocols, quantum computing and cryptography. Major project required. Prerequisite: interview with instructor. Enrollment limited to 12. J. Yellin

CMPS 290Y Quantum Computing. * Quantum information theory and theory of quantum computation. Quantum algorithms for database search, integer factorization, and order finding. Quantum coding and error correction. Shannon and von Neumann entropies. Quantum communication and cryptography. Prerequisite(s): course 201. Recommended: courses 210, 250, Computer Engineering 251, Physics 215. Knowledge of quantum mechanics helpful but not required. Some knowledge of Shannon information theory strongly recommended. See instructor to discuss course requirements before enrolling. Enrollment restricted to graduate students or seniors by consent of instructor. J. Yellin

CMPS 296 Masters Project (2 credits). F,W,S Independent completion of a masters project under faculty supervision. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

CMPS 297 Independent Study or Research. F,W,S Independent study or research under faculty supervision. Although this course may be repeated for credit, not every degree program will accept a repeated course towards degree requirements. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

CMPS 297F Directed Readings in Machine Learning (2 credits). F,W,S Directed readings in machine learning. Students read, present, and discuss current papers in machine learning. Specific topics include online learning the PAC (Probably Almost Correct) learning model, pattern recognition, and practical learning algorithms. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

CMPS 299 Thesis Research. F,W,S Thesis research conducted under faculty supervision. Although the course may be repeated for credit, not every degree program will accept a repeated course towards degree requirements. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

* Not offered in 2006-07

Computer Science Faculty

Office Phone and E-Mail

Martin Abadi

831-459-1489
On leave

Computer and network security, specification and verification methods, programming languages.

Dimitris Achlioptas

831-459-1081

Threshold phenomena in random graphs and random formulas. Applications of embeddings and spectral techniques in machine learning. Algorithmic analysis of massive networks.

Scott Brandt

831-459-5042

Operating systems, storage systems, real-time systems, distributed systems.

James Davis

831-459-1841

Computer graphics and computer vision, methods for acquiring and manipulating complex graphical models from the real world.

Cormac Flanagan

831-459-5375

Software engineering, programming languages, computer-aided verification, program analysis, defect detection, type systems.

David Helmbold

831-459-2016
Wed 10:00 - 11:00am

Machine learning and computational learning theory.

Phokion G. Kolaitis

831-459-4768

Logic in computer science, database theory, and computational complexity.

Bob Levinson

831-459-2087

Artificial Intelligence research - specifically in the areas of machine learning, heuristic search, knowledge representation, associative pattern retrieval and machine creativity.

Suresh Lodha

831-459-3773

Visualization (GeoSpatial, Scientific, Information, Global Inequality, Uncertainty, Multimodal) Vision (Sensor, Lidar Data, Camera Imagery, Omnidirectional Sensors).

Darrell Long

831-459-2616

Distributed computing systems, operating systems, performance evaluation, data management.

Michael Mateas

831-459-1789

Charlie McDowell

831-459-4772

Computer architecture, parallel computing, microprogramming, compilers, operating systems.

Ethan L. Miller

831-459-1222
On Sabbatical

Archival storage systems, file system security, petabyte-scale network-attached storage, efficiently utilizing next-generation technologies in file systems, storage system benchmarks, algorithms to more efficiently manage storage, and information retrieval from very large text and multimedia corpora.

Alex Pang

831-459-2712

Tensor visualization, scientific visualization, collaboration software, uncertainty visualization, virtual reality interfaces.

Ira Pohl

831-459-3648

Artificial intelligence, the C#, C, C++ and Java programming languages, practical complexity problems, heuristic search methods, deductive algorithms, and educational and social issues.

Neoklis Polyzotis

831-459-1304

Database systems and more specifically on approximation techniques for semi-structured data, on-line database tuning, and declarative data management over files.

Wang-Chiew Tan

831-459-3709
Tues 1:30 - 2:30pm & Thurs 10:00 - 11:00am

Database Systems - Data Provenance, Annotations, Archiving, Information Integration, Scientific Databases, Database Query Languages, Combinatorial Optimization of Database problems.

Allen Van Gelder

831-459-4611
Mon/Wed 3:30 - 4:30pm

Development of algorithms for propositional satisfiability, methods for verifiable software, theorem proving, analysis of algorithms, parallel algorithms, computer graphics, and scientific visualization.

Manfred Warmuth

831-459-4950

Jim Whitehead

831-459-1227

Software evolution, software configuration management, remote collaborative authoring, hypertext, hypertext versioning, and Internet information systems.

Joel Yellin