Computer Science 51. Introduction to Computer Science II
Catalog Number: 3411
Henry H. Leitner
Half course (spring term). Tu., Th., 1–2:30. EXAM GROUP: 15, 16
Abstract models for computational processes and their concrete realizations. Functional, imperative, and object-oriented styles of programming; processor and memory architectures; interpretation and compilation of programming languages. State-space search, finite-state processes, formal logic, data and functional abstraction, and syntactic and semantic formalisms as examples of useful abstractions. The engineering of complex software. Laboratory exercises using LISP, C++, and Java.
Prerequisite: Computer Science 50 or equivalent.
*Computer Science 91r. Supervised Reading and Research
Catalog Number: 0361
Steven J. Gortler
Half course (fall term; repeated spring term). Hours to be arranged.
In this course a student may undertake supervised individual study of advanced topics in computer science beyond those covered in regular courses, or may participate in a computer science research project. Students writing theses may enroll in this course while conducting their thesis research and writing. A student wishing to enroll in Computer Science 91r must be accepted by a faculty member who will supervise the course work and will specify the syllabus or project description. A form available in the Division of Engineering and Applied Sciences Academic Office, Pierce Hall 212b, must be filled out with a description of the course work and the basis for its evaluation. This form must be signed by the student and the faculty supervisor and filed in the Academic Office by the date on which study cards are due. A written report of the work carried out in the course is ordinarily required by the beginning of the reading period.
Note: Ordinarily, at most two terms of Computer Science 91r may be taken for academic credit. May not be taken Pass/Fail. Students wishing more information about the range of suitable projects or faculty supervisors should consult the Director of Undergraduate Studies.
Computer Science 124. Data Structures and Algorithms
Catalog Number: 5207
Michael D. Mitzenmacher
Half course (spring term). M., W., 1–2:30. EXAM GROUP: 6, 7
Design and analysis of efficient algorithms. Data structure representations and their use for provably efficient implementation of abstract operations: searching, sorting, set manipulation. Memory management. Graph algorithms. General algorithm design techniques.
Prerequisite: Computer Science 51; some exposure to discrete applied mathematics, such as Applied Mathematics 106 or 107 or Computer Science 121 or Statistics 110, is helpful.
Computer Science 141. Computing Hardware
Catalog Number: 4357
Michael D. Smith
Half course (fall term). M., W., F., at 9, and laboratory hours to be arranged. EXAM GROUP: 2
Introduction to the design, structure, and operation of digital computers; logic circuits and digital electronics; computer arithmetic; computer architecture; and machine language programming. Consideration of the design interactions between hardware and software systems.
Prerequisite: Computer Science 50.
Computer Science 143. Computer Networks
Catalog Number: 6401
H. T. Kung
Half course (fall term). M., W., 2:30–4. EXAM GROUP: 7, 8
Architecture, design, and performance of computer networks. Topics include: the Internet protocols, local area networks, performance analysis, queueing theory, congestion control, multicast, quality of service, and network security. Programming exercises on protocol implementation.
Prerequisite: Computer Science 51.
Computer Science 144. Networks Design Projects
Catalog Number: 5415
H. T. Kung
Half course (spring term). W., F., 4–5:30. EXAM GROUP: 9
Cooperative design and development of a computer network based on new and promising networking concepts which may still be under research. Exploration of real-world design concerns, including survey and critiques of relevant networking literature, early validation of proposed approach, design specification, implementation, testing, and evaluation. Students work in groups, and present weekly status reports. At the end of the class, students will defend their approaches and results in the presence of experts in computer networks.
Note: Enrollment is Limited. Preference given to concentrators in Computer Science who are proficient in computer programming.
Prerequisite: Computer Science 143 or equivalent experience.
[Computer Science 146. Computer Architecture]
Catalog Number: 6520
----------
Half course (spring term). Hours to be arranged.
Review of the fundamental structures in modern processor design. Topics include computer organization, instruction set design, memory system design, pipelining, and other techniques to exploit parallelism. Emphasis on a quantitative evaluation of design alternatives and an understanding of timing issues.
Note: Expected to be given in 2000–01.
Prerequisite: Computer Science 141.
Computer Science 148. Introduction to VLSI Design
Catalog Number: 1772 Enrollment: Limited to 16
Woodward Yang
Half course (spring term). Tu., Th., 11:30–1. EXAM GROUP: 13, 14
Presentation of concepts and techniques for the design and fabrication of VLSI integrated circuits. Topics include basic semiconductor device theory, diodes and MOS transistor operation; integrated circuit fabrication technology, VLSI layout and design rules; NMOS and CMOS circuit design, memory and processor design, advanced VLSI systems architecture; testing of VLSI circuits; and analog CMOS circuit design. CAD tools for design and simulation are used extensively for homework assignments and for a final VLSI design project. High quality projects may be fabricated at an external VLSI foundry.
Prerequisite: Computer Science 141 and Engineering Sciences 154, or permission of instructor.
Computer Science 152. Principles of Programming Languages
Catalog Number: 6841
Norman Ramsey
Half course (fall term). M., W., F., at 11. EXAM GROUP: 4
Intellectual tools needed to design, evaluate, and choose programming languages. Historical influence of theory, software engineering, and implementation technique on language design. Case studies, reinforced by programming exercises. Emphasizes advanced languages, abstraction mechanisms. Includes functional, object-oriented, and logic paradigms. Focuses on ideas and techniques most relevant to practitioners, but covers theoretical topics crucial for intellectual rigor: specification based on abstract syntax, lambda calculus, type systems,and dynamic semantics. Grounding sufficient to read professional literature.
Prerequisite: Students must have good programming skills. Must be comfortable with recursion and with basic mathematical ideas and notations.
[Computer Science 153. Principles of Programming Language Compilation]
Catalog Number: 2842
----------------
Half course (fall term). Hours to be arranged.
The underlying theory of the implementation of interpreters and compilers for programming languages, associated algorithms, and pragmatic issues. Theoretical emphasis on the relation to programming language theory and practical emphasis on applications outside of programming language implementation proper. Topics include lexical analysis, parsing algorithms, type checking and inference, code generation, run-time issues, optimization.
Note: Expected to be given in 2000–01.
Prerequisite: Computer Science 121 and 152.
Computer Science 161. Operating Systems
Catalog Number: 4347
Half course (spring term). Tu., Th., 1–2:30. EXAM GROUP: 15, 16
The fundamental principles of resource management and abstraction in modern operating systems. Control abstractions: thread, processes, scheduling synchronization. Storage abstractions: dynamic memory allocation, virtual memory, file system design. Communication abstractions: interprocess communication, networking. Case studies. Design and implementation of parts of a multiuser multitasking virtual-memory operating system.
Note: Open to students who achieved an honor grade (B- or better) in Computer Science 51 and who have experience developing large software systems.
Prerequisite: Computer Science 51.
Computer Science 165. Introduction to Database Systems
Catalog Number: 4712
Ugo O. Gagliardi
Half course (fall term). F., 2:30–5:30. EXAM GROUP: 7, 8, 9
Design principles for modern distributed database systems. Topics include: extended E/R, relational and object-oriented data models; database connectivity and the Java virtual machine; query processing, persistence, concurrency control, back-up and recovery; Web information organization, indexing and retrieval; search engines’ architecture and algorithms.
Prerequisite: Computer Science 161 or permission of instructor.
Computer Science 175. Computer Graphics
Catalog Number: 3771
Steven J. Gortler
Half course (fall term). W., F., 4–5:30. EXAM GROUP: 9
The computational aspects of computer graphics. Two major themes are image rendering (viewing transformations, clipping, visible-surface processing, raster algorithms, reflection models, lighting models, surface shading, antialiasing, ray tracing, radiosity, and volume rendering) and scene modeling (modeling transformations, curves and surfaces, texture mapping, data-amplification techniques, constructive solid geometry, scalar- and vector-field data, and animation). Ancillary topics include color compression, image compression, image compositing, graphical user interfaces, and special machine architectures for computer graphics.
Prerequisite: Computer Science 51, Applied Mathematics 21a or Mathematics 21a, and experience with a large software project (preferably written in C), e.g., Computer Science 153, 161, or 165.
Computer Science 181. Intelligent Machines: Perceptual Processes and Stochastic Methods
Catalog Number: 6454
Avi Pfeffer
Half course (spring term). M., W., 2:30–4. EXAM GROUP: 7, 8
Introduction to stochastic methods for vision and speech. Markov random fields and hidden Markov models. Statistical pattern recognition and categorization. Neural nets. Bayesian reasoning. Discussion of relevant psychological and neurophysiological results.
Prerequisite: Computer Science 51, 121, and Statistics 110, or equivalent.
Computer Science 182. Intelligent Machines: Reasoning, Actions, and Plans
Catalog Number: 0134
Barbara J. Grosz
Half course (fall term). M., W., 1–2:30. EXAM GROUP: 6, 7
Introduction to AI focused on approaches to problems of reasoning about action. Search and game-playing. Knowledge representation. Partial-order planning; representations of actions; techniques for handling goal interactions. Resource-limited planning; situated agents. Reasoning under uncertainty. Discussion of relevant work in philosophy and decision theory; applications to vision, language, robotics.
Prerequisite: Computer Science 51; Computer Science 121 (may be taken concurrently).
Computer Science 222. Algorithms at the Ends of the Wire
Catalog Number: 2493
Michael D. Mitzenmacher
Half course (fall term). Tu., Th., 2:30–4. EXAM GROUP: 16, 17
Covers topics related to what is done with information before and after it is sent across a network. Themes include compression, cryptography, coding, and information retrieval related to the World Wide Web. Theoretical aspects are emphasized, although current practice and recent advances are also a focus. Requires a major final project.
Prerequisite: Computer Science 124.
[Computer Science 224r. Randomness in Computation]
Catalog Number: 3380
Michael O. Rabin
Half course (fall term). Hours to be arranged.
Exploration of the surprising efficacy of randomization in the solution of algorithmic and general computer science problems. Applications include number theoretic algorithms, cryptographic protocols, computations in finite fields, computational geometry. CS applications will include routing in networks, parallel algorithms, pattern matching, agreement protocols for distributed systems. We shall also deal with programs that check and correct their own work and with Probabilistically Checkable Proofs (PCP). The probability theory prerequisites will be covered.
Note: Expected to be given in 2000–01.
Computer Science 226r. Efficient Algorithms
Catalog Number: 1749
Michael O. Rabin
Half course (fall term). Tu., Th., 11:30–1. EXAM GROUP: 13, 14
A survey of important computer algorithms for numerical and data manipulation problems and their applications in actual computing situations. Topics include combinatorial algorithms, string matching, FFT and its applications, algebraic computations, randomized algorithms in algebra number theory and geometry, maximal flows, error correcting codes, public key cryptography, protocols for distributed systems, and parallel algorithms.
Note: Expected to be omitted in 2000–01.
[Computer Science 228. Computational Learning Theory]
Catalog Number: 0364
Leslie G. Valiant
Half course (fall term). Hours to be arranged.
Possibilities of and limitations to performing learning by computational agents. Topics include computational models, polynomial time learnability, learning from examples and learning from queries to oracles. Computational limitations. Statistical limitations. Applications to Boolean functions, automata and geometric functions. Learning algorithms for models of neural computation.
Note: Expected to be given in 2000–01.
Prerequisite: Computer Science 121 or equivalent.
[Computer Science 231. Parallel Computation]
Catalog Number: 6999
Leslie G. Valiant
Half course (spring term). Hours to be arranged.
Models of parallel computation and their relationship: circuits, fixed networks, shared memory, bulk-synchrony. Automatic parallelization and its limits. Parallel algorithms for numerical problems such as solving linear systems. Algorithms for discrete problems such as sorting. Algorithms and programs that are efficiently portable among a variety of parallel architectures.
Note: Expected to be given in 2000–01.
Computer Science 244. Advanced Networks Design Projects
Catalog Number: 3018
H. T. Kung
Half course (spring term). W., F., 4–5:30. EXAM GROUP: 9
The contents and course requirements are similar to those of Computer Science 144, with the exception that students enrolled in Computer Science 244 are expected to devise novel algorithms and protocols, and demonstrate their advantages over existing ones. Substantial implementation and documentation are required.
Note: Enrollment is limited. Preference given to graduate students, or upper-class concentrators, in Computer Science who are proficient in computer programming.
Prerequisite: Computer Science 143 or equivalent experience.
[*Computer Science 246 (formerly Computer Science 246r). Advanced Computer Architecture]
Catalog Number: 0979
Half course (spring term). Hours to be arranged.
The contents and course requirements are similar to those of Computer Science 146, with the exception that students enrolled in Computer Science 246 are required to conduct extra readings and to complete an additional term project.
Note: Expected to be given in 2000–01.
Prerequisite: Background in computer software and hardware, and permission of the instructor.
Computer Science 253. Advanced Principles of Programming Language Compilation
Catalog Number: 2901
Michael D. Smith
Half course (spring term). Tu., Th., 10–11:30. EXAM GROUP: 12, 13
In-depth introduction to compiler optimizations developed to exploit recent advances in computer architecture. Topics include scalar optimization, instruction scheduling for superscalar and VLIW processors, data dependence analysis, interprocedural analysis on both array and pointer variables, cache optimizations such as blocking and prefetching.
Prerequisite: Computer Science 153 or equivalent.
*Computer Science 254r. Programming Methodologies
Catalog Number: 2767
Robert L. Walton
Half course (spring term). W., 4–6. EXAM GROUP: 9
Investigates program analysis, verification, and refinement; programming paradigms including those for parallel and distributed programming; program development and maintenance environments. This year the course will study web computing: schemes for turning the web into a computing resource.
*Computer Science 257. Programming with Concurrency
Catalog Number: 8581
Norman Ramsey
Half course (spring term). Tu., Th., 1–2:30. EXAM GROUP: 15, 16
Concurrency, its influence on program structure, its implementation -- according to interests of participants. Threads, communicating processes, second-class and first-class synchronization, mechanisms, concurrent functional programs. Debugging, modelling, and model-checking. Implementation, including synchronization stack management, scheduling, concurrent garbage collection, heap-allocated activations, first-class continuations. Concurrency support in the portable assembly language C--.
Prerequisite: Computer Science 161 or permission of the instructor.
Computer Science 261. Research Topics in Operating Systems
Catalog Number: 6706
Margo I. Seltzer
Half course (fall term). Tu., Th., 1–2:30. EXAM GROUP: 15, 16
A quantitative approach to operating system design and evaluation. Discussion of recent research including extensible operating system architectures, distributed systems, and performance analysis. Overview of research techniques and methodology.
Prerequisite: Computer Science 161, or equivalent.
Computer Science 262. Introduction to Distributed Computing
Catalog Number: 7949
James H. Waldo
Half course (spring term). Tu., Th., 2:30–4. EXAM GROUP: 16, 17
Examination of the special problems associated with distributive computing, especially those associated with partial failure and intrinsic limitations on global knowledge. The course will emphasize the specification and implementation of high level protocols that allow computational entities to collaborate in the face of these problems. Causal ordering, event and RPC based systems, and security problems in distributed systems will be discussed.
Prerequisite: Computer Science 161 or permission of instructor.
Computer Science 265. Advanced Introduction to Database Systems
Catalog Number: 4104
Ugo O. Gagliardi
Half course (fall term). F., 2:30–5:30. EXAM GROUP: 7, 8, 9
The contents and course requirements are similar to those of Computer Science 165, with the exception that students enrolled in Computer Science 265 are expected to conduct a research project.
Prerequisite: Computer Science 161 or permission of instructor.
Computer Science 275. Advanced Computer Graphics
Catalog Number: 5495
Steven J. Gortler
Half course (fall term). W., F., 4–5:30. EXAM GROUP: 9
The contents and course requirements are similar to those of Computer Science 175, with the exception that students enrolled in Computer Science 275 are required to conduct extra readings and to complete an additional term project.
Prerequisite: Computer Science 51, Applied Mathematics 21a or Mathematics 21a, and experience with a large software project (preferably written in C), e.g., Computer Science 153, 161, or 165.
Computer Science 276r. Computer Graphics, Special Topics
Catalog Number: 8097
Steven J. Gortler
Half course (spring term). M., W., 2:30–4. EXAM GROUP: 7, 8
Seminar examining in detail some specific aspect of computer graphics. Specific topics which change from year to year may include: image based rendering, photo-realistic rendering, geometric rerpresentations, representations of motion and animations, computer graphics hardware. Students will make one oral presentation, and create a software implementation of one of the covered concepts.
Prerequisite: Computer Science 175 or 275, or permission of instructor.
Computer Science 279. Topics in Computer-Human Interfaces, Information Retrieval and Visualization
Catalog Number: 2407 Enrollment: Enrollment may be limited.
Stuart M. Shieber
Half course (spring term). Tu., Th., 2:30–4. EXAM GROUP: 16, 17
Seminar providing background and current research in specific topics drawn from one or more of computer-human interfaces, information, retrieval, and information visualization. Intensive lab component emphasizes small group design and implementation of systems in these areas.
Prerequisite: Computer Science 51 and experience developing large software systems as evidenced by successful completion of a systems course requiring a large project.
Computer Science 281r. Artificial Intelligence: Reasoning and Planning Systems
Catalog Number: 0707
Avi Pfeffer
Half course (fall term). M., W., 1–2:30. EXAM GROUP: 6, 7
In-depth introduction to formalisms for knowledge representation and techniques for reasoning and planning. Topics: formal logic-based representations; probabilistic reasoning; nonmonotonic logics; truth-maintenance systems; qualitative reasoning; inheritance hierarchies; computational approaches to reasoning about actions and time, including actions of multiple agents, nonlinear planning, plan recognition; reasoning about knowledge, belief, and action.
Prerequisite: Computer Science 182, or permission of instructor.
Computer Science 283. Computer Vision
Catalog Number: 4475
Michael S. Brandstein
Half course (fall term). Tu., Th., 2:30–4. EXAM GROUP: 16, 17
Vision as an ill-posed inverse problem. Regularization. Bayesian approaches to vision. Image enhancement and feature extraction. Structure from motion, texture, shading, and binocular stereo. Active vision.
Note: Expected to be omitted in 2000–01.
[*Computer Science 287r. Natural Language Processing]
Catalog Number: 3306
Stuart M. Shieber
Half course (spring term). Hours to be arranged.
Principles and techniques of natural language processing, including grammar formalisms, syntactic analysis, semantic interpretation, and associated algorithms.
Note: Expected to be given in 2000–01.
Prerequisite: Computer Science 121 and 152.
Computer Science 288. Computational Models of Discourse
Catalog Number: 1392
Barbara J. Grosz
Half course (spring term). Tu., Th., 11:30–1. EXAM GROUP: 13, 14
Computational theories of discourse (text and dialogue) structure and processing. Topics include: anaphora, focusing, plans and speech acts, plan recognition algorithms, models of collaborative planning, intonation. Discussion of dialogue and text understanding systems. Application to the design of human-computer interface systems.
Note: Expected to be omitted in 2000–01.
Prerequisite: Computer Science 182 or 287r or equivalent, or permission of instructor.
Computer Science 299r. Special Topics in Computer Science
Catalog Number: 4592
Venkatesh Narayanamurti
Half course (fall term; repeated spring term). Hours to be arranged.
Supervision of experimental or theoretical research on acceptable computer science problems and supervision of reading on topics not covered by regular courses of instruction.
Note: Open to graduate students and A.B./S.M. candidates only. Students must arrange such work with a member of the Division. This course is ordinarily taken with the approval of the Committee on Higher Degrees in certain cases when a letter grade is required. Applicants should file a project sheet before study cards are filed. Project sheets may be obtained from the Academic Office, Pierce Hall 212b.
*Computer Science 311,312. Natural Language Processing, AI Planning, and Collaborative Systems
Catalog Number: 4677,6223
Barbara J. Grosz 1599
*Computer Science 315,316. Software Engineering
Catalog Number: 2402,2403
Ugo O. Gagliardi 1077
*Computer Science 321,322. Databases, Operating System, and Software Design
Catalog Number: 4085,4086
Margo I. Seltzer 3371
*Computer Science 323,324. Programming Languages, Natural Language Processing, and Human-Computer Interfaces
Catalog Number: 2450,2453
Stuart M. Shieber 2456
*Computer Science 325. Programming Languages and Tools
Catalog Number: 8055
Norman Ramsey 2831
*Computer Science 326. Programming Languages and Tools
Catalog Number: 0747
Norman Ramsey 2831
*Computer Science 327,328. Mathematical Logic, Theory of Computation
Catalog Number: 1160,3576
Harry R. Lewis 4455
*Computer Science 329,330. Operating System Theory and Architectural Design
Catalog Number: 6172,2839
Ugo O. Gagliardi 1077
*Computer Science 345,346. High-Performance Computer Systems
Catalog Number: 6154,6156
Michael D. Smith 3372
*Computer Science 351,352. Complexity of Computations: Concurrent Programming and Synchronization
Catalog Number: 0218,0255
Michael O. Rabin 7003
*Computer Science 353,354. Representation and Reasoning, Machine Learning and Decision Making
Catalog Number: 6816,1843
Avi Pfeffer 2830
*Computer Science 355,356. Computational Complexity, Parallel Algorithms, Machine Learning, and Neural Computation
Catalog Number: 0345,0346
Leslie G. Valiant 7396
*Computer Science 359,360. Online Algorithms and Randomized Algorithms
Catalog Number: 2104,1477
Michael D. Mitzenmacher 7748
*Computer Science 375,376. Computer Graphics
Catalog Number: 6832,7313
Steven J. Gortler 2824