## Computer Science

**Professor:** Nancy Ide (Chair); **Assistant Professors: **Thomas Ellman, Bradley Richards, Christopher Welty; **Visiting Associate Professor:**Louis Voerman.

**Requirements for Concentration:** Computer Science 101, 102, 203, 224, 240, 241, 245, 331, 334, plus any two other 300–level Computer Science courses, and Mathematics 221 and 263. No course numbered 200 or higher may be elected NRO and counted toward the requirements for concentration.

**Recommendations:** Prospective majors are strongly advised to complete Computer Science 101 and 102 by the end of the freshman year.

Students who intend to pursue graduate studies in computer science are strongly urged to take one or both of Computer Science 340 and 341.

**Advanced placement:** Students eligible for Advanced Placement may be able to bypass Computer Science 102, but not Computer Science 101. Please consult with the department.

**Non–majors:** Students majoring in the sciences are advised to complete Computer Science 101 and 102, or to complete a correlate sequence in Computer Science.

**Advisors:** The department.

**Correlate Sequence in Computer Science:** Students majoring in other programs may complement their study by electing a correlate sequence in Computer Science. Selection of the appropriate option should be made in consultation with the Computer Science faculty to ensure exposure to the areas of Computer Science most useful to the field of concentration.

**Requirements for the correlate sequence:** Computer Science 101, 102 and 203; any two of 224, 240, 241 and 245 (at least one of which must be either 240 or 241), plus any 300–level Computer Science course. Suggested correlate sequences include the following, in addition to Computer Science 101, 102 and 203:

Architecture: 224, 241 and (324 or 325)

Software Systems: 241, 245, and (334 or 335)

Programming Languages: 240, 245 and 331

Artificial Intelligence: (240 or 241), 245 and 365

Graphics: 241, (224, 240 or 245) and 378

Theory: 240, 241 and (340 or 341)

**I. Introductory**

**101a or b. Computer Science 1: Problem–Solving and Procedural Abstraction (1)**

Introduces the design and use of algorithms to solve computational problems, using a simple but powerful and elegant programming language. Topics include list processing, recursion, and higher order procedures. The course emphasizes programming as a way to express ideas rather than simply a means to make computers perform tasks. A weekly laboratory period provides guided hands–on experience. The department.

Open to all classes.

**102a or b. Computer Science II: Objects and Data Abstraction (1)**

Introduces the concepts and techniques of object–oriented programming. Topics include fundamental data types (e.g., stacks, queues, lists, and trees), fundamental algorithms (e.g., searching and sorting), analysis of algorithm complexity, input and output to files and streams, and an introduction to concurrency, synchronization, and event–driven programming. The department.

Open to all classes.

Prerequisite: Computer Science 101.

**II. Intermediate**

**203a or b. Computer Science III: Data Structures and Software Systems (1)**

Examines concepts and techniques for the design, implementation, and use of data structures in complex software systeMs. Topics include principles of data encapsulation, modularity, and separation of specification from implementation, together with programming constructs that promote these principles, such as containers, iterators, polymorphism, and inheritance. Development of a software system of significant complexity is required.

Prerequisite: Computer Science 102.

**224a or b. Computer Organization (1)**

Examines the hierarchical structure of computing systems, from digital logic and microprogramming through machine and assembly languages. Topics include the structure and workings of the central processor, instruction execution, memory and register organization, addressing schemes, input and output channels, and control sequencing. The course includes a weekly hardware/software laboratory where digital logic is explored and assembly language programming projects are implemented.

Prerequisite: Computer Science 102.

**240a. Language Theory and Computation (1)**

Study of regular sets, context free grammars and languages, finite and push–down automata, various models of computation such as Turing machines. Includes substantial programming exercises, designed to connect implementation with fundamental theoretical concepts. Ms. Ide.

Prerequisites: Computer Science 203, and Mathematics 263.

**241b. Algorithmics (1)**

Study of advanced topics in algorithms and data structures, including searching, network design, and optimization. Includes substantial programming exercises, and experimental analysis of time and memory use. Connects implementation of algorithms with fundamental theoretical concepts such as automata and mathematical analysis of algorithMs. Builds foundation for advanced work in computer science.

Prerequisites: Computer Science 203, and Mathematics 263.

**245b. Declarative Programming Models (1)**

Declarative programming languages are important alternatives to the imperative languages used in most software systeMs. This course covers two kinds of declarative programming: functional programming and logic programming. Topics include the operational and denotational semantics of declarative languages, techniques for programming in declarative languages, and the use of mathematical logic as a tool for reasoning about imperative prograMs.

Prerequisites: Computer Science 102 and Mathematics 263.

**265b. Introduction to Artificial Intelligence (1)**

An introductory level course intended for non–majors with limited Computer Science background (e.g., Cognitive Science majors) interested in a better understanding of the computational aspects of Artificial Intelligence. The course follows a readings format, including programming as well as written assignments.

Prerequisites: Computer Science 102 and permission of the instructor.

290a or b. Field Work (^{1}/2 or 1)

**295a or b. Special Topics ( ^{1}/2 or 1)**

Intermediate–level treatment of specialized topics in computer science,

Prerequisite: permission of instructor.

