Information on this website is posted for historical reference only. Please visit the Office of the Registrar for current requirements.

Home >
ORC/Catalog >
Courses (04) >

*Chair: Prasad Jayanti*

*Associate Chair: Hany Farid*

*Professors T. H. Cormen, B. R. Donald, R. L. Drysdale III, D. F. Kotz, F. Makedon, D. Rockmore, D. Rus; Associate Professors H. Farid, P. Jayanti; Assistant Professors C. J. Bailey-Kellogg, A. Chakrabarti, S.W. Smith; Instructors D. Balkcom, R. R. Mettu; Senior Lecturer P. Wayner; Lecturers S. Bratus, K. Forbes- Riley, M. J. Fromberger, R. S. Gray, T. N. Henderson, S. P. Linder, L. Loeb; Visiting Professor W. M. McKeeman; Visiting Associate Professor C. S. McDonald; Adjunct Professors G. Cybenko, M. D. McIlroy, D. M. Nicol, J. D. Pearlman, A. Saykin, C. S. Stein, P. Winkler; Adjunct Associate Professor J. A. Aslam.*

Students wishing to devote one course to the study of computer science may choose Computer Science 4 or 5, depending on their background and interests. Students wishing to devote two or more courses to the study of computer science should begin with Computer Science 5 and either 15 or 18.

The major in computer science is intended for those students who plan careers in computer science or in fields that make use of computing, for those who plan graduate study in computer science, and also for those who simply find computer science interesting. Undergraduates majoring in computer science will have opportunities to participate with faculty in activities outside formal coursework. These activities include assisting in courses, writing a thesis or doing a project under the guidance of a faculty member, and assisting a faculty member in research or in a programming project.

To fulfill the major in computer science, a student must complete the courses prerequisite to the major and satisfy the requirements of the major. For additional requirements for the Honors Program see the section ‘The Honors Program in Computer Science’ below.

The basic first courses for students planning advanced work in computer science are Computer Science 5, Computer Science 15 or 18, Computer Science 19, and Mathematics 3. Computer Science 5 should be taken before Computer Science 15 or 18. Computer Science 19 should be taken after, or concurrently with, Computer Science 15 or 18. Next in the sequence of Computer Science courses will normally be Computer Science 23, 25, and 37; these can be taken in any order. (Note that Computer Science 19 should be taken before Computer Science 25.) Computer Science 37 may be taken any time after Computer Science 5, but most students will take Computer Science 15 or 18 first.

*Prerequisite courses*: A student must complete Computer Science 5, 15 or 18, 19, and Mathematics 3, or the equivalent honors or advanced placement course.

* Requirements: *A student who wishes to major in Computer Science must obtain approval of her or his program of study from the Departmental Undergraduate Adviser. To complete the major, it is necessary to pass at least nine courses in addition to the four prerequisite courses. Among these nine courses must be the following:

1. Computer Science 23;

2. Computer Science 25;

3. Computer Science 37;

4. Computer Science 39;

5. Computer Science 58 or 78;

6. Computer Science 48 or 68;

7. at least one course in mathematics related to computer science (Mathematics 16, 20, 22, 25, 26, 28, 29, 31, 38, 39, 40, 50, 56 or their honors equivalent);

8. one other Computer Science course numbered between 27 and 89. This may include 48, 58, 68, or 78, if not used to satisfy requirements 5 or 6;

9. Computer Science Culminating Experience Course (Computer Science 99) or Thesis (Computer Science 97).

The following minors are available to all students who are not majoring in Computer Science and who do not have a modified major with Computer Science. For each minor, the prerequisites and required courses are listed below. Approval of a minor can be obtained through the Undergraduate Advisor.

I. Computer Science

*Prerequisites:* Computer Science 5, 15 or 18, and 19.

*Courses:* Computer Science 23, 25, 37; any one of Computer Science 39, 48, 58, 68, 78, or 85; plus one other Computer Science course numbered 27 or above.

II. Operations Research

*Prerequisites:* Mathematics 3, 8, 13, and Computer Science 19.

*Courses: *Computer Science 25; Mathematics 16, 20, 22; and one of Mathematics 38 or 88 or Computer Science 85 with approval of the Undergraduate Advisor.

