Computer Science

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

Requirements for Concentration: Computer Science 101/102, Mathematics 121/122 or Mathematics 125, Computer Science 224, 235, 240, 241, Mathematics 263; one of Mathematics 221 or 261; Computer Science 331, 334, plus two other 300-level computer science electives.

Recommendations: Prospective majors are strongly advised to complete Computer Science 101/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 340 and 341. Students who take Mathematics 125 should consider election of another course rather than one less unit.

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

Non-majors: Students majoring in the sciences are advised to complete the 101/102 sequence, or to complete a correlate sequence in computer science.

Advisers: 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 department and the major adviser to ensure exposure to the areas of computer science most useful to the field of concentration.

Requirements for the correlate sequence: 101/102; plus one of the following course groups: I. Computer Science 224, 241, plus any two 300-level courses; II. Computer Science 224, 235, 240, 331, (student should be aware that 340 is recommended but not required for this sequence); III. Computer Science 235, 240, 265, and 365 or 366 (taking both 365 and 366 is recommended but not required); IV.Computer Science 224, 240, 241 plus one of: 331, 334, 340, 341.

I. Introductory

101a or b. Computer Science I (1)

Introduces a number of important concepts in computer science through the use of a simple yet powerful and elegant modern programming language. These concepts include the use of procedural and data abstraction to cope with complexity, functional programming, symbolic programming, recursion, higher order procedures, and sequential programming. The course emphasizes programming as a way to express ideas, rather than just a way to get computers to perform tasks. A weekly laboratory period provides guided "hands-on" experience. Successful completion of this course or its equivalent is a prerequisite for all other courses in computer science. The department.

Open to all classes.

102a or b. Computer Science II (1)

Builds on the foundation laid in Computer Science I by introducing the student to abstract data structures, such as stacks, queues, linked lists, and trees. The course also deals with techniques for data manipulation, particularly sorting and searching, as well as methods for determining the efficiency of common sorting and searching algorithms. The department.

Open to all classes.

Prerequisite: Computer Science 101 or permission of the instructor.

II. Intermediate

224a or b. Computer Organization (1)

Examines the hierarchical structure of computing systems. The course covers the various levels of computer organization, from digital logic and microprogramming through machine and assembly languages. Among the topics considered are the structure and the workings of the central processor, instruction execution, memory and register organization, addressing schemes, input and output channels, and control sequencing.

Prerequisite: Computer Science 102.

235a. Software Development Methodology (1)

Covers the principles of software development from the prospective of modeling applications for design. This course currently focuses on object-oriented technology as a mechanism for expressing a model and will require paper-level object-oriented design projects as well as programming projects using an object-oriented language. This course is a natural successor to Computer Science 102.

Prerequisites: Computer Science 102 or permission of instructor.

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 102, Mathematics 122 or 125, 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 102, Mathematics 122 or 125, and Mathematics 263.

265a. Artificial Intelligence (1)

Examines the basic methods of artificial intelligence research and explores several of the primary areas of investigation. The research areas considered include knowledge representation, learning, problem solving, heuristic search, natural language processing, and expert systems. Mr. Welty.

Prerequisite: Computer Science 102 or permission of 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.

[297a or b. Advanced Programming Languages] (1/2)

The purpose of this reading course is to enable students already familiar with computer programming to acquire knowledge of other programming languages. The department routinely offers this course for Pascal, C, and LISP; other languages may be offered as interest dictates. Computer science faculty.

Prerequisite: permission of instructor.

Not offered in 2000/01.

298a or b. Independent Work (1/2 or 1)

Prerequisite: permission of instructor.

III. Advanced

324a. 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 2000/01.

[325a. 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 2000/01.

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 and Computer Science 240 or permission of instructor.

334b. 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.

Prerequisite: Computer Science 224.

[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: not offered in 2000/01.

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: offered in 2000/01.

365b. Topics in Artificial Intelligence (1)

Provides advanced study in a specific area within the field of artificial intelligence, such as problem solving, natural language processing, expert systems, or intelligent

interface design. The course is taught as a practicum and each student is required to design and implement a module for a prototype system. Mr. Welty.

Prerequisite: Computer Science 265 or Computer Science 266.

Alternate years: offered in 2000/01.

[366b. Natural Language Processing] (1)

Delves more deeply into an area central to the field of artificial intelligence: the use of the computer to understand ordinary human languages such as English. The course focuses on the construction of various modules of a parser for English and the different techniques used for representing and processing syntactic and semantic information. Ms. Ide.

Prerequisites: Computer Science 240 and either 235 or 265 or permission of instructor.

Alternate years: not offered in 2000/01.

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

Alternate years: offered in 2000/01.

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.

Prerequisites: Computer Science 235 and permission of instructor. Mathematics 221 highly recommended.

Alternate years: offered in 2000/01.

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 235 and permission of instructor.

399a or b. Senior Independent Work (1/2 or 1)