**298a or b. Independent Work ( ^{1}/2 or 1)**

Prerequisite: permission of instructor.

**III. Advanced**

**[324b. Computer Architecture] (1)**

An exploration of current research areas in computer organization including an examination of data–flow, microcode, cache memory, distributed, parallel, and other nonstandard architectures, and related topics. Mr. Voerman.

Prerequisite: Computer Science 224.

Alternate years: not offered in 2001/02.

**325b. Microcomputers and Digital Electronics (1)**

Advanced seminar in the architecture and implementation of microprocessors. Topics include digital logic, memory and processor interfaces, interrupt handling, and serial I/O methods. Differences among logic implementations such as TTL, CMOS, and ECL are considered. Students participate in the design and imple–mentation of a microcomputer. Mr. Voerman.

Prerequisite: Computer Science 224.

Alternate years: offered in 2001/02.

**331b. Compilers (1)**

Studies the theory of automata for language recognition as well as the implementation of actual compilers for programming languages. During the semester students develop modules comprising the front–end of a compiler for a subset of the Pascal language. Ms. Ide.

Prerequisite: Computer Science 224, 240, 245, or permission of instructor.

**334a. Operating Systems (1)**

Deals with the theory and implementation of the software that governs the management of system resources. Topics that are covered include file organization, process scheduling, system services, memory management, security methods, resource contention, and design principles. Operating systems for parallel and distributed processing, real–time processing, virtual machines, and networking are also considered. Mr. Voerman.

Prerequisites: Computer Science 203, 224.

**335a. Software Development Methodology (1)**

Presents a systematic methodology for developing large software systems, focusing on the specification, modeling and design phases of the software development process. Topics include class hierarchies, aggregation, class relationships, and use–case analysis, among others. The course also touches on relevant notions of software architecture and middleware. Concepts are reinforced in group projects.

Prerequisites: Computer Science 203.

**340b. Theory of Computation (1)**

Builds on the basis established in Computer Science 240 by delving more deeply into principles of induction and inductive definitions; incompleteness and undecidability; recursive function theory; models of computation including Turing machines and partial recursive functions; recursive function theory; the halting problem and other unsolvable probleMs. May also cover topics in operational, axiomatic and denotational semantics; domain theory; information systems; etc.

Prerequisite: Computer Science 240 or permission of instructor.

Alternate years: offered in 2001/02.

**341b. Computational Complexity and Analysis of Algorithms (1)**

Models of computation; construction of algorithms, analysis of worst–case and average behavior; complexity measures and bounds; sorting and searching, algorithms on trees, graphs and networks, matrix operations; the classes of P, NP and NP–complete problems, intractable problems and approximation algorithMs. The department.

Prerequisite: Computer Science 241 or permission of instructor.

Alternate years: not offered in 2001/02.

**[365a. Artificial Intelligence] (1)**

A traditional and modem perspective on Artificial Intelligence as a discipline of Computer Science. The course emphasizes the problems and solutions of a computational approach to machine intelligence, and how these solutions impact Computer Science as a whole. Topics vary each year to reflect the state of the art of this rapidly evolving field. Previous topics include logic and logical reasoning, bayesian reasoning, fuzzy logic, ontology, robotics, game playing, and the frame problem. Significant programming projects highlight the course material.

Prerequisites: Computer Science 203, Computer Science 245.

**375a. Networks (1)**

Provides a detailed introduction to network protocols and software, as well as a discussion of network architectures and technology. Topics covered include properties of various transmission media, methods for reliable transfer of data, Ethernet and local–area networks, ISDN, TCP/IP and the Internet, routing, security, and E–mail. Programming assignments and a project emphasize the key concepts. Mr. Richards.

Prerequisites: Computer Science 203 or permission of instructor.

**[376a. Database Design] (1)**

Concerned with the theory and techniques of database design and the organization of query and command languages. The differences among relational, hierarchical, and networked databases are considered. Topics include data independence, data dictionaries, data models, entity–attribute relationships, access methods, and security issues.

Prerequisite: Computer Science 203.

Alternate years: offered in 2001/02.

**377a. Parallel Programming (1)**

An introduction to parallel computing, with coverage of parallel architectures, programming models, and techniques. Topics include SIMD and MIMD models, shared–memory and message–passing styles of computation, synchronization, deadlock, and parallel language design. Students are exposed to common techniques for solving problems in sorting, searching, numerical methods, and graph theory, and gain practical experience through programming assignments run on a parallel processing system.

Prerequisite: Computer Science 203.

**378b. Graphics (1)**

Introduction to computer graphics: 3D modeling and viewing, geometric transformations, visible surface detection methods, illumination and shading models, surface rendering methods (including ray–tracing and radiosity), and color models. A brief review of the mathematics for computer graphics: coordinate systems, vector products, linear algebra, and parametric representations. Instructor to be announced.

Prerequisites: Computer Science 203 and Mathematics 221.

Alternate years: offered in 2001/02.

**[395a or b. Special Topics] ( ^{1}/2 or 1)**

In–depth treatment of specialized topics in computer science, such as programming language semantics, parallel processing, etc.

Prerequisite: Computer Science 203.

**399a or b. Senior Independent Work ( ^{1}/2 or 1)**