For completion of the Honors Program in Computer Science, and to be eligible to graduate with Honors or High Honors, a student must complete either an independent study project or a written thesis (for High Honors the thesis is required), and have his or her program of study approved as an Honors Program by the Undergraduate Advisor. In addition, the recommendation of the thesis/project advisor to award Honors or High Honors must be ratified by a departmental vote. College requirements for the Honors Program are discussed on pages XXX. The Honors project is undertaken by a student under the guidance of a faculty member. Usually the subject of the project or thesis will be motivated by the concepts or content of an advanced course taken as a part of the student’s major, and will normally be completed over a period of two or three terms. A variety of activities, such as participation in a department seminar, can lead to a project or thesis. Student suggestions for both projects and theses are welcome. The student should consult with his/her prospective project advisor and submit to the Undergraduate Advisor a brief written proposal of the project that has the written approval of the project advisor. The Undergraduate Advisor will review the student’s proposal and the courses that have been selected for the Honors major. Approval of the proposal and course selection will constitute formal admission into the Honors Program. This procedure is normally completed before the end of fall term, senior year. The student may then register for (at most two terms of) Computer Science 97, Honors Thesis Research.

Admission to the Honors Program requires a general College average of B, and a B average in the major at the time of admission and at the time of graduation. Moreover, a B+ average is required in the work of the Honors project/thesis. The B average in the major is determined as follows: Courses prerequisite to the major are not counted, but all other courses used as part of the major are counted, as are all courses titled Computer Science (beyond prerequisites, excluding 97), including courses cross-listed with Computer Science. Note that in the case of modified majors, courses used as part of the major may include courses from other departments. The B+ average required in the work of the Honors program is defined to be a grade of B+ given by the thesis/project advisor on the thesis or project. Questions about this requirement should be addressed to the Departmental Undergraduate Advisor.

Most graduate departments of computer science require applicants to take the Graduate Record Examination in Computer Science. This examination primarily covers material in Computer Science 5, 15, 18, 19, 23, 25, 37, 39, 58, and 68, plus material in Engineering Sciences 31. Those considering graduate school should take many of these courses. Less emphasis is placed on material in Computer Science 33, 43, 44, 48, and 78, and the various advanced topics covered in Computer Science 85 and 88 (although advanced topics are very good preparation for graduate study). Material from all courses listed as ‘mathematics related to computer science’ may appear on the examination, and it is hard to say that any of these courses is better preparation than the others. This examination is only one part of an application for graduate school. Letters of recommendation, particularly from professors who know you well through an advanced class or work on a project, usually are given more weight.

Many students have created modified majors with Computer Science being either the primary or the secondary part. Particularly common modified majors are with engineering, mathematics, or economics, but modified majors with philosophy, music, film studies, psychology, physics, geography, studio art, and many other subjects have been approved.

A modified major with Computer Science as the primary part must satisfy the first three requirements of the Computer Science major, two of requirements 4 through 6, and both of requirements 8 and 9. Students should discuss their plans with the Department’s Undergraduate Advisor to ensure a coherent major.

A modified major with Computer Science as the secondary part normally contains Computer Science 23, 25, and 37, and must contain at least two of these courses.

The Computer Science major modified with engineering requires satisfying most of the requirements of the computer science major, along with four engineering courses related to computer science. The prerequisites are Computer Science 5, 15 or 18, 19, Mathematics 3, 8, 13, and Physics 13, 14 (students in classes before 2002 need not complete Computer Science 19). The requirements are as follows:

1. Computer Science 23;

2. Computer Science 25;

3. Computer Science 37;

4. Satisfy two out of a, b, and c:

a) Computer Science 39;

b) One of Computer Science 58 or 78;

c) One of Computer Science 48 or 68;

5. one other Computer Science course numbered between 30 and 89. This may include 39, 48, 58, 68, or 78 if not used to satisfy requirement 4;

6. Engineering Sciences 22;

7. Engineering Sciences 31;

8. Engineering Sciences 62 or 63;

9. Engineering Sciences 26, 32, 61, 62, 63 or 91. (The same course cannot satisfy both 8 and 9).

10. Computer Science Culminating Experience Course (Computer Science 99) or Thesis (Computer Science 97).

The Department of Computer Science offers programs leading to the Ph.D. and M.S. degrees in Computer Science. Each is described below.

