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

Home >
ORC/Catalog >
Descriptions >

*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: graphics and digital arts, 2; applications, 3; artificial intelligence, 4; algorithms, 5; numerical analysis, 6; computer hardware, 7; software systems, 8; theory of computation, 9.

09W: 2 10W: Arrange

This course presents topics related to interactive visual art generated on a computer. Although it briefly covers computer-generated media art, the course focuses on the programming skills required for creating interactive works. Rather than using commercial software, students write their own programs, using the Processing language, to create compositions with which users can interact. The course introduces fundamental concepts of how to represent and manipulate color, two-dimensional shapes, images, motion, and video. Coursework includes short programming assignments to practice the concepts introduced during lectures and projects to explore visual compositions. The course assumes no prior knowledge of programming.

This course is not open to students who have passed Computer Science 5 or Engineering Sciences 20 or who have received credit for one of these courses via the Advanced Placement exam or the local placement exam. *Dist: TLA.* Bailey-Kellogg.

09S: 2 10S: Arrange

This course enables a student from another discipline to approach that discipline from a computational perspective—formulating computational problems, identifying suitable representations and approaches for solving them, and developing and implementing efficient solutions. The course assumes no computational background, and it introduces the fundamental computational skills that are useful in many disciplines. A series of laboratory exercises employ discrete, numerical, and statistical approaches to solve problems from a variety of disciplines. Solutions are developed in a high-level, interactive programming language that helps students learn and use the fundamental representations and techniques.

Prerequisite: Mathematics 8. Open to students who have taken Computer Science 5. *Dist: TLA.* Choudhury.

09X: Arrange

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 passed Computer Science 5 or Engineering Sciences 20 or who have received credit for one of these courses via the Advanced Placement exam or the local placement exam. *Dist: TAS.* Farid.

08F, 09S: 2 09F, 10S: Arrange

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.

In past years Engineering Sciences 20 could substitute for Computer Science 5 as a prerequisite for Computer Science courses, but since its content has changed this is no longer the case. Students considering the computer science major, or majors modified with computer science, or courses that require Computer Science 5 as a prerequisite should take Computer Science 5 instead of Engineering Sciences 20. *Dist: TLA.* Balkcom (fall), Drysdale (spring).

*Consult special listings*

08F: 10 09W: 11 09F, 10W: Arrange

Motivated by applications in the arts, sciences, social sciences, and computer systems, this course develops skills in solving problems computationally. Topics covered include representation (how to capture computationally the objects and processes of a problem), abstraction (how to build high-level, multi-purpose toolkits for manipulating representations), recursion and modularity (how to break problems into subproblems and combine solutions), reasoning (how to understand what a computation is doing), and concurrency (how to deal with multiple simultaneous processes). These concepts are taught within a functional programming language that supports them well; they are applied in a series of programming labs solving application problems.

Prerequisite: Computer Science 5 or Advanced Placement. *Dist: TLA.* Drysdale.

*Not offered in the period from 08F through 09S*

For hundreds of years, scientists and artists have studied motion in order to create better machines, detect injuries, improve athletic performance, express concepts and feelings, create more efficient factories, and understand hidden motivations. This interdisciplinary course will look at what is known and how it is used. We will also do our own motion analysis, complete projects using motion data, explore some of the languages that have been developed to describe human motion, and consider the relationship between the artistic representation of motion and scientific reality. Students will keep a motion journal, write two papers, and complete a research project that will be presented to the class in lieu of a final exam. There are no prerequisites for the course. Students from all departments are encouraged to attend. *Dist: TAS.* Loeb.

09W: 10 10W: Arrange

This course integrates discrete mathematics with algorithms and data structures, using computer science applications to motivate the mathematics. It covers logic and proof techniques, induction, set theory, counting, asymptotics, discrete probability, graphs, and trees.

Mathematics 19 is identical to Computer Science 19 and may substitute for it in any requirement.

Prerequisite: Computer Science 5, Engineering Sciences 20, or Advanced Placement. *Dist: QDS*. Zomorodian.

08F: 10A 09F: Arrange

