Computer Science Major

Table of Contents

• Current Information
• Background and Goals
• Major Requirements
• Descriptions of Courses
• Department Faculty

     Professor Mike Erlinger, Chair
     Computer Science Department
     Harvey Mudd College
     301 Platt Blvd
     Claremont, CA 91711
     909-621-8912 or -8225
     email: mike@cs.hmc.edu

Current Information

Computer Science was formally instituted as a major at Harvey Mudd College in the Spring of 1992. Currently the total number of HMC majors in Computer Science in their sophomore, junior, and senior years is about 75. Additionally, we provide for students in the HMC Joint CS/Math major (currently about 25 students) and students from the other Claremont Colleges.

The Computer Science Department has 10 full-time faculty. Our newest faculty member is Professor Christine Alvarado, who received the Ph.D. from MIT. Professor Alvarado brings new insight into problems of human computer interaction and artificial intelligence.

Since fall 1996, we have been using the Java programming language in the introductory programming course. The second course, CS 60, does a breath first investigation of many areas of computer science. CS 60 uses rex (a locally developed functional language), Java, Prolog, and a simple assembly language ISCAL. The third course, CS 70, emphasizes data structuring, using C/C++ as the language. CS 81 focuses on aspects of computation and logic for computer science into a single course. More advanced courses, such as Programming Languages, Artificial Intelligence, Software Development, Computer Systems, and Databases depend on CS 70 and CS 81.

Computer Science is housed in the Olin Science Center 1250 Dartmouth Ave. (at Foothill) with laboratories in the adjacent Beckman Hall and the Sprague Library. The Department is supported by a network of servers and clients (which we administer). We use this computing environment in teaching, research and clinic. This network is continuously upgraded with new equipment. Currently we have six servers, one hundred workstations, and about three terabytes of disk space. We have two dedicated teaching laboratories and various research enviroments, e.g., robotics and games. In addition, Computer Science students have access to all other HMC computing facilities.

The Computer Science Clinic is a requirement for graduation, and is usually taken in the senior year, although some students enroll earlier. Recent corporate sponsors of the clinic include The Aerospace Corporation, the IBM Corporation, HRL Laboratories, Nuera, Rockwell Science Center, and WebTV. Information about this year's projects can be found at http://www.cs.hmc.edu/clinic.html. Weekly clinic presentations are open to visitors. See the calendar at http://www.cs.hmc.edu/clinic/.

A partial list of past Computer Science Clinic projects includes:

• Creation of a new standard for the management of range countdown clocks.
• Development of a software module that converts a digital photo of a document into an image that looks scanned.
• Design and implementation of an extensible interface for current and future insulin pumps, glucose sensors, and related diabetes technology.
• Design and implementation of a computer security tool based on the biological immune system paradigm.
• Design and implementation of an extensible software architecture that enables satellite anomalies to be detected and displayed in visual form.
• Development of a simulation model of the GPS ground network and verification of that model via available data.
• Implementation of the MESQUITE mesh smoothing toolkit on a distributed cluster.
• Implementation of the VAIL waveform analysis tool on the the "grid" highly-parallel computing environment.

In addition to the CS Clinic, students may also engage in individual directed research, one outcome of which can be published papers in the literature. Current research projects include the areas of multiprocessor routing algorithms, network security, active messages, linear-logic programming languages, languages for real-time control, recognition of items in images, robotics, controlling computers with EEG signals, and others.

Our student staff operates the department's network and machines. This provides an added learning experience for those who desire it.

The Computer Science Colloquium meets once a week and features invited as well as local speakers, information of current interest, discussions of graduate schools and career opportunities.

Background and Goals

The purpose of the Computer Science major at HMC is to provide a clear academic focus for the discipline of Computer Science. Our goals are:

• Goal 1:
  All HMC students should receive an introduction in the field of computer science in the core curriculum that exposes them to the intellectual depth and breath of computer science and provides some experience with programming and problem solving.