During the first two years, the students take a set of core graduate courses, topics courses, research seminars, and begin to become involved in research projects. In the third year and beyond, the main activities will be research and participation in seminars and topics courses.

The requirements for the Ph.D. degree in Computer Science are as follows:

1. Admission to the degree program by an admissions committee of the Computer Science faculty.

2. Completion of a course of study that includes:

(a) Computer Science 105, 107, 108, and 118.

(b) Two of Computer Science 104, 106, and 109. If 109 is not taken then Computer Science 39 must also be taken, unless the departmental advisor to Ph.D. students certifies that the student has taken an equivalent course elsewhere.

(c) Two advanced topics courses numbered between 181 and 188.

(d) Two additional courses, which may be chosen from advanced topics courses numbered between 181 and 188, the courses Computer Science 33, 38, 43, 54, and 78 taken for graduate credit (which involves additional work not required of undergraduates), whichever of Computer Science 104, 106, and 109 was not used to satisfy requirement (b) above, and Computer Science 110.

A student’s course of study is subject to the approval of the departmental advisor to Ph.D. students. Students normally take the six core courses specified in requirements (a) and (b) above by the end of their second year.

3. Students are expected to pass the Research Presentation Exam by the end of the winter term of their third year. An examining committee consisting of three faculty members, appointed by the departmental advisor to the Ph.D. Program, will select a paper for the student to present. The paper is selected in the area of Computer Science that the student chooses to be examined in. The student will have a month to read the paper, and will then present the paper to the committee and will orally answer questions on the paper. The committee will evaluate the student’s presentation and performance answering questions, and will determine if the student passes the examination. A student repeats this exam until he/she eventually passes the exam. In each attempt, the student is assigned a new paper, but not necessarily a new committee. Passing the Research Presentation Exam is a prerequisite to thesis proposal (see requirement 5 below). For more details on this exam, consult the Computer Science department web page.

4. At least one term of participation in undergraduate teaching. That is, the student must pass Computer Science 257.

5. Each student must display readiness for research in one area by giving a written and a public oral presentation of their research plan. This thesis proposal will be judged by a faculty committee chosen by the student; the rules used for the composition of this committee are the same as for a Ph.D. defense committee; this committee does not require the approval of the Dean of Graduate Studies, but must be approved by the departmental advisor to Ph.D. students. The presentation will be followed by a question period in which the student demonstrates mastery of the relevant area, and defends their proposed thesis plan.

6. Six terms in residence at Dartmouth. (This is a College requirement.)

7. Preparation of a thesis acceptable to a faculty committee and a public defense of this thesis. The committee shall be formed for the purpose of guiding the student’s research, according to the rules of the College. This committee must be approved by the Dean of Graduate Studies. All members of the committee shall read and sign the thesis in its final form.

The requirements for the M.S. degree in Computer Science are as follows:

(a) Satisfactory completion of six Computer Science courses taken for graduate credit. At least three of these courses must be numbered above 100.

(b) Satisfactory completion of three additional courses taken for graduate credit, at least one of which is an advanced topics graduate course in Computer Science (listed as Computer Science 181-188). Any courses taken outside of the Computer Science department must be approved by the departmental advisor to Master’s students. Students are expected to complete the M.S. degree in a maximum period of seven consecutive terms.

Six course equivalents of research from CS 297-299 is the minimum amount of research required towards the development and writing of a Master’s Thesis.

(a) A thesis proposal, consisting of a written document and a public presentation, shall be completed by the end of the second term of study. This thesis proposal will be judged by a faculty committee chosen by the student; the rules used for the composition of this committee are the same as for an M.S. defense committee, namely, two faculty from Computer Science and one member external to Computer Science.

(b) Preparation of a thesis acceptable to a faculty committee and a public defense of this thesis. The committee shall be formed for the purpose of guiding the student’s research, according to the rules of the College. This committee must be approved by the Dean of Graduate Studies. All members of the committee shall read and sign the thesis in its final form. The thesis, including a copy of the signature page, shall be published as a departmental Technical Report.

*Course Numbering System: *For Computer Science courses numbered above 20, the last digit in the course number indicates the field of computer science as follows: application systems, 3; artificial intelligence, 4; algorithms, 5; numerical analysis, 6; hardware systems, 7; software systems, 8; theory of computation, 9.