This projects-based lab course teaches the principles and practices of 3D modeling. Lectures focus on principles of modeling, materials, shading, and lighting. Students create a fully rigged character model while learning their way around a state-of-the-art 3D animation program. Assignments are given weekly. Students are graded on the successful completion of the projects, along with a midterm examination. Work will be evaluated on a set of technical and aesthetic criteria. *Dist: TLA.* Loeb.

09W: 12 09S: 10 10W, 10S: Arrange

Techniques for building large, reliable, maintainable, and understandable software systems. Topics include UNIX tools and filters, programming in C, software testing, debugging, and teamwork in software development. Concepts are reinforced through a small number of medium-scale programs and one team programming project.

Prerequisite: Computer Science 8. *Dist: TLA.* McDonald (winter), Campbell (spring).

08F: 10 09F: 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 8 and Computer Science 19. *Dist: QDS.* Jayanti.

08F, 09F: 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.

09W: 11 10W: Arrange

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.

09S: 10 Not offered every year

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*. Chakrabarti.

09S: 10A

This course provides an introduction to statistical modeling and machine learning. Topics include learning theory, supervised and unsupervised machine learning, statistical inference and prediction, and data mining. Applications of these techniques to a wide variety of data sets will be described.

Prerequisites: Computer Science 5, Computer Science 6, or Engineering Sciences 20; Mathematics 22 or 24. *Dist: QDS.* Torresani.

09X: Arrange.

This course provides a practical and principled coverage of useful numerical and computational tools of use in many disciplines. The first half of this course provides the mathematical (linear algebra) and computing (Matlab) framework upon which data analysis tools are presented. These tools include data fitting, Fourier analysis, dimensionality reduction, estimation, clustering, and pattern recognition. This course is designed for undergraduate and graduate students across the sciences and social sciences.

Prerequisite: Computer Science 5 or equivalent, Mathematics 8 or equivalent, Mathematics 22 or Mathematics 24 or equivalent, as approved by the instructor. *Dist: TAS.* Farid.

09S: 11 09X: 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 or Engineering Sciences 20. *Dist: TAS.* Smith (spring).

09W, 09F: 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. Computer Science 19 is recommended. *Dist: TAS*. Palmer.

09W: 11 10W: Arrange

This course serves as an introduction to formal models of languages and computation. Topics covered include finite automata, regular languages, context-free languages, pushdown automata, Turing machines, computability, and NP-completeness.

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.

09S: 10A 10S: Arrange

This is the culminating course for the Digital Arts Minor. Students from arts and sciences come together to complete projects in digital arts, including: 3D computer animations; innovative digital installations; creative mobile media; interactive pieces; 2D digital projects. Students work in small teams to complete work of a high production quality or work that incorporates innovations in technology. This course has a required laboratory period.

Prerequisite: Computer Science 32 and one of the following courses: Film Studies 31, 35, 38; Studio Art 16, 29; Theater 30; Computer Science 12, 42, 82; or Psychology 21. *Dist: ART.* Pellacini.

09S: 2A 10S: Arrange

Bioinformatics is broadly defined as the study of molecular biological information, and this course introduces computational techniques for the analysis of biomolecular sequence, structure, and function. While the course is application-driven, it focuses on the underlying algorithms and information processing techniques, employing approaches from search, optimization, pattern recognition, and so forth. The course is hand-on: programming lab assignments provide the opportunity to implement and study key algorithms.

Prerequisite: Computer Science 8. Computer Science 19 is recommended. *Dist. TLA.* Bailey-Kellogg.

09W: 10 10W: 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 8. Computer Science 19 is recommended. *Dist: TAS.* Zomorodian.

09S: 11 10S: Arrange

Planning, scheduling, and design problems in large organizations, economic or engineering systems can often be modeled mathematically using variables satisfying linear equations and inequalities. This course explores these models: the types of problems that can be handled, their formulation, solution, and interpretation. It introduces the theory underlying linear programming, a natural extension of linear algebra that captures these types of models, and also studies the process of modeling concrete problems, the algorithms to solve these models, and the solution and analysis of these problems using a modeling language. It also discusses the relation of linear programming to the more complex frameworks of nonlinear programming and integer programming. These paradigms broaden linear programming to respectively allow for nonlinear equations and inequalities, or for variables to be constrained to be integers.

