Computer Science Website

COMPUTER SCIENCE (Div. III)

Chair, Professor DUANE BAILEY

Professors: BAILEY, BRUCE*, LENHART***, MURTAGH. Associate Professor: DANYLUK***. Assistant Professors: FREUND, LERNER, TERESCO. Visiting Assistant Professor: WYMAN.

Computers play an enormously important role in our society. General-purpose computers are used widely in business and industry and are found in an increasing number of homes. Special-purpose computers are found in everything from automobile engines to microwave ovens. Understanding and exploiting the great potential of computers is the goal of research in computer science. Among the many fascinating research projects in progress in computer science today are investigations of: ways to focus more computational power on a problem through the simultaneous use of many processors in parallel; revolutionary computer languages designed to simplify the process of constructing complex programs for computers; the use of computer-generated graphic images in the arts and as a tool for visualization in the natural sciences; and the use of digital methods in global communications. The Computer Science Department at Williams seeks to provide students with an understanding of the principles underlying computer science that will enable them to understand and participate in these exciting developments.

The department recognizes that students' interests in computer science will vary widely. The department attempts to meet these varying interests through: (1) its major; (2) a selection of courses intended primarily for those who are interested in a brief introduction to computer science or who seek to develop some specific expertise in computing for application in some other discipline; and (3) recommendations for possible sequences of courses for the non-major who wants a more extensive introduction to computer science. These offerings are discussed in detail below.

MAJOR

The goal of the major is to provide an understanding of algorithmic problem-solving as well as the conceptual organization of computers and complex programs running on them. Emphasis is placed on the fundamental principles of computer science, building upon the mathematical and theoretical ideas underlying these principles. The introductory and core courses build a broad and solid base for understanding computer science. The more advanced courses allow students to sample a variety of specialized areas of computer science including graphics, artificial intelligence, computer networks, software engineering, compiler design, and operating systems. Independent study and honors work provide opportunities for students to study and conduct research on topics of special interest.

The major in Computer Science equips students to take advantage of a wide variety of career opportunities. Thus the major can be used as a preparation for a career in computing, for graduate school, or simply to provide an in-depth study of computer science for the student whose future career will only tangentially be related to computer science.

MAJOR REQUIREMENTS

Required Courses in Computer Science
A minimum of 8 courses is required in Computer Science, including the following:

Introductory Courses

Computer Science 134 Introduction to Computer Science

Computer Science 136 Data Structures and Advanced Programming

Core Courses

Computer Science 237 Computer Organization

Computer Science 256 Algorithm Design and Analysis

Computer Science 334 Principles of Programming Languages

Computer Science 361 Theory of Computation

Electives

Two or more electives (bringing the total number of Computer Science courses to at least 8) chosen from 300- or 400-level courses in Computer Science. At least one of these must be a course designated as a PROJECT COURSE. Computer Science courses with 9 as the middle digit (reading, research, and thesis courses) will normally not be used to satisfy the elective requirements. Students may petition the department to waive this restriction with good reasons.

Required Courses in Mathematics

Mathematics 211 Linear Algebra

Mathematics 251 Discrete Mathematics

Students considering pursuing a major in Computer Science are urged to take Computer Science 134 and to begin satisfying their mathematics requirements early. Note in particular that Mathematic 251 covers material complementing that in the introductory courses (Computer Science 134 and 136) and is a prerequisite for many advanced courses.

Students who take Computer Science 105, 106, 108 or 109 may use that course as one of the two electives required for the major in Computer Science. Those who count Computer Science 109 toward the major must select an elective different from Computer Science 371 (Computer Graphics) for their project course. Similarly, students who count Computer Science 108 as an elective cannot select Computer Science 373 as their second elective, and Computer Science 315 may not be used as a second elective in conjunction with Computer Science 106. Computer Science 105, 106, 108, 109, and 134 are not open to students who have taken a Computer Science course numbered 136 or higher.

To be eligible for admission to the major, a student must normally have completed Computer Science 136 as well as Mathematics 251 by the end of the sophomore year. Mathematics 211 must be completed by the end of the junior year. Students are urged to have completed two of the four core courses (Computer Science 237, 256, 334, and 361) by the end of the sophomore year and must normally have completed at least three out of the four core courses by the end of the junior year.