*Note:* Among the prerequisites for courses listed below, Computer Science 14 may substitute for Computer Science 5, but only if taken before or during 04S.

05W: 2 05X:12 06W: 2

This course provides an overview of computing and computer science, including such topics as the history of computers, computer applications, introductory concepts in digital electronics and computer architecture, computer languages, theory of computation, artificial intelligence, and the impact that computers have had on society and are likely to have in the future. Students will be introduced to computing through appropriate high-level software, such as World Wide Web, hypertext, and scripting languages. For example, in recent offerings students learned HTML and Javascript, and wrote significant HTML projects.

This course is intended for students who plan to take only one course in computer science, although students who take this course are welcome to take Computer Science 5 later. This course is not open to students who have taken Computer Science 5 or 14. *Dist: TAS.* Fromberger.

04F, 05S, 05F, 06S: 2

This course provides an introduction to fundamental concepts and techniques of computer science. The framework is an object-oriented programming language. Both programming and algorithm analysis are covered. Programming topics include basics of data and control; problem decomposition; recursion; simple graphics; objects and abstraction; and arrays. Good programming style is emphasized throughout the course. Algorithm topics include searching, sorting, and linked lists. This course requires a significant time commitment on the part of the student. Although no previous computing experience is assumed, first-year students in the fall term are encouraged to contact the instructor prior to enrolling in the course.

Students planning to pursue the engineering sciences major are advised to take Computer Science 14. Students considering the computer science major, or majors modified with computer science, should take Computer Science 5. *Dist: TAS.* Drysdale (fall), Cormen (spring).

*Consult special listings*

04F, 06W:12

This hands-on course focuses on state-of-the-art computer animation, presenting techniques for traditional animation and how they apply to 3D computer animation, motion capture, and dynamic simulations. Facial and full-body animation are covered through projects, readings, and presentations, including physical simulation, procedural methods, image-based rendering, and machine-learning techniques. Students will create short animations. This course focuses on methods, ideas, and practical applications, rather than on mathematics. *Dist: ART.* Loeb.

05S, 06S: 12

Prerequisite: Mathematics 3 and prior or concurrent enrollment in Mathematics 8. *Dist: TAS.* The staff.

*Not offered in the period from 04F through 06S*.

This course continues the study of computer science begun in Computer Science 5. It is organized around the ideas of data abstraction and abstract data types. Students will learn ways to represent lists, sets, dictionaries, priority queues, and other structures inside of the computer. They will also study design tradeoffs (space, time, operations allowed) and reasons for choosing one data structure over another. Specific representations include linked structures, binary trees, balanced trees, and hashing. More advanced sorting methods than were covered in Computer Science 5 will also be included. Students will implement programs that make use of the data structures and algorithms and will be assigned written work. It is recommended that students who have placed out of Computer Science 5 (through Advanced Placement or departmental examination) should take Computer Science 18 instead of Computer Science 15.

Prerequisite: Computer Science 5. *Dist: TAS.*

05S:2 06S: Arrange

This course introduces one of the fundamental tools of modern business planning and an exciting area of current mathematical and computer science research. The course begins with a discussion of the kinds of problems to which linear programming applies, followed by an introduction to the simplex algorithm and duality and shadow prices. After a discussion of some pitfalls of the simplex algorithm, the course turns to the revised simplex method, the solution of general linear, programming problems, and the general theory of duality and feasibility, a discussion of the applications of linear programming to the efficient allocation of scarce resources, and problems such as production scheduling and inventory. The course will close with topics selected from applications to matrix games, connections with geometry, connections to optimal matchings, network flows, and transportation problems or the nature and implications of interior point methods in linear programming.

Prerequisite: Mathematics 6 or 8 or equivalent knowledge of matrix algebra and permission of the instructor. *Dist: TAS*. The staff.

04F:10 05W:11 05F:10 06W:11

A challenging introduction to programming languages and computer science that emphasizes alternative modes of algorithmic expression. Topics include recursive and higher- order procedures, performance analysis of algorithms, proof of program correctness, probabilistic algorithms, symbolic hierarchical data, abstract data types, polymorphic functions, object oriented programming, infinite data types, simulation, and the interpretation of programs. It is recommended that students planning to major in Computer Science take Computer Science 18 rather than Computer Science 15.

