# Natural Sciences: Computer Science, 2012-2013

### 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 (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 and capabilities that transcend short-term fashions and fluctuations in computer hardware and software. Computer Science offers a major, a concentration for mathematics majors, a concentration for physics majors, and a minor. Computer Science also contributes substantially to the concentration in scientific computing. Details of these programs are available 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 1928 Professor of Mathematics* **Curtis Greene**

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

*Professor of Biology ***Philip M. Meneely**

*Professor of Physics ***Walter Smith**

*Associate Professor of Physics ***Peter Love**

At Bryn Mawr College:

*Professor ***Deepak Kumar**

*Associate Professor ***Douglas Blank**

*Assistant Professor ***Dianna Xu**

### Major Requirements

- CMSC 105 and 106.
- CMSC/MATH 231 (Discrete Mathematics).
- CMSC 240, 245, 340 and 345.
- CMSC 350, 355 or 356.
- 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

- CMSC 105 and 106.
- Either CMSC 240 or 245.
- Either CMSC 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 PHYS 316, 322).

### The Computer Science Concentration for Physics Majors

- CMSC 105 and 106.
- Either PHYS 322 (Solid State Physics) or CMSC/PHYS 304 (Computational Physics).
- 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.

### The Concentration in Scientific Computing

For Mathematics, Physics, Chemistry, Biology, Economics and Astronomy majors: see the separate section in this catalog

### Minor Requirements

- CMSC 105 and 106.
- CMSC/MATH 231 (Discrete Mathematics).
- Either CMSC 240 and (355 or 356), or CMSC 245 and 350.
- Either CMSC 340 or 345.

### Courses

#### 100 The World of Computing NA/QU

*J.Dougherty*

This is a 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. *Does not count toward the major. Typically offered in alternate years*.

#### 101 Fluency with Information Technology NA/QU

*Staff*

This is 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 explore a range of uses of information technology in various fields. Does not count toward the major. *Typically offered in alternate years*.

#### 105 Introduction to Computer Science NA/QU

*D.Wonnacott/Staff*

This is an 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; and associated programming skills. There is a weekly programming laboratory section. *Typically offered every Fall*.

#### 106 Introduction to Data Structures NA/QU

*J.Dougherty*

This is an 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) and an introduction to object-orientated programming. There is a weekly programming laboratory section. *Prerequisite*: CMSC 105 (or 110 at Bryn Mawr) or the instructor’s consent. *Typically offered every Spring*.

#### 130 Foundations of Rigorous Thinking NA/QU

*S.Lindell*

This is a quantitative seminar to develop reasoning skills through mathematics: logic and sets. It uses symbology for abstract objects and formal methods of computing. This is a transition course for non-science students who might wish to do further work in computer or cognitive science. *Offered occasionally*.

#### 147 A History of Mechanized Thought NA/QU

*S.Lindell*

An exploration of the history of computer and information systems, from early number systems to binary arithmetic, and from the abacus to the modern computer. Includes a laboratory that explores aspects of digital and analog computing. *Offered occasionally*.

#### 187 Scientific Computing: Discrete Systems NA (Cross-listed in Biology)

*D.Wonnacott/P.Meneely*

This is a survey of computational techniques with applications in a variety of natural and social sciences, with an emphasis on problems involving discrete systems such as strings and networks. Computer programming is introduced in lecture, so no prior programming experience is required. First priority is given to students who have declared a concentration in scientific computing; if space is available, freshmen and sophomores share the second-highest priority, with juniors and seniors at the lowest priority. *Prerequisite*: One semester of any (social or natural) science is recommended. *Offered occasionally*.

#### 210 Linear Optimization and Game Theory NA/QU (Cross-listed in Mathematics and Economics)

*L.Butler*

*Prerequisite*: MATH 215 or MATH 115, and concurrent registration in MATH 215. *Typically offered in alternate years*.

#### 215 Human Computer Interaction NA

*S.Lindell*

Interaction between people and machines, with a focus on how to make computer interfaces more convenient. We will consider issues including the study of cognitive principles, foundations of perception, and guidelines for accessibility, along with safety and social implications. *Prerequisite*: One course in Computer Science or the instructor’s consent. *Offered occasionally*.

#### 221 Number Systems and Computer Arithmetic NA/QU (Cross-listed in Mathematics)

*S.Lindell*

This course explores mathematical theory of discrete systems used for numerical representation, with an emphasis on modern techniques for high-speed computing. Included are radix and residue systems, integer and floating-point representation, along with detailed coverage of algorithims for the standard arithmetic operations. *Prerequisite*: MATH 231 (Discrete Math) or a 200-level mathematics course that includes proofs.

#### 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 are encoding and decoding techniques, both for the purposes of data compression and for the detection and correction of errors. *Prerequisite*: MATH 215 (may be taken concurrently). *Offered occasionally*.

#### 240 Principles of Computer Organization NA

*J.Dougherty*

This course explores treatment of the hierarchical design of modern digital computers: boolean logic/algebra, sequential state systems, register machines, instruction sets, memory organization and assembly language programming. Lectures cover the theoretical aspects of system architecture; labs provide implementation experience via a hardware simulator. *Prerequisite*: CMSC 106 (or CMSC 206 at Bryn Mawr) or the instructor’s consent. Mathematics 231 recommended. Concurrent enrollment in this and two other computer science lab courses requires the instructor’s consent. *Typically offered yearly in alternation with Bryn Mawr*.

