# Computer Science: 2007-2008

### Description

Computer Science is the representation and manipulation of information - the study of the theory, analysis, design, and implementation of the data structures that represent information, and the algorithms that transform them. Computer Science is interdisciplinary, with roots in mathematics, physics and engineering, and with applications in virtually every academic discipline and professional enterprise.

Computer Science at Haverford College (**www.cs.haverford.edu**) emphasizes these fundamental concepts in conjunction with depth of thought and clarity of expression. This approach is consistent with the principles of scientific education in the liberal arts. The aim is to provide students with a base of skills which transcend short-term fashions and fluctuations in computer hardware and software. Some of these skills are mathematical, while others come from the rapidly growing and maturing field of computer science itself.

The Program in Computer Science offers a Major, a Concentration for Mathematics Majors, a Concentration for Physics Majors, and a Minor. Details of these programs are given at www.cs.haverford.edu/curriculum.

### Faculty

Professor Steven Lindell

Associate Professor David G. Wonnacott

Assistant Professor and Lab Coordinator John P. Dougherty

Affiliated Faculty:

Professor of Mathematics Lynne Butler

J. McLain King Professor of Mathematics Curtis Greene

William H. and Johanna A. Harris Distinguished Professor of Computational Science Robert Manning

Professor of Biology Philip M. Meneely

Associate Professor of Physics Walter Smith

Assistant Professor of Physics Peter Love

At Bryn Mawr College:

Professor Deepak Kumar

Associate Professor Douglas Blank

Assistant Professor Dianna Xu

### Major Requirements

- Computer Science 105 and 206
- Computer Science/Math 231 (Discrete Mathematics)
- Computer Science 240, 245, 340, and 345
- Computer Science 350 or 355
- One additional 300-level course in computer science, and two additional courses numbered 200 or higher (or related courses in math or physics)
- Computer Science 480 project and paper

### The Computer Science Concentration for Mathematics Majors

- Computer Science 105 and 206
- Either Computer Science 240 or 245
- Either Computer Science 340 or 345
- One additional computer science course numbered 300 or higher
- One additional computer science course numbered 200 or higher, or a related course in mathematics or physics (such as Math 203, 210, 218, 231, 235, 236, 237, 250, or Physics 316, 322).

### The Computer Science Concentration for Physics Majors

- Computer Science 105 and 206
- Physics 316 (Electronic Instrumentation and Computers)
- Either Physics 322 (Solid State Physics) or Computer Science/Physics 304 (Computational Physics)
- Two additional courses numbered 200 or higher chosen from the Haverford or Bryn Mawr computer science programs

### Minor Requirements

- Computer Science 105 and 206
- Computer Science/Math 231 (Discrete Mathematics)
- Either Computer Science 240 and 355, or Computer Science 245 and 350
- Either Computer Science 340 or 345

### Requirements for Honors

All astronomy majors are regarded as candidates for Honors. The award of Honors will be made on the basis of superior work in the departmental courses, in certain related courses, and in the comprehensive examinations, with consideration given for independent research.

### Courses

- 100
**The World of Computing**NA/QU

*J.Dougherty*

Survey of fundamental ideas in computing (user interfaces, algorithms, translation, history, Internet and Web, limits of computation, artificial intelligence, social implications, accessibility), with a weekly laboratory/discussion section and a term project to extend course concepts and demonstrate quantitative reasoning. Prerequisite: none. - 101
**Fluency with Information Technology**NA/QU

*S.Lindell*

A study of the skills, concepts and capabilities involve in the design, implementation and effective use of information technology. Using a variety of quantitative techniques, we will explore a range of uses of information technology in various fields. Prerequisite: none - 105
**Introduction to Computer Science**NA/QU

*J.Dougherty, D.Wonnacott*

Introduction to the intellectual and software tools used to create and study algorithms: formal and informal problem specification; problem solving and algorithm design techniques; reliability, proofs, and testing techniques; program clarity, complexity and efficiency; functional and imperative paradigms; associated programming skills. Weekly programming laboratory section. Prerequisite: none Typically offered every Fall. - 130
**Foundations of Rigorous Thinking**NA/QU

*S.Lindell*

Develops rigorous thinking skills through the linguistic foundations of mathematics: logic and sets. Emphasis on using symbology to represent abstract objects and the application of formal reasoning to situations in computer science. Designed to serve as a transition course for non-science students who might wish to do further course work in computer or cognitive science. Offered occasionally. - 147
**The History of Mechanical Thought**NA

*S.Lindell*

An exploration of the history of computer and information systems, from early number systems to binary logic, and from the abacus to the modern computer. We will also explore what makes a machine automatic, or a general purpose calculating machine. Offered occasionally. - 187
**Computing Across the Sciences**NA (Cross-listed in Biology)

*D.Wonnacott, P.Meneely*

Study of the computational techniques to investigate continuous and discrete systems in a variety of sciences: numerical techniques for simulation and optimization, important in the analysis of continuous systems; discrete systems emphasizing biological sequence alignment with DNA and proteins. No prior experience with programming is required. Prerequisite: One semester of calculus; one semester of any lab science is also highly recommended. Offered occasionally. - 206
**Introduction to Data Structures**NA/QU

*D.Wonnacott*

Overview of the intellectual and software tools used to create and study data structures: specification of data types; abstraction and representation; reasoning tools to study correctness and efficiency; classic data structures for collections (set, vector, list, stack, queue, tree, graph); introduction to object-orientated programming. Weekly programming laboratory section. Prerequisite: Computer Science 105 (or 110 at Bryn Mawr) or instructor consent. Typically offered every Spring. - 210
**Linear Optimization and Game Theory**NA/QU (Cross-listed in Mathematics and Economics)