Prerequisite: Computer Science 5, or placement in Computer Science 18 via Advanced Placement or departmental exam. *Dist: TAS.* Fromberger.

04F:11 05W: 10 05F:11 06W:10

This course integrates discrete mathematics with algorithms and data structures, using computer science applications to motivate the mathematics. It is designed to be taken simultaneously with Computer Science 15 or 18. However, students who are unable to complete it in this way may take it after Computer Science 15 or 18 but before Computer Science 25.

The course introduces counting techniques and number theory, with an emphasis on the application to RSA public key cryptography. It covers logic and proofs, including mathematical induction. Relationships among recursive algorithms, recurrence relations, and mathematical induction are discussed with particular attention to trees as a recursive data structure. Issues of expected running time for algorithms and the technique of “hashing” data files for quick recovery of information guides the discussion of probability through independent trials experiments and expected values. The course also covers basic graph theory.

Prerequisite: Concurrent enrollment in Computer Science 15 or 18 or completion of Computer Science 15 or 18. *Dist: QDS*. The staff (fall), Mettu (winter).

05W, 05S:12 06W, 06S: Arrange

Techniques for building large, reliable, maintainable, and understandable software systems. Topics include object-oriented design, user interface design, software project management, techniques for increasing reliability, and testing. Concepts are reinforced through a small number of medium-scale programs and one team programming project. This course requires a significant time commitment on the part of the student.

Prerequisite: Computer Science 15 or 18. *Dist: TAS. *Linder.

04F, 05S: 2 05F, 06S: Arrange

A survey of fundamental algorithms and algorithmic techniques, including divide-and- conquer algorithms, lower bounds, dynamic programming, greedy algorithms, amortized analysis, and graph algorithms. Presentation, implementation and formal analysis, including space/time complexity and proofs of correctness, are all emphasized.

Prerequisite: Computer Science 15 or 18 and Computer Science 19. *Dist: QDS.* Jayanti (fall), Drysdale (spring).

04F, 05F: 12

A study and analysis of important numerical and computational methods for solving engineering and scientific problems. The course will include methods for solving linear and nonlinear equations, doing polynomial interpolation, evaluating integrals, solving ordinary differential equations, and determining eigenvalues and eigenvectors of matrices. The student will be required to write programs and run them on the computer.

Prerequisite: Computer Science 5 and Mathematics 23. *Dist: QDS*. Shepherd.

05S:12 Laboratory 05X:9 Laboratory 06S:12 Laboratory

This course teaches classical switching theory including Boolean algebra, logic minimization, algorithmic state machine abstractions, and synchronous system design. This theory is then applied to digital electronic design. Techniques of logic implementation, from Small Scale Integration (SSI) through Application-Specific Integrated Circuits (ASICs), are encountered. There are weekly laboratory exercises for the first part of the course followed by a digital design project in which the student designs and builds a large system of his or her choice. In the process, Computer-Aided Design (CAD) and construction techniques for digital systems are learned. *Dist: TLA*. Hansen (spring), Pogue (summer).

06S: Arrange Offered in alternate years

This course studies the management of large bodies of data or information. This includes schemes for the representation, manipulation, and storage of complex information structures as well as algorithms for processing these structures efficiently and for retrieving the information they contain. This course will teach the student techniques for storage allocation and deallocation, retrieval (query formulation), and manipulation of large amounts of heterogeneous data. Students are expected to program and become involved in a project in which they study important aspects of a database system: ways to organize a distributed database shared by several computers; transactions that are processed locally and globally; robustness guarantees of the stored data against failure; security and data integrity guarantees from unauthorized access; privacy; object-oriented schemes for multimedia data; indexing, hashing, concurrency control, data mining, data warehousing, mobile databases and storage file structures.

Prerequisite: Computer Science 23 or equivalent, as approved by instructor. *Dist: TAS*.

05S: 12 05X, 06S: Arrange

The architecture and organization of a simple computer system is studied. Topics covered include how information is represented in memory, machine-language instructions and how they can be implemented at the digital logic level and microcode level, assembly language programming, and input/output operations. Speedup techniques, such as pipelining and caching, are also covered.