#### 245 Principles of Programming Languages NA

*D.Wonnacott/J.Dougherty*

Study of the design and implementation of modern programming languages: lexical and syntactic analysis; scoping mechanisms; run-time environments; and implementation of structured, functional, object-oriented and concurrent programming languages. Lectures cover theoretical foundations of language design and implementation; labs provide opportunities to use and implement language features. *Prerequisite*: CMSC 206 or consent. CMSC.MATH is 231 strongly recommended. *Typically offered yearly in alternation with Bryn Mawr*.

#### 287 High Performance Computing NA

*J.Dougherty*

*Prerequisite*: CMSC 206 or the instructor’s consent. *Offered occasionally*.

#### 300 Computer Science Research Foundations NA

*S.Lindell*

This is an introduction to research skills needed for the field of computer science, designed to prepare students for senior thesis or summer research work. *Prerequisite*: Open to junior computer science majors; others with the instructor’s consent.

#### 304 Computational Physics NA/QU (Cross-listed in Physics)

*P.Love*

*Prerequisite*: Junior-standing. PHYS 213 and either CMSC 105 or extensive experience with a programming language or the instructor’s consent. *Typically offered in alternate years*.

#### 340 Analysis of Algorithms NA (Cross-listed in Mathematics)

*S.Lindell*

This course offers qualitative and quantitative analysis of algorithms and their corresponding data structures from a precise mathematical point of view. Topics include performance bounds, asymptotic and probabilistic analysis, worst-case and average-case behavior, and correctness and complexity. We will study particular classes of algorithms, such as sorting and searching in detail. *Prerequisite*: CMSC 106. *Typically offered in alternate years*.

#### 345 Theory of Computation NA (Cross-listed in Mathematics)

*S.Lindell*

This is an introduction to the mathematical foundations of computer science: finite state automata, formal languages and grammars, Turing machines, computability, unsolvability and computational complexity. *Prerequisite*: CMSC/MATH 231. *Typically offered in alternate years*.

#### 350 Compiler Design NA

*D.Wonnacott*

This is an introduction to compiler design, including the tools and software design techniques required for compiler construction. Students construct a working compiler using appropriate tools and techniques in a semester-long laboratory project. Lectures combine practical topics to support lab work with more abstract discussions of software design and advanced compilation techniques. *Prerequisite*: CMSC 245. *Typically offered in alternate years*.

#### 356 Concurrency and Co-Design in Operating Systems NA

*D.Wonnacott*

This is a practical introduction to the principles of shared-memory concurrent programming and of hardware/software co-design, which together underlie modern operating systems; this includes a substantial laboratory component, currently using Java's high-level concurrency and the HERA architecture. *Prerequisite*: CMSC 240. *Typically offered in alternate years*.

#### 392 Software Development for Accessibility NA

*J.Dougherty*

This course covers the software life cycle, including specification, design, coding, verification, validation and documentation. We consider issues of usability and adaptability throughout this cycle and across diverse populations and situations. Students work in teams; field work with practical applications, if available. *Prerequisite*: CMSC 106 (or 206 at Bryn Mawr) or the instructor’s consent. *Offered occasionally*.

#### 393 Physics of Computation NA

*S.Lindell*

This is an advanced seminar covering the fundamental physical limits and potentials of computation. *Prerequisite*: MATH 235 or PHYS 303 or the instructor’s consent. *Offered occasionally*.

#### 394 Software Tools for Computer Science Research NA (Cross-listed in Mathematics)

*D.Lippel*

*Offered occasionally*.

#### 399 Senior Thesis NA

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

This course offers a half credit in both fall and spring semesters, and its purpose is to help students prepare the senior thesis. The seminar, deals with the oral and written exposition of advanced material. *Prerequisite*: Senior standing.

#### 460 Teaching Assistant NA

*S.Lindell*

Does not count toward the major.

#### 480 Independent Study NA

*J.Dougherty*

The pursuit of advanced material under the direct supervision of a faculty member. *Prerequisite*: The instructor’s consent.

#### RELATED COURSES IN MATHEMATICS

MATH 203 **Applied Statistics**

MATH 210 **Linear Optimization and Game Theory**

MATH 215 **Linear Algebra**

MATH 218 **Probability and Statistics**

MATH 222 **Introduction to Scientific Computing**

MATH 250 **Combinatorial Analysis**

#### RELATED COURSES IN PHYSICS

PHYS 316 **Electronic Instrumentation and Computers**

PHYS 322 **Solid State Physics**

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

CMSC 110 **Introduction to Computing**

CMSC 120 **Visualizing Information**

CMSC 206 **Introduction to Data Structures**

CMSC 212 **Computer Graphics**

CMSC 231 **Discrete Mathematics**

CMSC 246 **Programming Paradigms**

CMSC 250 **Computational Models in the Sciences**

CMSC 325 **Computational Linguistics**

CMSC 330 **Algorithms: Design & Practice**

CMSC 355 **Operating Systems**

CMSC 361 **Emergence**

CMSC 371 **Cognitive Science**

CMSC 372 **Artificial Intelligence**

CMSC 376 **Androids: Design & Practice**

CMSC 380 **Recent Advances in Computer Science**