Computer Science Department

Professor: Nancy Ide (Chair); Assistant Professors: Thomas Ellman, Luke Hunsbergerb, Bradley Richards, Jennifer Walter; Visiting Associate Professor: Louis Voerman.

b Absent on leave, second semester.

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 Computer Science 342.

Advanced Placement: Students eligible for Advanced Placement may be able to bypass 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.

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: 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. No course numbered 200 or higher may be elected NRO and counted toward the requirements for the correlate. Suggested correlate sequences include the following, in addition to Computer Science 101, 102 and 203:

I. Introductory

101a or b. Computer Science I: Problem-Solving and Abstraction (1)

Introduces the design and implementation of algorithms to solve computational problems, using an object-oriented programming language. Topics include procedural abstraction, expression evaluation, flow of control constructs and recursion; data abstraction, classes, inheritance and interfaces; elementary data structures (e.g., arrays, strings, vectors, lists, stacks, queues); input/output and event-driven programming. The course emphasizes principles of program design and data organization. A weekly laboratory period provides guided hands-on experience. The department.

Open to all classes.

102a or b. Computer Science II: Data Structures and Algorithms (1)

Development of data structures and algorithms in an object-oriented programming language. Topics include hierarchic program refinement, preconditions, postconditions and invariants; data encapsulation and fundamental data structures (e.g., priority-queues, sets, maps, heaps, search trees, hash tables and graphs); fundamental algorithms (e.g., searching and sorting) and analysis of algorithm complexity. A weekly laboratory period provides guided hands-on experience. The department.

Open to all classes.

Prerequisite: Computer Science 101.

II. Intermediate

203a or b. Computer Science III: Software Design and Implementation (1)

Develops techniques for design and implementation of complex software systems. Topics include object-oriented modeling, design patterns, component libraries, multiple inheritance, parametric polymorphism, generic algorithms, containers, iterators, function objects and storage management. Development of a software system of significant complexity is required. A weekly laboratory period provides guided hands-on experience.

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. Mr. Voerman.

Prerequisite: Computer Science 102.

240a. Language Theory and Computation (1)

Study of regular sets, context free grammars and languages, finite and push-down automata, as well as more powerful models of computation, such as Turing machines. Provides theoretical foundations for Computer Science 331, Compiler Design. Ms. Ide.

Prerequisites: Computer Science 203, and Mathematics 263.

241b. Algorithmics (1)

Introduces the systematic study of algorithms and their analysis with regard to time and space complexity. Topics include divide-and-conquer, dynamic programming, greediness, randomization, upper and lowerbound analysis, and introduction to NP completeness. Emphasis is placed on general design and analysis techniques that underlie algorithmic paradigms. Builds a foundation for advanced work in computer science. Ms. Walter.

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 programs.

Prerequisites: Computer Science 102 and Mathematics 263.

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: offered in 2004/05.

[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: not offered in 2004/05.

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 high-level computer. 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.

[342b. Topics in Theoretical Computer Science] (1)

Investigation of a selected topic in theoretical computer science. The topic is chosen each year according to the interests of students and faculty. Potential topics include algorithms, complexity, computability, programming language semantics, and formal methods, among others. The department.

Prerequisite: Computer Science 240, Computer Science 241, Computer Science 245.

365a. Artificial Intelligence (1)

An introduction to Artificial Intelligence as a discipline of Computer Science, covering the traditional foundations of the field and a selection of recent advances. Traditional topics include: search, two- player adversarial games, constraint satisfaction, knowledge representation and reasoning, and planning. Additional topics will vary from year to year and will be selected from the following: reasoning about time, probabilistic reasoning, neural networks, philosophical foundations, multi- agent systems, robotics, recent advances in planning. Significant programming assignments and a course project complement the material presented in class.

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, TCP/IP and the Internet, routing, and security. 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: not offered in 2004/05.

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.

378a. 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. Mr. Ellman.

Prerequisites: Computer Science 203 and Mathematics 221.

Alternate years: offered in 2004/05.

388b. Computer Animation: Art, Science and Criticism (1)

(Same as Art 388b, Media Studies Development Project 388b) An interdisciplinary course in Computer Animation aimed at students with previous experience in Computer Science, Studio Art or Media Studies, but not necessarily more than one of these areas. The course introduces students to mathematical and computational principles and techniques used to describe the shape and motion of three-dimensional figures in Computer Animation. It introduces students to artistic principles and techniques used in drawing, painting and sculpture, as they are translated into the context of Computer Animation. It also encourages students to critically examine Computer Animation as a medium of communication. Finally, the course exposes students to issues that arise when people from different scholarly cultures attempt to collaborate on a project of mutual interest. The course is structured as a series of animation projects interleaved with screenings and classroom discussions. Students carry out their projects working in pairs or small groups, using state-of-the-art modeling and animation software. In classroom discussions students critically evaluate their project work, and reflect on the process of interdisciplinary collaboration itself. Mr. Ellman, Mr. Roseman.

Prerequisites: Computer Science 378 and permission of the instructors.

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)