Prerequisite: Computer Science 5. Computer Science 15 or 18 is recommended. *Dist: TAS. *Forbes-Riley.

05S:10 06S: Arrange

The migration of important social processes to distributed, electronic systems raises critical security and privacy issues. Precisely defining security and privacy is difficult; designing and deploying systems that provide these properties is even harder. This course examines what security and privacy mean in these settings, the techniques that might help, and how to use these techniques effectively. Our intention is to equip computer professionals with the breadth of knowledge necessary to navigate this emerging area.

Prerequisite: completion of Computer Science 23 and completion of (or concurrent enrollment in) Computer Science 37; or instructor’s permission. *Dist: TAS*. Bratus.

04F: 12 05W: 2 05F: Arrange

This course serves as an introduction to formal models of languages and computation. Topics covered include finite automata, regular languages, context-free languages, push-down automata, Turing machines, computability, and NP-completeness. Offered every fall and alternate winters.

Prerequisite: Computer Science 25 (students who have not taken Computer Science 25, but have a strong mathematical background, may take Computer Science 39 with permission of the instructor). *Dist: QDS. *Chakrabarti.

04F:10A 05F: Arrange

This course is about how to mathematically model and computationally render (draw) two- and three-dimensional scenes and images. Two basic modes of rendering studied are (1) fast, interactive, real-time rendering, where realism is sacrificed for speed or (2) photo- realistic rendering, where the primary goal is a realistic image. Topics include two- and three-dimensional primitives, geometrical transformations (e.g., three-dimensional rotations, perspective and parallel projections), curves and surfaces, light, visual perception, visible surface determination, illumination and shading, and ray tracing. Assignments typically consist of a mixture of written work and “hands-on” projects. Knowledge of basic linear algebra is assumed.

Prerequisite: Computer Science 19 and 23. Computer Science 25 is recommended. *Dist: TAS. *Linder.

05W: 10 06W: Arrange

An introduction to the field of Artificial Intelligence. Topics include games, robotics, Lisp, Prolog, image understanding, knowledge representation, logic and theorem proving, understanding of natural languages, and discussions of human intelligence.

Prerequisite: Computer Science 23 and 25. *Dist: TAS.* Balkcom.

05S: 10A Offered in alternate years

Techniques for automatic translation of programming languages are discussed. The course includes a brief survey of various techniques and formalisms that can be used for describing the syntax and semantics of programming languages, for describing abstract and concrete machine architectures, and for describing program translation and transformation. This course includes a project to construct a compiler that will translate a program written in a high-level language into machine code for a conventional-architecture machine.

Prerequisite: Computer Science 23 and 37. Computer Science 25 and 39 are strongly recommended. *Dist: TAS. *McKeeman*.*

05S: 2

This project course is a hands-on introduction to robotics. The course will introduce students to the basic concepts in robotics, focusing on the mechanics, and electronic principles behind building robots and on the classic algorithms, architectures, and theories behind controlling and programming robots. Topics include: basic mechanics, basic electronics, control architectures (planning, subsumptionism, and behavior-based robotics), configuration sensing, motion planning, uncertainty in robotics, map making, grasping, manipulation, shape and object recognition, distributed robotics, and applications of robotics. Students will build a robot in teams using a robot building kit. They will use this robot to implement the algorithms discussed in class in the context of a concrete task (for example, a roborat system for the foraging task).

Prerequisites: facility with computers and programming (especially C), and some exposure to algorithms and formal methods. Computer Science 23 and 25 are recommended. *Dist. TLA*. Linder.

*Not offered in the period from 04F through 06S*

This course introduces the student to the concepts of modern numerical analysis. The main emphasis will be on developing effective numerical methods to solve problems in ordinary and partial differential equations. Other topics will be chosen from optimization, approximation, Fourier Transform, and Monte Carlo methods. The specific content will depend in part on the instructor.

Prerequisite: Computer Science 5 and Mathematics 33, or permission of the instructor. *Dist: QDS. *

04F:11 05F: Arrange

This course studies how computer operating systems allocate resources and create virtual machines for the execution of user jobs. Topics covered include storage management, scheduling, concurrent processing, shared access to files, synchronization, and data protec-tion. Both abstract models and actual examples of operating systems will be studied.

Prerequisite: Computer Science 23 and 37. Computer Science 25 is recommended. *Dist: TAS*. Smith.