Satisfactory participation is required in the Computer Science Colloquium by all senior majors. With the advance permission of the department, two appropriate mathematics courses numbered 240 or above may be substituted for one Computer Science elective. Other variations in the required courses, adapting the requirements to the special needs and interests of the individual student, may be arranged in consultation with the department.

Potential majors are strongly encouraged to pick up the latest copy of the Informal Guide to Courses in Computer Science, which can be obtained from the departmental office or on the World Wide Web at http://www.cs.williams.edu. This document contains much more information on the major, including suggested patterns of course selection and advice on courses relevant to different student goals.

LABORATORY FACILITIES

The Computer Science Department maintains two departmental computer laboratories for students taking Computer Science courses. The Macintosh laboratory (used in Computer Science 105, 106, 108, 109, 134, 136, and 237) consists of an electronic classroom containing Macintosh G4 computers. This laboratory also contains projection facilities enabling the instructor to display the computer screen during lectures and demonstrations.

The Unix laboratory (used in courses numbered 136 and above) consists of a network of workstations that are available exclusively to students taking advanced Computer Science courses. These workstations also support student and faculty research in computer science.

THE DEGREE WITH HONORS IN COMPUTER SCIENCE

The degree with honors in Computer Science is awarded to a student who has demonstrated outstanding intellectual achievement in a program of study which extends beyond the requirements of the regular major. The principal considerations in recommending a student for the degree with honors will be: mastery of core material, ability to pursue independent study of computer science, originality in methods of investigation, and creativity in research. Honors study is highly recommended for those students with strong academic records in computer science who wish to attend graduate school, pursue high-level industrial positions in computing, or who would simply like to experience research in computer science.

Prospective honors students are urged to consult with their departmental advisor at the time of registration in the spring of the sophomore or at the beginning of the junior year to arrange a program of study that could lead to the degree with honors. Such a program normally consists of Computer Science 493 and 494 and a WSP of independent research under the guidance of a Computer Science faculty member, culminating in a thesis which is judged acceptable by the department. The program produces a significant piece of written work. The written work often includes a major computer program, depending on the nature of the honors work. All honors candidates are required to give an oral presentation of their work in the Computer Science Colloquium in early spring semester.

Students considering honors work should obtain permission from the department before registering in the fall of the senior year. Formal admission to candidacy occurs at the beginning of the spring semester of the senior year and is based on promising performance in the fall semester and winter study units of honors work. Recommendations for the degree with honors will be made for outstanding performance in the three honors courses. Highest honors will be recommended for students who have displayed exceptional ability, achievement, or originality.

INTRODUCTORY COURSES

The department offers a choice of five introductory courses-Computer Science 105: Understanding the Web: Technologies and Techniques, Computer Science 106: Life as an Algorithm, Computer Science 108: Artificial Intelligence: Image and Reality, Computer Science 109: The Art and Science of Computer Graphics, and Computer Science 134: Introduction to Computer Science.

Computer Science 134 provides an introduction to computer science with a focus on developing computer programming skills. These skills are essential to most upper-level courses in the department. As a result, Computer Science 134 together with Computer Science 136 are required as a prerequisite to most advanced courses in the department. Those students intending to take several Computer Science courses are urged to take Computer Science 134 early.

Those students interested in learning more about important new ideas and developments in Computer Science, but not necessarily interested in developing extensive programming skills, should consider Computer Science 105: Understanding the Web: Technologies and Techniques, Computer Science 106: Life as an Algorithm, Computer Science 108: Artificial Intelligence: Image and Reality, or Computer Science 109: The Art and Science of Computer Graphics. Computer Science 105 explores the computing technology that underlies the internet. Computer Science 106 explores models and theories shared between computer science and biology. Computer Science 108 discusses the techniques used to construct computer systems that exhibit intelligent behavior from learning to planning and problem-solving. Computer Science 109 introduces students to the techniques of computer graphics used for the creation of artistic images. In addition, all four of these courses provide an introduction to the techniques of computer programming.