Prerequisites: Computer Science 3, 8, or 19; Mathematics 8; Mathematics 22 or 24; or permission of the instructor. *Dist: TAS.* Fleischer.

09S: 12 09X: 9 10S: 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*. Cooley (spring), Hansen (summer).

09S: 2A 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 19 is recommended. *Dist: TAS.* McKeeman.

10W: 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 8. *Dist: TAS.* Pellacini.

08F, 09F: 2A (Granger)

09W: 10

This project course is a hand-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 robo-rat system for the foraging task).

Prerequisite: Computer Science 8. *Dist. TLA*. Balkcom.

08F: 11 09F: 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 protection. Both abstract models and actual examples of operating systems will be studied.

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

*Not offered in the period from 08F through 10S*

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 8. Computer Science 19 and 37 are recommended. *Dist: TAS.*

All terms: Arrange

This independent study course is for students who have completed all the courses in the digital arts minor and want to continue working on projects in digital arts. Projects may include computer animations, interactive digital arts, installations, or research projects. Students work alone or in teams. This course may be taken at most twice.

Prerequisite: Computer Science 42 and permission of the instructor is required. Loeb, Pellacini, Torresani.

09S: 2 10S: 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 19 is recommended. *Dist: TAS.* Campbell.

All terms: Arrange

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

10W: Arrange Not offered every year

08F: 2A 09W: 10 09S: 2A

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.* Fleischer (fall), Jayanti (winter), Zomorodian (spring)*.*

09F, 09W, 09S: 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.* Choudhury (fall), Campbell (winter), Balkcom (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.

08F, 09W, 09S: 10A 09F, 10W, 10S: Arrange

Participation in a software engineering group project in the context of on-going partnerships with community service agencies. Group members are responsible for all aspects of a software system, including iterative requirements analysis, design, implementation, testing, and maintenance. The course also stresses customer interactions, documentation, process, and teamwork. The result is a software product of significant scope and significant benefit to the community.

Prerequisite: Computer Science 23, 25 and 37, or permission of instructor. Bailey-Kellogg.

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 web contains information about these courses.

*Not offered during 2008-09*

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.

09W, 10W: Arrange

This course provides an introduction to algorithms and algorithm design techniques at a level more advanced than a typical undergraduate course in algorithms, yet basic enough to be applicable widely across the many subfields of computer science. There is a strong emphasis on rigorously proving the correctness of and running time bounds on the algorithms studied. Typical techniques covered include, but are not limited to, randomization, amortized analysis, linear programming and approximation. Typical problems include, but are not limited to, splay trees, perfect hashing, skip lists, fast randomized algorithms for minimum cuts and minimum spanning trees, maximum matching, pattern matching, and some simple approximation algorithms: both combinatorial and based on linear programming relaxation.

Prerequisites: Computer Science 25 and 39. Additionally, students are expected to be familiar with basic concepts from graph theory, discrete mathematics, linear algebra, and probability. Fleischer.

*Not offered during 2008-09*

The course examines in the context of modern computational practice algorithms for solving linear systems Ax = b and Az = λx. Matrix decomposition algorithms, matrix inversion, and eigenvector expansions are studied. Algorithms for special matrix classes are featured, 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.

08F, 09F: 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. Berk.

09W, 10W: 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. Smith.

09S, 10S: Arrange

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 39. Chakrabarti.

*Not offered during 2008-09*

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.

*Not offered during 2008-09*

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.

09S: 10A (Torresani).

09X: Arrange (Farid).

09S: 2A (Bailey-Kellogg).

08F: 2A (Granger).

*Not offered during 2008-09*

08F: 2A (Fleischer).

09W: 10 (Jayanti)

09S: 2A (Zomorodian).

08F: Arrange (Choudhury).

09W: Arrange (Campbell, Choudhury)

09S: Arrange (Balkcom).

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.