• Goal 2:
  Our majors should have a strong background in the field of computer science blending experimentation, theory, and design, and should be able to integrate their broad background derived from the HMC Core Curriculum.

• Goal 3:
  Our majors should possess strong oral and written communication skills, leadership skills, and understand the impact of their work on society.

• Goal 4:
  Our majors should have opportunities to engage in significant projects and research.

• Goal 5:
  Our majors should be prepared for opportunities including immediate employment and graduate school.

• Goal 6:
  Our faculty members should be effective teachers and mentors.

• Goal 7:
  Our faculty members should be productive scholars who make an impact on our disciplines and involve students in our research.

• Goal 8:
  Our faculty members should be active in service to the college and our local or professional communities.

• Goal 9:
  The department should promote an environment that is welcoming and supportive to all students.

• Goal 10:
  The department should have a reputation for excellence within and beyond the college.

• Goal 11:
  The department should cultivate good relationships with the other academic departments at HMC and with our computer science colleagues at the other Claremont Colleges.

Computer Science Major Requirements

The HMC CS major produces CS professionals and future academics well-rounded and well-grounded in CS fundamentals. We offer specializations by way of the approved electives, in combination with clinic projects. Independent research is encouraged as an option. The Computer Science major therefore consists of the following requirements:

When taken in the context of HMC graduation requirements, the CS major requirements generally leave at least two courses which may be freely chosen.

Each of the components of the major is described below.

CS foundation requirements:

CS kernel requirements:

Most of the above courses include an essential laboratory component, in the form of computer-based development exercises and projects.

CS elective requirement:

Students may substitute electives in one or more CS-related areas, such as in Engineering or Mathematics, with the consent of the faculty advisor.

CS Clinic Requirement:

Each CS student is required to enroll in the CS Clinic (CS 183 and 184) for one full academic year (two semesters in the same academic year).

CS Colloquium Requirement

A precedence diagram (.pdf, .ps, .gif) for Computer Science courses is available in downloadable form. For the hard copy of this document, the diagram should be attached at the end. There is also a spread-sheet of sample four-year programs (.ps, .pdf).

A typical course sequence showing major courses only:

Descriptions of Computer Science Courses

CS 5. Introduction to Computer Programming
Alvarado, Dodds, Kuenning, Libeskind-Hadas. Introduction to programming and problem solving via computer. Students are introduced to and program in Java. In this course, students explore data representation (both simple and structured data types, classes, objects), flow-control structures (if, for, recursion, subroutines), basic algorithms (sorting, searching, numeric computation), and program design. No prior programming experience required. 3 credit hours (First semester.)

CS 60. Principles of Computer Science
Dodds, Keller, and Libeskind-Hadas. Introduction to principles of computer science. Information structures, functional programming, object-oriented programming, grammars, logic, logic programming, correctness, algorithms, complexity analysis, finite-state machines, basic processor architecture, and theoretical limitations. Prerequisites: Computer Science 5 (or equivalent) and one semester of calculus. 3 credit hours. (Both semesters.)

CS 70. Data Structures and Program Development
Kuenning, O'Neill, Stone. Abstract data types including priority queues, dynamic dictionaries, and disjoint sets. Efficient data structures for these data types, including heaps, self-balancing trees, and hash tables. Analysis of data structures including worst-case, average-case, and amortized analysis. Storage allocation and reclamation. Secondary storage considerations. Extensive practice in implementing these data structures for a variety of applications. Prerequisites: Computer Science 60. 3 credit hours. (Both semesters.)

CS 81. Computability and Logic
Keller, Bull (Pomona). An introduction to some of the mathematical foundations of computer science, particularly logic, automata, and computability theory. Develops skill in constructing and writing proofs, and demonstrates the applications of the aforementioned areas to problems of practical significance. Prerequisites: Computer Science 60 and Math 55. 3 credit hours. (Both semesters.)

