(for 2009–2010 academic year)
Professors Mulry (Chair), Nevison
Associate Professor A.D. Nakhimovsky
Assistant Professors Ramachandran, Sommers
Visiting Assistant Professor Spacco
Laboratory Instructors Cucura, Sawyer
Computer science is the study of algorithmic processes and the machines that carry out these processes. Computer science is a mix of theory, application, design, and experiment. Theory addresses questions about the nature and limits of computation, the abstract properties of machine models, the complexity of algorithms, and the formalization of programming languages. Applications include machine and systems design, the design and implementation of programming languages, artificial intelligence, networks, graphics, and simulation. An important aspect of computer science is the development of methods for the systematic and accurate design of large systems in hardware and software. Both applications and theoretical issues must be tested experimentally.
The computer science major prepares students either for graduate study in computer science or for computer-intensive professional careers. The computer science minor and the major in computer science/mathematics prepare students for professions in which computer science overlaps significantly with another discipline. COSC 100, 121, 122, 123, 130, and 150 provide opportunities for non-majors to learn about computer applications in the liberal arts and to survey, at an introductory level, some topics in computer science.
Major Program in Computer Science
The prerequisite for beginning a major in computer science is COSC 101, Introduction to Computing, which should be taken in the first year. Students may bypass COSC 101 by obtaining Advanced Placement credit or demonstrating equivalent experience.
The following computer science courses are required for the major: 102, 201, 202, 290, 303, 304, and three electives from the 400-level courses. In addition, the cognate course MATH 111 is required.
In order to satisfy the major, a minimum grade of C in COSC 102 and 201 is required, as well as a minimum GPA of 2.0 in the courses chosen to meet major requirements, including the cognate course.
Recommendations for Majors Majors who anticipate future graduate study in computer science may wish to take additional mathematics courses from among MATH 112, 113, 250, 310, 316, 320, and 329. Majors interested in the theory of computer science should take seminars COSC 450, Advanced Theory, and COSC 460, Analysis of Algorithms.
Minor Program in Computer Science
Consists of COSC 102, 202, 290, one of 303 or 304, and one additional 300- or 400-level course. A minimum grade of C in 102, as well as a minimum GPA of 2.0 in the courses chosen to meet the minor requirements, are necessary to satisfy the minor.
Honors and High Honors in Computer Science Students who graduate with a 3.2 overall average and a 3.4 average in the major program will receive department honors. Each fall the department may, at its discretion, invite one or more seniors who meet the honors requirements to submit a proposal for senior thesis research. Students whose proposals are accepted and who complete satisfactory theses will be awarded high honors.
Awards See “Honors and Awards: Computer Science” in Chapter VI.
Advanced Placement and Transfer Credit The department grants advanced placement and credit to students who perform satisfactorily on the College Entrance Examination Board Advanced Placement (AP) exam for computer science as follows: students receiving scores of 4 or 5 on the A exam receive credit for COSC 101; students receiving scores of 3 on the AB exam receive credit for COSC 101; students receiving scores of 4 or 5 on the AB exam receive credit for COSC 101 and 102. Other students with sufficient secondary school background in computer science may receive advanced placement without credit after consultation with the department chair. Transfer credit for a computer science course taken at another college or university will be granted only by the approval of the department.
Major Program in Computer Science/Mathematics
Preparation for this major consists of MATH 111 and 112 and COSC 101 and 102. The following courses are required for the major: MATH 113, 250; COSC 201, 202, 290, and 304; either MATH 320 or 323, and one additional mathematics course at the 300 level; either COSC 450 or 460, and one additional computer science course at the 400 level.
Honors and High Honors in Computer Science and Mathematics A student who graduates with an average of 3.4 in courses required for the major will receive honors. A student with an average of 3.7 in the major courses may submit a senior research thesis.
A committee of three members of the faculty, including at least one from each department, will evaluate the thesis. Students completing distinguished theses will receive high honors.
Study Groups Colgate sponsors two study-abroad programs in the natural sciences and mathematics, one at the University of Wales in Cardiff and the other at the University of Wollongong in Australia. See “Off-Campus Study Group Programs” in Chapter VI.
Course Offerings
All credit-bearing laboratories carry 0.25 course credits unless noted otherwise. Please see the “Academic Credit” section in Chapter VI for additional information and restrictions.
100/100L Computers in the Arts and Sciences
Staff
This course introduces students to the fundamentals of computers and technology. It aims to provide the understanding needed to effectively utilize technology and to assess its impact on our lives and careers. The course includes an overview of how computer systems and networks work, including the principles and methods behind the operation of the Internet and the World Wide Web. Students learn to compose web pages using HTML. Other computer applications, such as spreadsheets and databases, are also studied; and a basic introduction to algorithmic and programming concepts is included. The course includes a weekly two-hour laboratory. The required credit-bearing laboratory COSC 100L must be taken concurrently with COSC 100. No computer experience is required. The course does not count toward the major. This course is crosslisted as CORE 126.
101/101L Introduction to Computing I
Staff
This course is an introduction to computer science through the study of programming utilizing the programming language Python. Topics include program control, data structures, arrays, classes and objects, recursion, inheritance and polymorphism, data abstraction, and modular design. A weekly two-hour laboratory provides the opportunity to develop programming and design skills. The required credit-bearing laboratory COSC 101L must be taken concurrently with COSC 101. This course, or its equivalent, is a prerequisite to the computer science major. It is recommended also for students in other disciplines who desire a rigorous introduction to computers and programming.
102/102L Introduction to Computing II
Staff
This course is a continuation of COSC 101 and is the first course in the major. It develops advanced programming topics such as abstract data types and algorithms and their analysis. Abstract data structures introduced include stacks, queues, lists, and binary trees; algorithms include search and sort procedures. The concepts of information hiding, data abstraction, and modular design are emphasized. Object-oriented programming is used throughout the course. Laboratories include the design and implementation of programs that illustrate the topics of the course. There are three lectures and a two-hour laboratory each week. The required credit-bearing laboratory COSC 102L must be taken concurrently with COSC 102. Prerequisite: COSC 101.
121 Introduction to Biology-Inspired Algorithms
Staff
This course is an introduction to computer methods, cellular automata, genetic algorithms, and neural networks, inspired by biological processes. Cellular automata are used to simulate population growth as well as other physical phenomena such as fluid flow. Genetic algorithms are used to find optimal solutions, for example in portfolio maximization, using Darwinism. Neural networks are used in learned pattern matching, such as in handwriting recognition and portfolio analysis. A number of variations of these methods are covered. Students use existing tools to explore models simulated or solved using these methods. No programming experience is necessary; however, students are expected to be proficient in using a word processor and web browser. The course does not count toward the major.
122/122L Introduction to Computer Graphics and Animation
C. Nevison
This course provides an introduction to the fundamentals of computer graphics, animation, and algorithms that are the basis for image processing. The course also introduces a programming system that provides an object-oriented approach with tools for animations of three-dimensional graphics. The course includes a weekly two-hour laboratory where students gain practice in testing and implementing the concepts introduced in class. No prior programming experience is required. The required credit-bearing laboratory COSC 122L must be taken concurrently with COSC 122. The course does not count toward the major.
123/123L Introduction to Robotics
Staff
In the future, robots may perform tasks considered too dull, dirty, or dangerous for humans. They could entertain us, clean our houses, mow our lawns, build our cars, fight our wars, perform surgery on our hearts and brains, and explore distant planets and the deepest oceans. Who knows what else? This course introduces the fundamental concepts of robotics. Topics include locomotion, sensing, perception, and control. Students construct and program robots in weekly laboratory sessions. The required course-bearing laboratory COSC 123L must be taken concurrently with COSC 123. No computer experience is required. The course does not count toward the major.
130 Measuring the Internet
J. Sommers
This course introduces students to the principles and algorithms used in the everyday operation of the internet, as well as concepts and practical problems in network and system security. Students also examine the ethical, social, and political aspects of the technical topics raised in class. To make concepts concrete, students engage in collecting and analyzing data measured from internet paths and systems, and examine how these concepts relate to contemporary experience. No prior programming experience is necessary. This course does not count toward the major. Not open to students who completed Core Scientific Perspectives, The Underside of the Internet.
150 Contemporary Issues in Computer Science
P. Mulry, V. Ramachandran
This course provides an introduction to contemporary concepts, models, and issues in computer science. Topics introduced are chosen from the nature and limits of computation, algorithms and their applications, machine intelligence, logic and systems design, coding, cryptography, and others. The course relates these topics to contemporary experience by examining associated ethical, legal, social, and political issues such as privacy in the electronic age, software reliability, information access, technological overload, and electronic piracy. Class format includes lecture, working with and testing of concepts, and class discussion. Students use the Internet as a tool to complete a group research project. No computer experience is required. The course does not count toward the major. This course is crosslisted as CORE 142.
201/201L Computer Organization
C. Nevison, J. Spacco
This course is a study of the fundamental concepts of computer architecture. Topics include the representation of information, components of the computer and how they interact, microarchitecture and microprogramming, conventional machine and assembly language, and advanced architectures. Several types of computer design are reviewed; a RISC architecture is the subject of detailed study. The laboratory is used to examine how different components of a computer’s architecture can affect its performance. Three lectures and a two-hour laboratory each week. The required credit-bearing laboratory COSC 201L must be taken concurrently with COSC 201. Prerequisite: COSC 101. Offered in the fall only.
202/202L Introduction to Symbolic Programming
A.D. Nakhimovsky
This course teaches symbolic computation in a functional programming environment, while providing a general introduction to programming languages and computer science. The emphasis is on alternative modes of algorithmic expression, program design, data abstraction, and skillful use of recursion. Topics include recursive and higher-order procedures, functional programming in contrast with imperative programming, performance analysis of algorithms, data abstraction and abstract data types (including infinite data types), data-directed and object-oriented programming, constraint propagation, and logic programming. Laboratory assignments build simple versions of well-known AI and simulation programs. There are three lectures and a two-hour lab each week. The required credit-bearing laboratory COSC 202L must be taken concurrently with COSC 202. Prerequisite: COSC 101. Offered in the spring only.
290/290L Discrete Structures
P. Mulry
This course introduces concepts and methods in discrete structures with various applications to computer science. Topics include sets, logic, relations, functions, induction, and recursion; order relations and structures such as posets, lattices, and Boolean algebras; algebraic structures such as semigroups, monoids, products, and quotients; trees, languages, and finite-state machines. Methods are tested and implemented in a weekly laboratory component. The required credit-bearing laboratory COSC 290L must be taken concurrently with COSC 290. Prerequisite: COSC 101, MATH 111, or equivalent. Offered in the spring only.
303/303L Principles of Design for Large Systems
C. Nevison, J. Spacco
This course surveys the tools and techniques for the design and implementation of large systems on computers, both local and distributed. The organizational and communications problems associated with large system design are discussed, as well as methods for overcoming these problems. This course includes a laboratory component in which students work in teams to design part or all of a large system. The required credit-bearing laboratory COSC 303L must be taken concurrently with COSC 303. Prerequisites: COSC 102 and 201. Offered in the spring only.
304/304L Theory of Computing
P. Mulry
This course introduces the theory of computing and includes such topics as automata and their relationship to formal grammars, Turing machines and other models of computing, undecidable problems, and computational complexity. The required credit-bearing laboratory COSC 304L must be taken concurrently with COSC 304. Prerequisites: COSC 102 and 290. Offered in the fall only.
420/420L Programming Languages
P. Mulry
This course surveys the salient features of diverse programming languages and examines the foundations and principles of language design. Topics include formal description of language syntax, ambiguity, storage allocation, parameter linkage, and current issues in language design. The required credit-bearing laboratory COSC 420L must be taken concurrently with COSC 420. Prerequisites: COSC 304 or permission of instructor.
425/425L Compiler Design
V. Ramachandran
An exploration of the principles by which high-level programs and their data structures are analyzed and mapped into corresponding low-level implementations and representations. Topics include regular expressions and symbol tables for lexical analysis, attribute grammars and tree manipulations for syntactic/semantic analysis, continuations, unification-based inference of data types, and graph-theoretic algorithms for program optimization. The required credit-bearing laboratory COSC 425L must be taken concurrently with COSC 425. Prerequisites: COSC 201 and 304, or permission of instructor.
430/430L Artificial Intelligence
A.D. Nakhimovsky
This seminar investigates how computers can be made to behave “intelligently.” Particular topics include the programming language LISP, natural language processing, computer vision, search techniques, AI databases, story comprehension, medical diagnosis, and problem-solving. The emphasis is on writing small versions of classic AI programs. The required credit-bearing laboratory COSC 430L must be taken concurrently with COSC 430. Prerequisite: COSC 303 or permission of instructor.
435/435L Computer Graphics
J. Spacco
This seminar is an introduction to the concepts and techniques of interactive computer graphics. A broad spectrum of subjects including computational geometry, picture generation and display, illumination models, ray tracing, and the design of user interfaces are discussed. A special independent project based on individual study and normally involving a substantial working program is expected of each student. The required credit-bearing laboratory COSC 435L must be taken concurrently with COSC 435. Prerequisite: COSC 303 or permission of instructor.
440/440L Operating System Seminar
J. Sommers
A brief historical review of computer operating systems serves as an introduction to a detailed consideration of the machine and language features required to support a complex time-sharing operating system. The ideas and techniques of interrupts, concurrent processing, paging, scheduling, reentrant procedures, and various memory protection schemes are studied. The required credit-bearing laboratory COSC 440L must be taken concurrently with COSC 440. Prerequisite: COSC 303 or permission of instructor.
445/445L Parallel and Distributed Computing
C. Nevison
This course surveys the field of parallel and distributed computing, covering hardware design and architecture, interconnection networks, and parallel algorithms. In addition to the broad survey, students concentrate on the implementation of message-passing parallel computers and algorithms. This aspect of the course includes laboratory work using the parallel computer laboratory. The required credit-bearing laboratory COSC 445L must be taken concurrently with COSC 445. Prerequisites: COSC 303 and 304, or permission of instructor.
450/450L Advanced Theory
P. Mulry
This course addresses topics in the theory of computation and the semantics of programming languages. Topics include axiomatic, denotational, and operational semantics, type theory, and categorical models of computation. Students work collectively, presenting and implementing various issues raised in the course. The required credit-bearing laboratory COSC 450L must be taken concurrently with COSC 450. Prerequisite: COSC 304 or permission of instructor.
455/455L Distributed Web Applications
A.D. Nakhimovsky
This course addresses theoretical, methodological, and practical aspects of creating distributed web applications. It introduces students to meta-languages, such as XML and related technologies, and in the process builds on their theoretical background in formal languages and grammars, parsing, and interpretation. It also builds on and further develops the background in software engineering that students acquire in COSC 303. The emphasis is on distributed systems consisting of components interacting over standard interfaces, frequently using XML as a standard format for data interchange and presentation. The course includes a group project. The required credit-bearing laboratory COSC 455L must be taken concurrently with COSC 455. Prerequisites: COSC 303 and 304 (the latter may be concurrent), or permission of instructor.
460/460L Analysis of Algorithms
V. Ramachandran
This course provides a conceptual framework within which both theoretical and concrete analyses of computer algorithms may be developed. Topics to be covered include abstract models of computation; the efficient design of algorithms using data structures such as trees, networks, lists, queues, and stacks; sorting; searching; graph algorithms; and intractable problems. The required credit-bearing laboratory COSC 460L must be taken concurrently with COSC 460. Prerequisites: COSC 304 or permission of instructor.
465/465L Computer Networks
J. Sommers
This course introduces the fundamental concepts in computer networks. Topics include layered network architecture, error detection and correction, medium access control, routing, congestion control, and internetworking. If time permits, the following advanced topics may also be included: network security, multimedia, multicast, and wireless networking. Students complete weekly laboratory assignments in which they build network applications and implement increasingly complex network protocols in order to gain a deeper understanding of topics covered in class. The required credit-bearing laboratory COSC 465L must be taken concurrently with COSC 465. Prerequisites: COSC 303 or permission of instructor. Some knowledge of differential calculus and elementary probability and statistics is helpful.
480/480L Topics in Computer Science
Staff
A seminar offered occasionally as an alternate to others in the department. Topics vary depending upon needs of students and interests of the instructor. Students interested in the specific content of this course as offered in a particular term should consult the instructor. The required credit-bearing laboratory COSC 480L must be taken concurrently with COSC 480. This seminar is counted toward completion of the major requirement. Prerequisites: COSC 303 and 304, or permission of instructor.
491 Independent Study
Staff
An independent study of a theoretical or experimental nature chosen from the computer science or applications area. Open to majors by invitation of the department.