Although none of our introductory courses assume prior programming skills, some students planning to take Computer Science 134 who have no prior programming experience may find it useful to gain some programming experience together with a broader understanding of our field by taking one of the department's other introductory courses before enrolling in Computer Science 134. On the other hand, students with significant programming experience should consider electing Computer Science 136 (see "Advanced Placement" below). Students in either of these categories are encouraged to contact a member of the department for guidance is selecting a first course.

ADVANCED PLACEMENT

Students with an extensive background in computer science are urged to take the Advanced Placement AB Examination in Computer Science. A score of 4 or better on the AB exam is normally required for advanced placement in Computer Science 136. Students scoring 3 or lower on that exam or who have taken the Advanced Placement A Examination in Computer Science should consider enrolling in Computer Science 134.

Students who wish to be placed in Computer Science 136 but who have not taken the Advanced Placement Examination should consult with the department. Such students should have had a good course in computer science using a structured language such as C++ or Java, and should have covered such topics as recursion, arrays, files, and have some exposure to object-orientation.

PLANS OF STUDY FOR NON-MAJORS

The faculty in Computer Science believes that students can substantially enrich their academic experience by completing a coherent plan of study in one or more disciplines outside of their majors. With this in mind, we have attempted to provide students majoring in other departments with options in our department's curriculum ranging from two-course sequences to collections of courses equivalent to what would constitute a minor at institutions that recognize such a concentration. Students interested in designing such a plan of study in any department should discuss their plans in detail with a member of the faculty. We welcome such inquiries from students. To assist students making such plans, however, we include some suggestions below.

Students seeking to develop an extensive knowledge of computer science without majoring in the department are encouraged to use the major requirements as a guide. In particular, the four core courses required of majors are intended to provide a broad knowledge of topics underlying all of computer science. Students seeking a concentration in Computer Science are urged to complete at least two of these courses followed by one of our upper-level electives. Such a program would typically require the completion of a total of five computer science courses and one course in mathematics (MATH 251).

There are several sequences of courses appropriate for those primarily interested in developing skills in programming for use in other areas. For general programming, Computer Science 134 followed by Computer Science 136 and 237 will provide students with a strong background in algorithm and data structure design together with an understanding of issues of correctness and efficiency. Computer Science 323 provides valuable exposure to the techniques and tools needed for the development and maintenance of large software systems. Students of the program are encouraged to take Computer Science 106 and 134 at a minimum, and should consider Computer Science 136 and 256. The sequence of courses Computer Science 109 and 134 would provide sufficient competence in computer graphics for many students interested in applying such knowledge either in the arts or sciences. For students requiring more expertise in the techniques of computer graphics, Computer Science 136 and 371 could be added to form a four-course sequence.

There are, of course, many other alternatives. We encourage interested students to consult with the department chair or other members of the department's faculty.

GENERAL REMARKS

Divisional Requirements

All Computer Science courses listed may be used to satisfy the Division III distribution requirement.

Alternate Year Courses

Computer Science 106, 108, 109, 315, 323, 336, 337T, 338T, 371, 373, 432, and 434 are each normally offered every other year. All other Computer Science courses are normally offered every year.

Course Numbering

The increase from 100, through 200 and 300, to 400 indicates in most instances an increasing level of maturity in the subject that is expected of students. Within a series, numeric order does not indicate the relative level of difficulty of courses. Rather, the middle digit of the course number (particularly in upper-level courses) generally indicates the area of computer science covered by the course.

Course Descriptions

Brief descriptions of the courses in Computer Science can be found below. More detailed information on the offerings in the department is available in the Informal Guide to Courses in Computer Science.

Courses Open on a Pass-Fail Basis

Students taking a computer science course on a pass-fail basis must meet all the requirements set for students taking the course on a graded basis.

With the permission of the department, any course offered by the department may be taken on a pass-fail basis. Courses graded with the pass-fail option may not be used to satisfy any of the major or honors requirements. However, with the permission of the department, courses taken in the department beyond those requirements may be taken on a pass-fail basis.