CS 105. Computer Systems
Erlinger, Kuenning, Bull (Pomona). An introduction to computer systems. In particular the course investigates data representations, machine level representations of programs, processor architecture, program optimizations, the memory hierarchy, linking, exceptional control flow (exceptions, interrupts, processes, and Unix signals), performance measurement, virtual memory, system-level I/O, and basic concurrent programming. These concepts are supported by a series of hands-on lab assignments. Prerequisite: Computer Science 70. 3 credit hours. (Both semesters.)

CS 121. Software Development
Keller, Sweedyk. Rigorous introduction to the technological and managerial discipline concerned with the design and implementation of large software systems. Techniques for software specification, design, verification, and validation. Formal methods for proving the correctness of programs. Student teams design, implement, and present a substantial software project. Prerequisites: Computer Science 70. 3 credit hours. (Both semesters.)

CS 124. User Interface Design
O'Neill. This course introduces students to issues in the design, implementation, and evaluation of human-computer interfaces, with emphasis on user-centered design and graphical interfaces. Students will learn skills that aid them in choosing the right user interaction technique and developing an interface that is well-suited to the people for whom it is designed. (Second semester, alternate years).

CS 125. Computer Networks
Erlinger. Principles and analysis techniques for internetworking. Analysis of networking models and protocols. Presentation of computer communication with emphasis on protocol architecture. Prerequisite: Computer Science 105. 3 credit hours. (Second semester.)

CS 131. Programming Languages
O'Neill, Stone, and Bruce (Pomona). A thorough examination of issues and features in language design and implementation including language-provided data structuring and data-typing, modularity, scoping, inheritance, and concurrency. Compilation and run-time issues. Introduction to formal semantics. Prerequisite: Computer Science 70 and 81. 3 credit hours. (Both semesters.)

CS 132. Compiler Design
Stone. The theory, design, and implementation of compilers and interpreters. The interaction between compiler design and run-time organization. Logistics of porting to new hardware. Prerequisite: Computer Science 105 and 131. 3 credit hours. (Second semester, alternate years.)

CS 133. Databases
Keller. Fundamental models of databases: entity-relationship, relational, deductive, object-oriented. Relational algebra and calculus, query languages. Data storage, caching, indexing, and sorting. Locking protocols and other issues in concurrent and distributed data-bases. Prerequisite: Computer Science 70 and 81 (131 recommended). 3 credit hours. (First semester, alternate years.)

CS 134. Operating Systems: Design and Implementation
O'Neill. Design and implementation of operating systems, including processes, memory management, synchronization, scheduling, protection, filesystems, and I/O. These concepts are used to illustrate wider concepts in the design of other large software systems, including simplicity; efficiency; event-driven programming; abstraction design; client-server architecture; mechanism vs. policy; orthogonality; naming and binding; static vs. dynamic, space vs. time, and other tradeoffs; optimization; caching; and managing large codebases. Group projects provide experience in working with and extending a real operating system. Prerequisite: Computer Science 105. 3credit hours. (Second semester, alternate years.)

CS 136. Advanced Computer Architecture
Erlinger, Kuenning. Reduced vs. complex instruction set architecture, pipelining, instruction-level parallelism, superscalar architectures, advanced memory-hierarchy design, advanced computer arithmetic, multiprocessor systems, cache coherence, interconnection networks, performance analysis and case studies. Prerequisite: Computer Science 105. 3 credit hours. (Second semester, alternate years.)

CS 140. Algorithms (joint-listed as Mathematics 168).
Libeskind-Hadas, Sweedyk, Chen (Pomona). Algorithm design, analysis, and correctness. Design techniques including divide-and-conquer and dynamic programming. Analysis techniques including solutions to recurrence relations and amortization. Correctness techniques including invariants and inductive proofs. Applications including sorting and searching, graph theoretic problems such as shortest path and network flow, and topics selected from arithmetic circuits, parallel algorithms, computational geometry, and others. An introduction to computational complexity, NP-completeness, and approximation algorithms. Proficiency with programming is expected as some assignments require algorithm implementation. Prerequisite: Computer Science 70 and Mathematics 55. 3 credit hours. (Both semesters. Students taking the course as Mathematics 168 have slightly different prerequisites.)

