Pre-Fall 2015 Ph.D. Curriculum

The PhD program consists of 4 parts:

• courses
• qualifying exams
• dissertation proposal
• dissertation

n order to obtain your PhD degree, you must complete a minimum of 75 credits of graduate work beyond the BS degree, including at least 21 credits of dissertation. A Master of Science in Computer Science may be transferred as 30 credits without taking individual courses into consideration. Other graduate coursework may be transferred on a course-by-course basis. This includes courses taken for degrees other than a Master of Science in Computer Science.

You are required to take at least 2 courses of each of the following 3 areas at the School of Engineering. You should choose courses that DO NOT have substantial overlap with courses that you have taken previously at the School of Engineering or elsewhere. You must receive at least a grade of B in each of the 6 courses and a GPA over these 6 courses of at least 3.5. If you are a full-time student, you must complete these course requirements by the end of your second year.

Systems Core Area

3 Credits Computer Architecture II CS-GY 6143

An overview of state-of-the-art single-core systems, including advanced pipelining, super-scalar, vector processors, VLIW and vector processing. High-performance computing systems: Computer systems that improve performance and capacity by exploiting parallelism. Selected topics in parallel computing are introduced, such as interconnection networks, parallel algorithms, GPUs, PRAMs, MIMD and SIMD machines. Alternatives to traditional computing are discussed, including GPUs, TPUs, systolic arrays, neural networks and experimental systems.
Prerequisite: Graduate standing and CS-GY 6133.

3 Credits Operating Systems II CS-GY 6243

This course surveys recent important commercial and research trends in operating systems. Topics may include virtualization, network server design and characterization, scheduling and resource optimization, file systems, memory management, advanced debugging techniques, data-center design and energy utilization.
Prerequisite: Graduate standing and CS-GY 6233.

3 Credits Distributed Operating Systems CS-GY 6253

This course introduces distributed-networked computer systems. Topics: Distributed control and consensus. Notions of time in distributed systems. Client/Server communications protocols. Middleware. Distributed File Systems and Services. Fault tolerance, replication and transparency. Peer-to-peer systems. Case studies of modern commercial systems and research efforts.

3 Credits Computer Networking CS-GY 6843

This course takes a top-down approach to computer networking. After an overview of computer networks and the Internet, the course covers the application layer, transport layer, network layer and link layers. Topics at the application layer include client-server architectures, P2P architectures, DNS and HTTP and Web applications. Topics at the transport layer include multiplexing, connectionless transport and UDP, principles or reliable data transfer, connection-oriented transport and TCP and TCP congestion control. Topics at the network layer include forwarding, router architecture, the IP protocol and routing protocols including OSPF and BGP. Topics at the link layer include multiple-access protocols, ALOHA, CSMA/CD, Ethernet, CSMA/CA, wireless 802.11 networks and linklayer switches. The course includes simple quantitative delay and throughput modeling, socket programming and network application development and Ethereal labs.
Knowledge of Python and/or C. Prerequisite: Graduate standing.

3 Credits Information, Security and Privacy CS-GY 6813

This course introduces Information Systems Security and covers cryptography, capability and access control mechanisms, authentication models, security models, operating systems security, malicious code, security-policy formation and enforcement, vulnerability analysis, evaluating secure systems.
Prerequisite: Graduate standing. *Online version available.

3 Credits Network Security CS-GY 6823

This course begins by covering attacks and threats in computer networks, including network mapping, port scanning, sniffing, DoS, DDoS, reflection attacks, attacks on DNS and leveraging P2P deployments for attacks. The course continues with cryptography topics most relevant to secure networking protocols. Topics covered are block ciphers, stream ciphers, public key cryptography, RSA, Diffie Hellman, certification authorities, digital signatures and message integrity. After surveying basic cryptographic techniques, the course examines several secure networking protocols, including PGP, SSL, IPsec and wireless security protocols. The course examines operational security, including firewalls and intrusion-detection systems. Students read recent research papers on network security and participate in an important lab component that includes packet sniffing, network mapping, firewalls, SSL and IPsec.
Prerequisite: Graduate standing. * Online version available.

