COMPUTER SCIENCE (Div. III)

Chair, Professor KIM B. BRUCE

Professors: BRUCE, LENHART, MURTAGH. Associate Professor: BAILEY. Assistant Professor: DANYLUK*. Visiting Assistant Professor: SACHS.

Computers play an enormously important role in our society. General purpose computers are used widely in business and industry and 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, parallel processing, 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
or Computer Science 135 Introduction to Computer Science:

Enriched Section

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.

Required courses in Mathematics

Mathematics 151 Discrete Mathematics

Mathematics 211 Linear Algebra

Students who take Computer Science 105, 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 can not select Computer Science 373 as their second elective. Note also that Computer Science 105, 108 and 109 are not open to students who have already successfully completed a Computer Science course numbered 134 or higher.

To be eligible for admission to the major, a student must normally have completed Computer Science 136 as well as Mathematics 151 by the end of the sophomore year. Math 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 in Bronfman 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, 108, 109, 134, 135, 136, and 237) consists of an electronic classroom containing 20 color Macintosh computers connected via an ethernet network to Macintosh and Sun file and print servers. This laboratory also contains a projection device enabling the instructor to display the computer screen during lectures and demonstrations.

The Sun laboratory (used in courses numbered 135 and above) consists of a network of powerful RISC workstations, which 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 adviser 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 two semesters 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. Under certain circumstances, the honors work can consist of coordinated study involving a regular course and one semester plus a WSP of independent study. The program culminates in 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.

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 five introductory courses - Computer Science 105: Understanding the Web: Technologies and Techniques, Computer Science 108: Artificial Intelligence: Image and Reality, Computer Science 109: The Art and Science of Computer Graphics, Computer Science 134: Introduction to Computer Science, and Computer Science 135: Introduction to Computer Science: Enriched Section. Complete descriptions of each of these courses are found below. In this section we merely attempt to indicate for which students each of these courses might be appropriate.

Students planning to major in Computer Science will usually begin their studies within the department by taking either Computer Science 134 or 135. Computer Science 134 provides an introduction to computer science and programming. No experience with computers or programming is required in order to take this course. Students with significant programming experience should consider electing either Computer Science 135 or Computer Science 136 (see Advanced Placement below). The combination of Computer Science 134 (or Computer Science 135) and Computer Science 136 serves as a prerequisite to most upper-level courses in the department.

Computer Science 135 is a course designed to introduce students to interesting (but accessible) research areas in computer science. In addition, it covers the basic material discussed in Computer Science 134 at an accelerated pace. It is recommended to students who have had some previous programming experience but not enough to seek advanced placement in Computer Science 136.

Those students interested in learning more about important new ideas and developments in Computer Science, but who are not necessarily interested in developing extensive programming skills, should consider Computer Science 105: Understanding the Web: Technologies and Techniques,Computer Science 108: Artificial Intelligence: Image and Reality, or Computer Science 109: The Art and Science of Computer Graphics. Computer Science 108 discusses the techniques used to construct computer systems that exhibit intelligent behavior from understanding language to learning. Computer Science 109 introduces students to the techniques of computer graphics used for special effects in films, visualization in the sciences, and the creation of artistic images.

Non-majors primarily interested in developing programming skills for use in other disciplines are directed to Computer Science 134. Alternately, those expecting to construct programs that produce graphic images may wish to consider the combination of Computer Science 109 followed by Computer Science 134.

Those students intending to take several Computer Science courses are urged to begin satisfying their mathematics requirements early. Note in particular that Mathematics 151 covers material complementing that in the introductory courses (Computer Science 134, 135, and 136) and is a prerequisite for many advanced courses. As a result it should be taken in the first year a student is at Williams or in the fall of the sophomore year if possible.

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 135.

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 Pascal, C, or Java, and should have covered such topics as recursion, arrays, records, files, and have some exposure to pointers. Copies of programs written and titles of books used in courses will be helpful in this process. Students who have less programming experience or who are not familiar with Pascal, C, or Java should consider electing Computer Science 135.

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 151).

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 (or 135) 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. 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 105, 108, 109, 336, 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 that can be obtained at the Departmental Office.

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. Permission will not be given to Computer Science majors to meet any of the requirements of the major or honors degree on this basis. However, with the permission of the department, courses taken in the department beyond those requirements may be taken on a pass-fail basis.

COURSES INTENDED PRIMARILY FOR NON-MAJORS