CS 141. Advanced Topics in Algorithms
Libeskind-Hadas. Advanced topics in the design and analysis of combinatorial algorithms. Example topics are amortized analysis of data structures, competitive analysis of on-line algorithms, matroid theory, and introduction to parallel and distributed algorithms. A significant component of the course is written and oral student presentations of material from the original literature. Prerequisite: Computer Science 140/Mathematics 168. 3 credit hours. (First semester, alternate years.)

CS 142. Complexity Theory .
Libeskind-Hadas, Bull (Pomona). Brief review of computability theory through Rice's Theorem and the Recursion Theorem followed by a rigorous treatment of complexity theory. The complexity classes P, NP, and the Cook-Levin Theorem. Approximability of NP-complete problems. The polynomial hierarchy, PSPACE-completeness, L and NL-completeness, #P-completeness. IP and Zero-knowledge proofs. Randomized and parallel complexity classes. The speedup, hierarchy, and gap theorems. Prerequisite: Computer Science 81. 3 credit hours. (First semester.)

CS 144. Scientific Computing (joint-listed as Mathematics 164).
dePillis. Computational techniques applied to problems in the sciences and engineering. Modeling of physical problems, computer implementation, analysis of results; use of mathematical software; numerical methods chosen from: solutions of linear and nonlinear algebraic equations, solutions of ordinary and partial differential equations, finite elements, linear programming, optimization algorithms, and fast-Fourier transforms. Prerequisites: Mathematics 63 and 64, and Computer Science 60. 3 credit hours. (Second semester.)

CS 147. Computer Systems Performance Analysis
Kuenning. Measurement and analysis of computer software and systems performance, with emphasis on methodological issues. Measurement planning and experimental design. Statistical methods for data analysis. Hypothesis testing. Effective graphical and tabular presentation of data. Common errors in performance measurement. Elementary queueing theory. Simulation methods. Project in performance measurement. Typical projects include measurement of databases, theorem provers, file systems, networks, OS kernels, and computer processors.

CS 151. Artificial Intelligence
Alvarado. Knowledge representation, including rule-based systems and neural networks, learning paradigms, and philosophical challenges to artificial intelligence. Discussion of areas of current research: natural language processing, robotics, vision, cognitive modeling, case-based-reasoning. Prerequisite: Computer Science 81 (131 recommended). 3 credit hours. (Second semester.)

CS 152. Neural Networks
Keller. Modeling, simulation, and analysis of artificial neural networks and their relation to biological networks. Design and optimization of discrete and continuous neural networks. Back propagation, and other gradient descent methods. Hopfield and Boltzmann networks. Unsupervised learning. Self-organizing feature maps. Applications chosen from function approximation, signal processing, control, computer graphics, pattern recognition, time-series analysis. Relationship to fuzzy logic, genetic algorithms, and artificial life. Prerequisites: Computer Science 60 and Mathematics 63. 3 credit hours. (First semester.)

CS 153. Computer Vision
Alvarado, Dodds. Computational algorithms for visual perception. Image acquisition, image processing, segmentation. Representation of color, shading, texture, shape. Stereo and motion analysis. Object recognition. Relations to robotics, human perception, image databases. Prerequisite: Computer Science 70. 3 credit hours. (Second semester, alternate years.)

CS 154. Robotics
Dodds. Hands-on introduction to autonomous robotics. Topics span sensor operation and low-level actuator control through architectures and algorithms for accomplishing tasks. There is an emphasis on the recent success of probabilistic approaches throughout the course. The basic framework and analysis of both industrial and biologically-motivated robots are addressed. The laboratory component of the class provides experience in developing algorithms, programming, and testing a range of robot behaviors on our hardware platforms. Prerequisite: Computer Science 70. 3 credit hours. (Second semester)

