05. Demystifying the Internet. This course provides an introductory survey of topics in computer science that are related to the Internet. Students will become familiar with the history and underlying structure of the Internet and with technologies such as email, web browsers, search engines, and web page design tools. We will learn about the science behind the technology: topics to be addressed include network design and network protocols, limitations of modern encryption methods, and applications of algorithmics and artificial intelligence to the design of search engines. Some time will also be spent considering social issues such as privacy, worms and viruses, spam, cookies, and encryption policy. Two class meetings per week, with occasional in-class lab sessions.
This course does not provide prerequisite credit for any computer science course, nor does it count towards the computer science major. No previous experience with computers is required. Limited to 40 students. Omitted 2007-08.
11. Introduction to Computer Science I. This course introduces ideas and techniques that are fundamental to computer science. The course emphasizes procedural abstraction, algorithmic methods, and structured design techniques. Students will gain a working knowledge of a block-structured programming language and will use the language to solve a variety of problems illustrating ideas in computer science. A selection of other elementary topics will be presented, for example: the historical development of computers, comparison and evaluation of programming languages, and artificial intelligence. A laboratory section will meet once a week to give students practice with programming constructs. Two class hours and one one-hour laboratory per week.
First semester: The Department. Second semester: Professor Rager.
12. Introduction to Computer Science II. A continuation of Computer Science 11. This course will emphasize more complicated problems and their algorithmic solutions. The object-oriented programming paradigm will be discussed in detail, including data abstraction, inheritance and polymorphism. Other topics will include the implementation of simple data structures and the use of finite-state machines in algorithm design. A laboratory section will meet once a week to give students practice with programming constructs. Two class hours and one one-hour laboratory per week.
Requisite: Computer Science 11 or consent of the instructor. This course is the appropriate starting point for most students with some prior programming experience. It is open to students who took Computer Science 11 before 2003-04 only with consent of the instructor. First semester: Professor Kaplan. Second semester: Professor L. McGeoch.
14. Introduction to Computer Systems. This course will provide an introduction to computer systems, stressing how computers work. Beginning with Boolean logic and the design of combinational and sequential circuits, the course will discuss the design of computer hardware components, microprocessing and the interpretation of machine instructions, and assembly languages and machine architecture. The course will include a brief introduction to operating systems and network communication. A laboratory section will allow students to design and build digital circuits and to develop assembly language programs. Three class hours and one one-hour laboratory per week.
Requisite: Computer Science 11 or some programming experience. Second semester. Professor C. McGeoch.
15. Scientific Computing. (Also Physics 15.) This course explores how computation can be used effectively to solve problems arising in scientific disciplines. Topics include numerical integration, solving systems of equations and differential equations, root finding, the fast Fourier transform, statistical tests, random number generation, curve fitting, error analysis, and simulation of physical systems. We will emphasize ways of constructing correct, efficient algorithms and of implementing those algorithms well
No previous programming experience is required, but quantitative aptitude is essential. Students will be expected to learn the basics of programming in the first few weeks and will do substantial programming throughout the semester.
Requisite: Mathematics 11. First semester. Professors Hall and L. McGeoch.
21. Data Structures. A fundamental problem in computer science is that of organizing data so that it can be used effectively. This course introduces basic data structures and their applications. Major themes are the importance of abstraction in program design and the separation of specification and implementation. Program correctness and algorithm complexity are also considered. Data structures for lists, stacks, queues, trees, sets and graphs are discussed. This course will provide advanced programming experience. Three class hours per week.
Requisite: Computer Science 12. First semester. Professor L. McGeoch.
23. Programming Language Paradigms. The main purpose of a programming language is to provide a natural way to express algorithms and computational structures. The meaning of “natural” here is controversial and has produced several distinct language paradigms; furthermore the languages themselves have shaped our understanding of the nature of computation and of human thought processes. We will explore these paradigms and discuss the major ideas underlying language design. We will apply formal methods to analyze the syntax and semantics of programming languages. Several languages will be introduced to illustrate ideas developed in the course. Three class meetings per week. Offered in alternate years.
Requisite: Computer Science 21 or consent of the instructor. Omitted 2007-08.
24. Artificial Intelligence. An introduction to the ideas and techniques that allow computers to perform intelligently. The course will cover both methods to solve “general” problems (e.g., heuristic search and theorem provers) and “expert systems” which solve specific problems (e.g., medical diagnosis). Laboratory work will include introductions to LISP and/or PROLOG and to special AI tools. Other topics will be chosen to reflect the interest of the class and may include: communicating in English, game playing, planning, vision and speech recognition, computers modeled on neurons, learning, modeling of human cognitive processes and the possibility and implications of the existence of non-human intelligence. Three class meetings per week. Offered in alternate years.
Requisite: Computer Science 11. First semester. Professor Rager.
25. Artificial Intelligence II.
Omitted 2007-08.
27. Cryptography. Banks, businesses, and governments have long needed the ability to transmit information between computers while preventing eavesdroppers from acquiring the information. With the expansion of electronic commerce on the Internet, individuals need similar assurance that their transactions are private. One way to try to keep information secret is to encrypt it before transmitting it. Encryption can also be used to achieve other goals of secure communications, such as permitting “digital signatures” on electronic messages in order to prevent the transmission of fraudulent messages. In this course we will study a variety of encryption schemes, how they can be used, and how secure they are. Topics will include classical cryptosystems, the data encryption standard, public-key cryptography, key escrow systems, and public policy on encryption. Three one-hour lectures per week. Offered in alternate years.
Requisites: Computer Science 21 and one of Mathematics 15, 24, 26, or 28. Omitted 2007-08.
29. Networks. Computing networks have fundamentally changed the ways we use computers. The ubiquity of networks and their broad range of uses have introduced substantial challenges in the design and analysis of computer communication. It is now critical that any pair of computers be able to communicate large amounts of data with minimal delay, thus producing challenges for the design, management, and analysis of networks.
This course will examine the underlying concepts that make computer networks possible. We will begin with the problems of communicating between two computers, and then we will address the problems of building generalized networks for an arbitrary number of computers. Topics will include layered network structure, signaling methods and their theoretical limitations, error detection and correction, flow control, routing, congestion, protocol design, compression, encryption, programming interfaces, and security.
Requisite: Computer Science 11. Second semester. Professor Kaplan.
31. Algorithms. This course addresses the design and analysis of computer algorithms. Although theoretical analysis is emphasized, implementation and evaluation techniques are also covered. Topics include: set algorithms such as sorting and searching, graph traversal and connectivity algorithms, string algorithms, numerical algorithms, and matrix algorithms. Algorithm design paradigms will be emphasized throughout the course. The course will end with a discussion of the theory of NP-Completeness and its implications. Four class hours per week.
Requisites: Computer Science 21 and Mathematics 15, 26, or 28 or consent of the instructor. First semester. Professor C. McGeoch.
32. Introduction to Computer Graphics and Geometric Modeling. This course covers basic concepts and techniques in Computer Graphics and Geometric Modeling, including color, lighting, shading, ray tracing, hidden surface algorithms, solid modeling and radiosity. Fractals, Bezier and B-spline curves and surfaces, and subdivision schemes will also be discussed. Emphasis will be placed on mathematical methods underlying these basic concepts and techniques.
Requisites: Mathematics 11, Computer Science 11 or 12, or consent of the instructor. First semester. Visiting Lecturer Goldman.
37. Compiler Design. An introduction to the principles of the design of compilers, which are translators that convert programs from a source language to a target language. Some compilers take programs written in a general-purpose programming language, such as C, and produce equivalent assembly language programs. Other compilers handle specialized languages. For instance, text processors translate input text into low-level printing commands. This course examines techniques and principles that can be applied to the design of any compiler. Formal language theory (concerning regular sets and context-free grammars) is applied to solve the practical problem of analyzing source programs.
Topics include: lexical analysis, syntactic analysis (parsing), semantic analysis, translation, symbol tables, run-time environments, code generation, optimization, and error handling. Each student will design and implement a compiler for a small language. Three class hours per week. Offered in alternate years.
Requisites: Computer Science 14 and 21. Second semester. Professor L. McGeoch.
38. Theoretical Foundations of Computer Science. This course covers basic mathematical concepts that are essential in computer science, and then uses them to teach the theory of formal languages and machine models of languages. The notion of computability will be introduced in order to discuss undecidable problems. The topics covered include: regular, context-free and context-sensitive languages, finite state automata, Turing machines, decidability, and computational complexity. Three class hours per week. Offered in alternate years.
Requisites: Computer Science 11 and Mathematics 15, 26 or 28 or consent of the instructor. Omitted 2007-08.
39. Principles of Operating System Design. An introduction to the design and implementation of operating systems. The problem of managing computer resources is complex, and there are significant system design issues concerning process management, input/output control, memory management, and file systems. This course examines these issues and the principles that are the basis of modern operating systems. Topics include: interprocess communication, process scheduling, deadlock avoidance, device drivers, virtual memory, and security. Three class hours per week. Offered in alternate years.
Requisites: Computer Science 14 and 21. Omitted 2007-08.
40. Seminar in Computer Science. The topic for 2005 is Computational Biology. Recent advances in understanding the molecular basis of life rely not only on the traditional laboratory methods of the biologist but also on computational techniques for extracting meaning from enormous amounts of data. This field presents hard new problems to the computer scientist, as well as opportunities to bring existing techniques to bear on a new domain. In this course we will study algorithms and data structures that address such problems as multiple sequence alignment, physical mapping, similarity search, gene detection, protein structure prediction, genome rearrangements, and the construction of phylogenetic trees.
Requisite: Computer Science 21. Omitted 2007-08.
77, 78. Senior Departmental Honors.
Open to seniors with consent of the Department. First and second semesters. The Department.
97, 98. Special Topics. Independent reading.