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, P. Winkler; Associate Professors A.T. Campbell, H. Farid, P. Jayanti; Assistant Professors C. J. Bailey-Kellogg, D. Balkcom, A. Chakrabarti, F. Pellacini, S.W. Smith; Instructors E. Davidson, K. Forbes-Riley, M. Fromberger; Senior Lecturer P. Wayner; Lecturers A. Paul, R. Ray; Research Associate Professor P. Thompson; Research Assistant Professors J. C. Ford, T. N. Henderson, L. Loeb; Visiting Professors M. D. McIlroy, W. M. McKeeman; Visiting Associate Professor C. S. McDonald; Adjunct Professors G. Cybenko, D. M. Nicol, J. D. Pearlman, D. Rus, A. Saykin, C. S. Stein; Adjunct Associate Professor J. A. Aslam, E. Demidenko; Adjunct Assistant Professor S. P. Linder.
INTRODUCTORY COURSES
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 18.
MAJOR IN COMPUTER SCIENCE
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 18, Computer Science 19, and Mathematics 3. Computer Science 5 should be taken before Computer Science 18. Computer Science 19 should be taken after, or concurrently with, Computer Science 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
37 may be taken any time after Computer Science 5, but most students will take Computer Science 18 first.
REQUIREMENTS FOR THE COMPUTER SCIENCE MAJOR
Prerequisite courses: A student must complete Computer Science 5, 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 Advisor. To complete the major, it is necessary to pass at least nine courses in addition to taking 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 98, pending faculty approval, or 99) or Thesis (Computer Science 97).
MINORS IN COMPUTER SCIENCE
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, 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.
THE HONORS PROGRAM IN COMPUTER SCIENCE
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 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 in the Regulations section. 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.
PREGRADUATE STUDY IN COMPUTER SCIENCE
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, 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 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.
MODIFIED MAJORS
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
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, 18, 19; Mathematics 3, 8, 13; and Physics 13, 14. 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 98, pending faculty approval, or 99) or Thesis (Computer Science 97).
GRADUATE STUDY IN COMPUTER SCIENCE
The Department of Computer Science offers programs leading to the Ph.D. and M.S. degrees in Computer Science. Each is described below.
REQUIREMENTS FOR THE DOCTOR’S DEGREE (PH.D.)
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 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.
REQUIREMENTS FOR THE MASTER OF SCIENCE DEGREE (M.S.)
The requirements for the M.S. degree in Computer Science are as follows:
1. Course requirements:
(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.
2. Research requirements:
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.
3. Thesis requirements:
(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 as noted in the Graduate Student Handbook, “three faculty members from the student’s department/program (including the dissertation advisor). One of the three may be from outside the department/program, but this is not a requirement.�?
(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.
UNDERGRADUATE COURSES
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.
3. 3D Computer Animation and the Math that Drives It (Identical to, and described under, College Course 1; also Mathematics 5)
05F:10A
Dist: TAS. Satisfies the Interdisciplinary requirement (Class of 2004 and earlier). Rockmore, Loeb.
4. Concepts in Computing
06W: 206X:1207W: 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 or received credit for Computer Science 5, Engineering Sciences 20, or any Computer Science course numbered 18 or above. Dist: TAS. Farid (winter), the staff (summer).
5. Introduction to Computer Science
05F, 06S, 06F, 07S: 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.
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: TAS. Balkcom (fall), Cormen (spring).
7. First-Year Seminar in Computer Science
Consult special listings
12. Motion Study: Using Motion Analysis for Science, Art and Medicine
06S: 1107W: 2A
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.
13. Computer Animation: The State of the Art
06W: 1207S:2
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.
16. Linear Programming (Identical to Mathematics 16)
06S:1107S: 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, 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. Elizalde.
18. Structure and Interpretation of Computer Programs
05F:1006W:1106F:1007W: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.
Prerequisite: Computer Science 5, or placement in Computer Science 18 via Advanced Placement or departmental exam. Dist: TAS. Fromberger.
19. Discrete Mathematics in Computer Science (Formerly Computer Science 21. Identical to Mathematics 19 and Engineering Sciences 66)
05F:1106W: 1006F:1107W: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 18. However, students who are unable to complete it in this way may take it after Computer Science 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 18 or completion of Computer Science 18. Dist: QDS. Pomerance (fall), Chakrabarti (winter).
23. Software Design and Implementation
06W, 06S:1207W, 07S: 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 18. Dist: TAS. McDonald (winter), Fromberger (spring).
25. Algorithms
05F, 06S: 1006F, 07S: 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 18 and Computer Science 19. Dist: QDS. Jayanti.
26. Methods in Computation (Identical to Mathematics 26 and to Engineering Sciences 91)
05F, 06F: 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.
27. Digital Electronics (Identical to Engineering Sciences 31)
06S: 12 Laboratory06X: 9 Laboratory07S: 12 Laboratory07X: 9 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. Pogue (spring), Hansen (summer).
33. Information Systems
06S: 12Offered 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. Paul.
37. Computer Architecture
06S: 1106X, 07S: 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 18 is recommended. Dist: TAS. Forbes-Riley.
38. Security and Privacy
06S:207S: 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. Smith.
39. Theory of Computation (Formerly Computer Science 49)
05F: 1206F: 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.
43. Computer Graphics
05F: 2A06F: 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. Pellacini.
44. Artificial Intelligence (Identical to Cognitive Science 44)
06W: 1007W: 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.
48. Implementation of Programming Languages
07S: ArrangeOffered 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. The staff.
54. Principles of Robot Design and Programming
06S: 2AOffered in alternate years
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).
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. Balkcom.
56. Numerical Analysis (Identical to Mathematics 56)
Not offered in the period from 05F 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.
58. Operating Systems
05F:1106F: 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. Computer Science 25 is recommended. Dist: TAS. Smith.
68. Principles of Programming Languages
06W: 207W: 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.
78. Computer Networks
06S:1107S: 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. Campbell.
82. Reading Course
All terms: Arrange
Advanced undergraduates occasionally arrange with a faculty member a reading course in a subject not occurring in regular courses.
85. Topics in Theoretical Computer Science
06W: 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. Chakrabarti.
88. Topics in Computer Systems
05F, 06W, 06S: 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. Bailey-Kellogg (fall), Donald (winter), Pellacini (spring).
97. Thesis Research
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.
98. EPICS: Engineering Projects in Community Service
05F, 06W, 06S: 10A06F, 07W, 07S: 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.
99. Current Trends and Ethical Issues in Computer Science
06W: 10A07W: 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. Bailey-Kellogg.
GRADUATE COURSES
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.
104. Artificial Intelligence
05F: 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.
105. Algorithms and Data Structures
06W: 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. Ray.
106. Numerical Linear Algebra (Identical to Engineering Science 106 and Mathematics 116)
Not offered every year.
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.
107. Computer Architecture (Identical to Engineering 116)
05F, 06F: 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.
108. Advanced Operating Systems
06W: 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.
109. Theory of Computation
06S: 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. Winkler.
110. Writing, Presenting, and Evaluating Technical Papers in Computer Science
05F: Arrange
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. Cormen.
118. Programming Languages
06S: 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, McIlroy.
180. Reading Course
181. Special Topics Seminar
185. Algorithms Seminar
06W: Arrange Chakrabarti.
186. Numerical Analysis Seminar
187. Computer Architecture and Hardware Seminar
188. Computer Systems Seminar
05F: ArrangeBailey-Kellogg.
06W: Arrange Donald.
06S: ArrangePellacini.
Prerequisite: Computer Science 23, 25, and 37, or permission of the instructor. Computer Science 58 may be recommended.
257. Supervised Undergraduate Teaching
May be taken multiple times for credit. One course equivalent.
297. Graduate Research
Student participates in research under the supervision of a faculty member. May be taken multiple times for credit. One course equivalent.
298. Thesis Research
Student participates in research under the supervision of a faculty member. May be taken multiple times for credit. Two course equivalents.
299. Full-Time Thesis Research
Student participates in research under the supervision of a faculty member. May be taken multiple times for credit. Three course equivalents.