CS 155. Computer Graphics
Sweedyk. Geometric models for visual output. Rastering. Three-dimensional volume and surface modeling. Reflectance and illumination models. Texturing and shading. Color and animation. Prerequisite: Computer Science 140 and Mathematics 63 (Linear Algebra). 3 credit hours. (First semester.)

CS 156. Parallel and Real-Time Computation
Keller, Chen (Pomona). Characteristics and applications for parallel and real-time systems. Specification techniques, algorithms, architectures, languages, design, and implementation. Prerequisites: Computer Science 105 and 140 (131 recommended). 3 credit hours. (Second semester, alternate years.)

CS 157. Computer Animation
Sweedyk. This course introduces students to the theory and practice of computer animation. The course covers the algorithms and data structures for building and animating articulated figures and particle systems including interpolation techniques, deformations, forward and inverse kinematics, rigid body dynamics, and physically based modeling. In addition the course surveys the art, history and production of computer animation. Prerequisites: Computer Science 155. 3 credit hours. (Second semester, alternate years.)

CS 181, 182. Computer Science Seminar
Staff. Advanced topics of current interest in computer science. Prerequisite: permission of instructor. 3 credit hours. (Both semesters.)

CS 183, 184. Computer Science Clinic I, II
Staff. Team project in computer science, with corporate affiliation. Prerequisites: Computer Science 121. 3 credit hours.

CS 185, 186. Senior Research Project I, II
Staff. Projects involving original research under faculty supervision. 1-3 credit hours.

CS 189. Programming Practicum.
Dodds, Stone. This course is a weekly programming seminar, emphasizing efficient recognition of computational problems and their difficulty, developing and implementing algorithms to solve them, and the testing of those implementations. Attention is given to the effective use of programming tools and available libraries, as well as to the dynamics of team problem-solving. 1 credit hour. (May be repeated for elective credit up to 3 times.) (Both semesters.)

CS 191, 192. Computer Science Project I, II.
Staff. Participation in projects of substantial interest to computer scientists. Emphasis is on the design and implementation of computer systems for real problems. Students typically work in small teams with faculty supervision. 1-3 credit hours per semester.

CS 193, 194, 195, 196. Computer Science Colloquium.
Staff. Oral presentations and discussions of selected topics, including recent developments in computer science. Participants include computer science majors, clinic participants, faculty members, and visiting speakers. Required for all junior and senior computer science majors any semester in residence at HMC. Study abroad students should coordinate this requirement with the Computer Science Faculty member who is organizing colloquium. 0 credit hours.

CS 197, 198. Advanced Problems in Computer Science.
Staff. Independent study in a field agreed upon by student and a faculty member. 1-3 credit hours.

Faculty

Christine Alvarado Assistant Professor of Computer Science, 2005. A.B. Dartmouth College, S.M., Ph.D., Massachusetts Institute of Technology. Professor Avarado's research interests are in the conjunction of artificial intelligence and human computer interaction.

Zachary Dodds, Associate Professor of Computer Science, 1999. B.A., M.S., Ph.D., Yale University. Professor Dodds' interests are in computer vision and robotics.

Michael A. Erlinger, Professor of Computer Science and Chair, 1981. B.S., University of San Francisco; M.S., Ph.D., University of California, Los Angeles; Lecturer, University of California, Los Angeles; Member, Technical Staff, Bell Telephone Laboratories; Senior Project Engineer, Hughes Aircraft Company; Member, Technical Staff, The Aerospace Corporation. Professor Erlinger's interests are in computer systems, especially computer networking.