05W: 12 06W: Arrange

This course provides a study of the principles of programming languages. The course will focus on the similarities and differences among imperative, functional, logical, and object oriented programming languages. Topics include formal definitions of languages and tools for automatic program translation, control structures, parameter passing, scoping, types, and functions as first-class objects. For each language category, implementation issues will be discussed, and program development strategies illustrated through programming exercises.

Prerequisite: Computer Science 23. Computer Science 25 and 37 are recommended. *Dist: TAS.* Bailey-Kellogg.

05S:11 06S: Arrange

This course focuses on the communications protocols used in computer networks: their functionality, specification, verification, implementation, and performance; and how protocols work together to provide more complex services. Aspects of network architectures are also considered. Laboratory projects are an integral part of the course in which networking concepts are explored in depth.

Prerequisite: Computer Science 23 and 37. Computer Science 25 is recommended. *Dist: TAS.* Henderson.

All terms: Arrange

Advanced undergraduates occasionally arrange with a faculty member a reading course in a subject not occurring in regular courses.

04W: Arrange

Each year a course in an advanced topic in theoretical computer science is offered. Topics covered in recent years include combinatorial optimization, computational geometry, cryptography, network flows, and distributed algorithms. Students may receive credit for Computer Science 85 more than once.

Prerequisite: Computer Science 25 or permission of instructor required. Recommended prerequisite will vary with term. Consult the Instructor for the topic. *Dist: QDS.* Drysdale.

04F, 05S: Arrange

Each year a course in an advanced topic in Computer Systems is offered. Topics covered in recent years include robotics, electronic commerce, and multimedia. Students may receive credit for Computer Science 88 more than once.

Prerequisite: Computer Science 23 or permission of instructor required. Computer Science 25 and/or Computer Science 37 may be required in certain terms. Recommended prerequisites will vary with term. Consult the Instructor for the topic. *Dist: TAS.* Donald, Farid (fall), Bailey-Kellogg, Balkcom, Makedon (spring).

All terms: Arrange

Open only to students who are officially registered in the Honors Program. Permission of the Undergraduate Advisor and thesis advisor required. This course does not serve for distributive credit, and may be taken at most twice.

05W: 10A 06W: Arrange

This course will survey current technological trends and ethical issues in computer science. By the nature of the course, the specific topics will change from year to year, but the emphasis will be on the basic components of computer science. These include history, human-computer interaction, industry, hot or speculative technologies, connectivity and access, parallel computing, scientific computing, cryptography and privacy, current computing as reflected in the popular press, and fault-tolerant computing. The ethical issues covered will include the societal impact of information technology, invasion of privacy, computer crime, ethical codes for professional organizations, legislation for the information age, ethics at school and in the workplace, intellectual property rights, and software patents.

Prerequisites: Computer Science 23, 25, and 37 or permission of the instructor. This course is intended to be for seniors; any non-seniors must receive permission from the instructor and the undergraduate advisor. Makedon.

Graduate students wishing to take a graduate course who have not passed the listed Dartmouth prerequisite courses with a grade at least as good as the median grade in the course must get written permission from the instructor in order to enroll in the graduate course. Any undergraduate enrolling in a graduate course must have the written permission of the instructor.

Some advanced undergraduate courses may be taken for graduate credit when supplemented by work not required of undergraduates. The Graduate Directory contains information about these courses.

04F: Arrange

This course is a graduate-level survey of artificial intelligence. It covers the basic principles underlying artificial intelligence (search methods, knowledge representation and ‘expert systems’, planning, learning, etc.) and examples of particular artificial intelligence applications areas (natural language understanding, vision, robotics).

Prerequisite: Computer Science 44. Donald.

05W: Arrange

The main topics of the course are paradigms for designing algorithms (e.g.,* *divide and conquer, greedy method, structured search, balancing, dynamic programming, scaling, problem reductions), and the criteria for their analysis (e.g.,* *worst-case, average case, lower bounds, sensitivity, amortization, resource tradeoffs, NP-completeness). The course deals primarily with the classical sequential algorithms, but also introduces parallel, distributed, random, probabilistic, and approximation algorithms as time permits.