*L.Butler*

Prerequisite: Math 121 and instructor consent, or Math 215. Typically offered in alternate years. - 225
**Fundamentals of Databases**NA

*S.Lindell*

Introduction to the principles of relational database design and use, including the entity/relationship data model and the logical algebra/calculus behind query languages. An integrated laboratory component covers declarative programming using the international standard SQL. Prerequisite: Computer Science 206 and Computer Science/Math 231. Offered occasionally. - 235
**Information and Coding Theory**NA (Cross-listed in Mathematics)

*S.Lindell*

This course covers the mathematical theory of the transmission (sending or storing) of information. Included will be encoding and decoding techniques, both for the purposes of data compression and for the detection and correction of errors. Prerequisite: Math 215 or equivalent (may be taken concurrently). Offered occasionally. - 240
**Principles of Computer Organization**NA

*D.Wonnacott*

Treatment of the hierarchical design of modern digital computers: boolean logic/algebra; sequential state systems; register machines; instruction sets; memory organization; assembly language programming. Lectures cover the theoretical aspects of system architecture; labs provide implementation experience via a hardware simulator. Prerequisite: Computer Science 206 or instructor consent; Computer Science/Math 231 strongly recommended. Typically offered yearly in alternation with Bryn Mawr. - 245
**Principles of Programming Languages**NA

*D.Wonnacott*

Study of the design and implementation of modern programming languages: lexical and syntactic analysis; scoping mechanisms; run-time environments; implementation of structured, functional, object-oriented, and concurrent programming languages. Lectures cover theoretical foundations of language design and implementation; labs provide opportunities to both use and implement language features. Prerequisite: Computer Science 206 or instructor; Computer Science/Math 231 strongly recommended. Typically offered yearly in alternation with Bryn Mawr. - 304
**Computational Physics**NA/QU (Cross-listed in Physics)

*P.Love*

Prerequisite: Junior standing. Physics 213 and either Computer Science 105 or extensive experience with a programming language; you can also enroll with consent of the instructor. Typically offered in alternate years. - 340
**Analysis of Algorithms**NA (Cross-listed in Mathematics)

*S.Lindell*

Qualitative and quantitative analysis of algorithms and their corresponding data structures from a precise mathematical point of view. Performance bounds, asymptotic and probabilistic analysis, worst case and average case behavior. Correctness and complexity. Particular classes of algorithms such as sorting and searching will be studied in detail. Prerequisite: CMSC 206. Typically offered in alternate years. - 345
**Theory of Computation**NA (Cross-listed in Mathematics)

*S.Lindell*

Introduction to the mathematical foundations of computer science: finite state automata, formal languages and grammars, Turing machines, computability, unsolvability, and computational complexity. Prerequisite: Computer Science/Math 231. Typically offered in alternate years. - 350
**Compiler Design**NA

*D.Wonnacott*

A practical introduction to modern compiler and interpreter design with a substantial laboratory component using compiler-writing tools. Prerequisite: Computer Science 245. Typically offered yearly in alternation with Bryn Mawr. - 355
**Operating Systems**NA

*D.Wonnacott*

A practical introduction to modern operating systems, with a substantial laboratory component. Prerequisite: Computer Science 240 Typically offered yearly in alternation with Bryn Mawr. - 392
**Advanced Topics: High Performance Scientific Computing**NA

*J.Dougherty*

Introduction to parallel computing with particular attention to applications in the natural sciences and economics: architectures, shared vs. distributed memory, SPMD, pipelining, granularity and locality, interprocess communication, performance issues, dependability; lab work using MPI or PVM. Prerequisite: Computer Science 206 required; 240 and 355 recommended; or permission of instructor Offered occasionally. - 393
**Physics of Computation**NA

*S.Lindell*

Advanced seminar convering the fundamental physical limits and potentials of computation. Prerequisite: Math 235 or Physics 303 or instructor consent. Offered occasionally. - 394
**Number Systems and Computer Arithmetic**NA (Cross-listed in Mathematics)

*S.Lindell*

The mathematical theory of discrete systems used for numerical representation, including their arithmetic algorithms, with an emphasis on modern techniques for high-speed computing. Prerequisite: Discrete Mathematics 231 or another 200 level MATH course with rigorous proofs Offered occasionally. - 399
**Senior Seminar**NA

*Staff*

Seminar for seniors writing theses, dealing with the oral and written exposition of advanced material. Offered occasionally. - 480
**Senior Thesis Preparation**NA

*J.Dougherty, S.Lindell, D.Wonnacott*

An independent study course, taken for a half credit in both the fall and the spring semesters of the senior year, whose purpose is to research and prepare a written expression and oral presentation of advanced material under the direct supervision of a faculty member.

**RELATED COURSES IN MATHEMATICS**

- 203 Applied Statistics
- 210 Linear Optimization and Game Theory
- 215 Linear Algebra
- 218 Probability and Statistics
- 222 Introduction to Scientific Computing
- 250 Combinatorial Analysis

**RELATED COURSES IN PHYSICS**

- 316 Electronic Instrumentation and Computers
- 322 Solid State Physics

**COMPUTER SCIENCE COURSES OFFERED AT BRYN MAWR COLLEGE**

- 110 Introduction to Computing
- 120 Visualizing Information
- 212 Computer Graphics
- 231 Discrete Mathematics
- 246 Programming Paradigms
- 325 Computational Linguistics
- 330 Algorithms: Design & Practice
- 361 Emergence
- 371 Cognitive Science
- 372 Artificial Intelligence
- 376 Androids: Design & Practice
- 380 Recent Advances in Computer Science