Robert M. Keller, Csilla and Walt Foley Professor of Computer Science, 1991. B.S., M.S., Washington University; Ph.D., University of California, Berkeley; Assistant Professor, Princeton University; Visiting Assistant Professor, Stanford University; Associate and Full Professor, University of Utah; Director of Research and Vice President, Research and Development, Quintus Corporation; Professor and Chair, Division of Computer Science and Chair of the Graduate Group in Computer Science, University of California, Davis; Visiting Scientist, Lawrence Livermore National Laboratory; Faculty Part-Time Staff Member, Senior Level, Jet Propulsion Laboratory. Professor Keller's interests are in languages and systems for parallel processing and in declarative programming languages.

Geoff Kuenning, Associate Professor of Computer Science, 1998. B.S., M.S., Michigan State University; Ph.D., University of California at Los Angeles; Computer Scientist, Lawrence Livermore Laboratory; Systems Programmer, Ball Computer Products; Senior Software Engineer, Digital Equipment Corporation; Manager of Operating Systems Development, Callan Data Systems; Principal Consultant, Interrupt Technology Corporation; PostDoc, University of California at Los Angeles. Professor Kuenning's interests are in operating systems, file systems, and computer security.

Ran Libeskind-Hadas, Joseph Platt Chair of Effective Teaching, Professor of Computer Science, 1993. A. B. Harvard University, M.S., Ph.D., University of Illinois at Urbana-Champaign; Visiting Lecturer, University of Illinois at Urbana-Champaign. Professor Libeskind-Hadas' interests are in design and analysis of algorithms, parallel computing, and fault-tolerance.

Melissa O'Neill, Assistant Professor of Computer Science, 2001. B.Sc. University of East Anglia (UK), M.Sc. & Ph.D. Simon Fraser University (Canada). Research interests span many systems areas including functional programming, programming language tools, and parallel and distributed computing (with particular reference to easy-to-code finegrained parallelism). Underlying focus is to make programming easier and more reliable. Also interested in user-centered design and digital typography.

Christopher Stone, Assistant Professor of Computer Science, 2000. B.S., M.S., Ph.D. Carnegie-Mellon University. Professor Stone's interests are in programming languages and their compilation.

Elizabeth Sweedyk, Associate Professor of Computer Science, 1999. B.A. Michigan State University, B.S. and M.S.E University of Michigan, Ph.D., University of California, Berkeley; Postdoctoral fellow University of Pennsylvania and DIMACS. Professor Z' s research interests are in algorithms and computer graphi

Wing Cheung Tam, Professor Emeritus of Computer Science, 1974. B.S., M.S., Ph.D., University of California, Los Angeles; Post Graduate Research Engineer, University of California, Los Angeles; Assistant Professor, Wayne State University; Senior System Programmer, McDonnell Douglas Corporation. Professor Tam's interests are in software engineering and real-time systems.

Affiliated Faculty in other HMC Departments

Lisette de Pillis, Associate Professor of Mathematics, 1993. B.A., University of California, San Diego; M.A., Ph.D., University of California, Los Angeles. Professor de Pillis' interests are in scientific computing.

David Harris. Assistant Professor of Engineering, 1999. S.B. and M. Eng. Massachusetts Institute of Technology, 1994; Ph.D., Stanford University, 1999; Visiting Professor: Sun Microsystems, 1997. Professor Harris' interests are in computer architecture.

Sarah Harris. Assistant Professor of Engineering, 2005. B.S. Brigham Young University, M.S., Ph.D. Stanford University.

Ruye Wang. Associate Professor of Engineering, 1990. M.S., Tianjin University, China; M.S., Ph.D., Rutgers University; Lecturer, Peking University, China. Professor Wang's interests are in computer vision.

Affiliated Faculty in other Claremont Colleges

Kim Bruce, Professor of Computer Science, Pomona College.

Everett L. Bull, Professor of Computer Science and Professor of Mathematics, Pomona College. Professor Bruce's interests are in programming languages.

Tzu-Yi Chen, Assistant Professor of Computer Science, Pomona College. Professor Chen's research interests include parallel computing, algorithms, and sparse matrix computations.

Art Lee, Associate Professor, Claremont McKenna College. Professor Lee's interests are in databases and software engineering.