The techniques are illustrated with algorithms for several domains, drawn from among information retrieval, graphs, networks, matroids, string matching, cryptology, arithmetic, matrices, and algebra. Many examples of important data structures and algorithms are described.

Prerequisite: Computer Science 25 and 39. Students are expected to be familiar with basic concepts from graph theory, discrete mathematics, linear algebra, and probability. Chakrabarti.

05W: Arrange Not offered every year.

The* *course examines in the context of modern computational practice algorithms for solving linear systems Ax = b and Az = lx. Matrix decomposition algorithms, matrix inver-sion, and eigenvector expansions are studied. Algorithms for special matrix classes are fea-tured, including symmetric positive definite matrices, banded matrices, and sparse matrices. Error analysis and complexity analysis of the algorithms are covered. The algorithms are implemented for selected examples chosen from elimination methods (linear systems), least squares (filters), linear programming, incidence matrices (networks and graphs), diagonalization (convolution), sparse matrices (partial differential equations).

Prerequisite: Computer Science 26, Mathematics 26, or Engineering Sciences 91. Students are to be familiar with approximation theory, error analysis, direct and iterative techniques for solving linear systems, and discretization of continuous problems to the level normally encountered in an undergraduate course in numerical analysis. Rockmore.

05F: 10

This course provides an introduction to the field of computer architecture. The history of the area will be examined from the first stored program computer to current research issues. Topics covered will include successful and unsuccessful machine designs, cache memory, virtual memory, pipelining, instruction set design, RISC/CISC issues, and hardware/software tradeoffs. Readings will be from the text and an extensive list of papers. Assignments will include homeworks and a substantial project, intended to acquaint students with open questions in computer architecture.

Prerequisite: Computer Science 37; Computer Science 58 is recommended. Cybenko, Berk.

05W: Arrange

This course covers advanced topics in operating systems, including issues such as the hardware/software interface, operating-system structure, CPU scheduling, concurrency, virtual memory, interprocess communication, file systems, protection, security, fault tolerance, and transaction processing. The course also considers many of these topics in the context of distributed systems.

Prerequisite: Computer Science 58. McDonald.

05S: 10

Building on the material covered in a standard undergraduate course, this course studies aspects of both computability and complexity. The study of computability includes Reductions, Rice’s theorems, Post Correspondence Problem, Valid Computations, Kleene Hierarchy, and the Recursion Theorem. The study of complexity covers some results on space complexity (Savitch’s Theorem, Immerman’s Theorem, Pspace), Cook-Levin Theorem and the Hardness of Approximation. Additional topics are covered if there is time.

Prerequisite: Computer Science 49. Jayanti.

*Not offered in the period from 04F to 05X*

Students will learn how to write technical papers in computer science, how to present technical papers in a conference-talk setting, and how program committees and journal editors evaluate technical papers. Writing topics include the proper use of technical typesetting software, organization of technical papers, and English usage. Students will write technical papers, produce official course notes, and give oral presentations.

Prerequisite: Each student must submit a short expository piece to be evaluated by the instructor at the start of the course; only those students meeting a required level of competence will be permitted to take the course for a grade. Students should also have a Computer Science background sufficient to understand research papers.

Enrollment limited.

05S: Arrange

This course covers fundamental and advanced topics in the design, implementation and use of imperative, functional, logical and object-oriented programming languages. Topics covered include formal definitions of languages, tools for automatic program translation, parameter passing, scoping, type systems, control structures and automatic memory management. For each language category, implementation issues will be discussed, and program development strategies illustrated through programming exercises.

Prerequisite: Computer Science 68. Undergraduate courses in compilers (Computer Science 48) are recommended. McKeeman.

05W: Arrange Drysdale.

04F: Arrange Farid.

04F: Arrange Donald.

05S: Arrange Bailey-Kellogg.

05S:Arrange Balkcom.

05S:Arrange Makedon.

Prerequisite: Computer Science 23, 25, and 37, or permission of the instructor. Computer Science 58 may be recommended.

May be taken multiple times for credit. One course equivalent.

Student participates in research under the supervision of a faculty member. May be taken multiple times for credit. One course equivalent.

Student participates in research under the supervision of a faculty member. May be taken multiple times for credit. Two course equivalents.

Student participates in research under the supervision of a faculty member. May be taken multiple times for credit. Three course equivalents.