Theory Core Area

Note: One of the 2 courses must be CS 6753 unless you have already taken an equivalent course.

3 Credits Design and Analysis of Algorithms II CS-GY 6043

This course covers techniques in advanced design and analysis. Topics: Amortized analysis of algorithms. Advanced data structures: binomial heaps, Fibonacci heaps, data structures for disjoint sets, analysis of union by rank with path compression. Graph algorithms: elementary graph algorithms, maximum flow, matching algorithms. Randomized algorithms. Theory of NPcompleteness and approach to finding (approximate) solutions to NPcomplete problems. Selected additional topics that may vary.
Knowledge of algorithms and data structures equivalent to CS-GY 6033. Prerequisite: Graduate standing.

3 Credits Theory of Computation CS-GY 6753

This course introduces the theory of computation. Topics: Formal languages and automata theory. Deterministic and non-deterministic finite automata, regular expressions, regular languages, context-free languages. Pumping theorems for regular and context-free languages. Turing machines, recognizable and decidable languages. Limits of computability: the Halting Problem, undecidable and unrecognizable languages, reductions to prove undecidability. Time complexity, P and NP, Cook-Levin theorem, NP completeness.
Prerequisites: Graduate standing and CS-GY 6003 (or instructor's permission).
Knowledge of discrete math (equivalent to CS-GY 6003). Prerequisite: Graduate Standing.

3 Credits Applied Cryptography CS-GY 6903

This course examines Modern Cryptography from a both theoretical and applied perspective, with emphasis on ?provable security? and ?application case studies?. The course looks particularly at cryptographic primitives that are building blocks of various cryptographic applications. The course studies notions of security for a given cryptographic primitive, its various constructions and respective security analysis based on the security notion. The cryptographic primitives covered include pseudorandom functions, symmetric encryption (block ciphers), hash functions and random oracles, message authentication codes, asymmetric encryption, digital signatures and authenticated key exchange. The course covers how to build provably secure cryptographic protocols (e.g., secure message transmission, identification schemes, secure function evaluation, etc.), and various number-theoretic assumptions upon which cryptography is based. Also covered: implementation issues (e.g., key lengths, key management, standards, etc.) and, as application case studies, a number of real-life scenarios currently using solutions from modern cryptography.
Prerequisite: Graduate standing.

3 Credits Computational Geometry CS-GY 6703

This course introduces data structures and algorithms for geometric data. Topics include intersection, polygon triangulation, linear programming, orthogonal range searching, point location, Voronoi diagrams, Delaunay triangulations, arrangements and duality, geometric data structures, convex hulls, binary space partitions, robot motion planning, quadtrees, visibility graphs, simplex range searching.
Knowledge of algorithms and data structures equivalent to CS-GY 6033. Prerequisite: Graduate Standing.

Programming/Software Core Area

3 Credits Software Engineering I CS-GY 6063

The course emphasizes the full software-engineering approach with alternative approaches. Technical emphasis is on requirements, design, development and modeling. Management issues include software cost estimating and project management. Understanding the processes applicable to the software development/integration cycle and maintenance along with technology changes on quality and development activities is highlighted.
Solid ability to program in Python. Some familiarity with Django is helpful. Please note: The course will not teach how to program in Python. The students are required to be able to do so already. Experience using version control systems (git in particular) is important. Prerequisite: Graduate standing.

3 Credits Software Engineering II CS-GY 6073

The course covers modern, advanced software-engineering approaches with theory and practice orientations. Important design and management issues are analyzed and evaluated. Technical and management tradeoffs in distributed software systems are emphasized. An extensive number of real world case studies are assessed. A class project is required.
Prerequisite: CS-GY 6063 and graduate standing.

3 Credits Principles of Database Systems CS-GY 6083

This course broadly introduces database systems, including the relational data model, query languages, database design, index and file structures, query processing and optimization, concurrency and recovery, transaction management and database design. Students acquire hands-on experience in working with database systems and in building web-accessible database applications.
Knowledge of basic data structures and algorithms (search trees, hash tables, sorting and searching). Knowledge of principles of operating systems and of the client-server architecture. Basic familiarity with the UNIX operating systems. Programming proficiency. Prerequisites: Graduate standing.

3 Credits Compiler Design and Construction CS-GY 6413

This course covers compiler organization. Topics: Lexical analysis, syntax analysis, abstract syntax trees, symbol table organization, code generation. Introduction to code optimization techniques.
Knowledge of discrete math equivalent to CS-GY 6003, and knowledge of fundamental data structures. Prerequisites: Graduate Standing.

3 Credits Interactive Computer Graphics CS-GY 6533

This course introduces the fundamentals of computer graphics with hands-on graphics programming experiences. Topics include graphics software and hardware, 2D line segment-scan conversion, 2D and 3D transformations, viewing, clipping, polygon-scan conversion, hidden surface removal, illumination and shading, compositing, texture mapping, ray tracing, radiosity and scientific visualization.
Knowledge of Data Structures and Algorithms, and be comfortable with C/C++ programming.. Prerequisites: Graduate standing.

3 Credits Artificial Intelligence I CS-GY 6613

Artificial Intelligence (AI) is an important topic in computer science and offers many diversified applications. It addresses one of the ultimate puzzles humans are trying to solve: How is it possible for a slow, tiny brain, whether biological or electronic, to perceive, understand, predict and manipulate a world far larger and more complicated than itself? And how do people create a machine (or computer) with those properties? To that end, AI researchers try to understand how seeing, learning, remembering and reasoning can, or should, be done. This course introduces students to the many AI concepts and techniques.
Knowledge of Data Structures and Algorithms. Prerequisite: Graduate standing.

3 Credits Web Search Engines CS-GY 6913

This course covers the basic technology underlying Web search engines and related tools. The main focus is on large-scale Web search engines (such as Google, Yahoo and MSN Search) and their underlying architectures and techniques. Students learn how search engines work and get hands-on experience in how to build search engines from the ground up. Topics are based on a reading list of recent research papers. Students must work on a course project and may have to present in class.
Prerequisite: Graduate standing

3 Credits Machine Learning CS-GY 6923

This course is an introduction to the field of machine learning, covering fundamental techniques for classification, regression, dimensionality reduction, clustering, and model selection. A broad range of algorithms will be covered, such as linear and logistic regression, neural networks, deep learning, support vector machines, tree-based methods, expectation maximization, and principal components analysis. The course will include hands-on exercises with real data from different application areas (e.g. text, audio, images). Students will learn to train and validate machine learning models and analyze their performance.
Knowledge of undergraduate level probability and statistics, linear algebra, and multi-variable calculus. Prerequisite: Graduate standing.

3 Credits Application Security CS-GY 9163

This course addresses the design and implementation of secure applications. Concentration is on writing software programs that make it difficult for intruders to exploit security holes. The course emphasizes writing secure distributed programs in Java. The security ramifications of class, field and method visibility are emphasized.
Knowledge of Information, Security and Privacy equivalent to CS-GY 6813. Prerequisite: Graduate standing

Computer Science and Engineering Department faculty may modify these area course offerings from time to time. Certain selected topics courses may be used to fulfill these requirements with written permission from the department.

Additionally, for the following courses, you are required to take the course unless you have already taken an equivalent course (at either the graduate or undergraduate level) with a grade of B or higher. If you have taken an equivalent course and received a B grade or higher, you will not be permitted to take it at the School of Engineering as part of this PhD program without special permission:

3 Credits Computer Architecture I CS-GY 6133

Computer architecture design: Instruction set design techniques, performance and cost; Extensions to traditional instruction sets. An instruction set studied in detail. Processor implementations: Unpipelined execution and its improvement by means of pipelining. Advanced pipelining, including branch prediction, out-of-order execution and superscalar execution, is introduced. Alternatives to traditional computing, such as VLIW and vector computation are described. Improving computer capacity, by improving the memory hierarchy is studied, including advanced cache memory, main memory and virtual memory implementations. An introduction to high-performance computing, including multi-core processors.
Prerequisite: Graduate standing and Knowledge of Computer Architecture and Organization equivalent to CS-UY 2214.

3 Credits Introduction to Operating Systems CS-GY 6233

This course introduces basic issues in operating systems. Topics: Threads, processes, concurrency, memory management, I/O Control and case studies.
Prerequisite: Graduate standing.

3 Credits Design and Analysis of Algorithms I CS-GY 6033

This course reviews basic data structures and mathematical tools. Topics: Data structures, priority queues, binary search trees, balanced search trees. Btrees. Algorithm design and analysis techniques illustrated in searching and sorting: heapsort, quicksort, sorting in linear time, medians and order statistics. Design and analysis techniques: dynamic programming, greedy algorithms. Graph algorithms: elementary graph algorithms (breadth first search, depth first search, topological sort, connected components, strongly connected components), minimum spanning tree, shortest path. String algorithms. Geometric algorithms. Linear programming. Brief introduction to NP completeness.
Knowledge of Discrete Math equivalent to CS-GY 6003, and knowledge of Fundamental Data Structures. Prerequisites: Graduate Standing

3 Credits Programming Languages CS-GY 6373

This course covers the structures, notations and semantics of programming languages. Topics: Issues of scope, type structure and parameter passing. Control structures, including support for exception handling and concurrency. Abstract data types and object oriented languages. Programming in the large. Implementation issues. Functional, logic programming languages. Examples from a variety of languages.
Knowledge of C, Python, Linux. Prerequisites: Graduate standing.

The purpose of the qualifying exam is to assess your knowledge of computer science and your ability to perform dissertation-level research. You will be evaluated based on 2 components: a research exam and course work.

After entering the PhD program, you will work on a research project under the direction of a research adviser. By the end of the second year, you must take a research exam based on this work. The research exam will be tailored to the your individual research, and will have the following 3 parts: (1) written report, (2) oral presentation, (3) answering questions posed by the research exam committee. The research exam will be used to assess your ability to do dissertation-level research. The exact format of the report and presentation can vary depending upon your research accomplishments up until that time and the focus area. You may schedule the research exams during 2 periods of time in the year; a range of dates around the end of the fall and spring semesters will be announced in advance by the graduate director.

Your overall course performance will be evaluated as part of the qualifying exam process. Special emphasis will be given to performance in PhD core courses. If you take the research exam in your third semester, you must complete at least 4 PhD core courses by the end of your third semester in order for your course performance to be evaluated at the end of the third semester. Otherwise, your evaluation will be delayed until the end of the fourth semester, by which time you must have taken all 6 PhD core courses.

Evaluation of your course performance will likely be based on a review your transcripts and possible consultation with your instructors. In special cases, you may be subject to additional evaluation and/or additional written exams in some core course areas.

The Computer Science and Engineering faculty will examine your research-exam results and course performance to decide if you pass or fail the qualifying examination. They can also give you a conditional pass that imposes additional requirements and will be converted to a pass or fail grade.

If you fail the qualifying exam on your first attempt, you may retake it once. You must make your second attempt by the end of the your fifth semester. If you do not pass the qualifying exam on your second attempt, you will be dismissed from the PhD program. You cannot register for dissertation credit until you have passed the qualifying exam.

If you enter the PhD program with a master's degree in computer science, you are urged to take the research exam and at least 4 of the required core courses by the end of your third semester. This gives you the potential to pass the qualifying exam by the end of your third semester and to begin taking thesis credits in your fourth semester.

The last, and most substantial, aspect of the PhD program is the dissertation. The dissertation must embody a significant original research contribution and must be written in accepted scholarly style. The research should be conducted in close consultation with your advisor. It is strongly recommended that you submit at least 1 paper on your research to a refereed archival journal or refereed conference. When your adviser feels that you have obtained sufficiently significant research results and that you have written an acceptable dissertation, a public dissertation defense will be scheduled. It will consist of your oral presentation and questions from the dissertation committee.

Additional requirements for the PhD dissertation are available from the Office of the Associate Provost of Research and PhD programs.