You are here: Campus >Registrar's Office > Academic Catalog 2006-2007 > Courses > Computer Science

Computer Science (CS)

Chair: Professor Jeffrey R. Ondich

Professors: David F. Appleyard, Jack Goldfeather, Richard W. Nau, Jeffrey R. Ondich

Associate Professor: David R. Musicant

Assistant Professors: Amy Csizmar-Dalal, David Liben-Nowell

Computer Science is about more than computers: it is the systematic study of processes for solving problems. The Computer Science program at Carleton focuses on understanding how to think about these processes, how to program computers to carry out important tasks efficiently, and how to apply computer science ideas to important applications.

Since computer science plays a key role in our world, Introduction to Computer Science, CS 117, and Data Structures, CS 127, are useful and recommended to all Carleton students. Other options are Explorations in Computer Science, CS 107, which provides an overview of computer technology and an introduction to the fundamental concepts and applications of computer science, and the First Year Seminars that are offered on a regular basis.

Those who choose to major in computer science find many opportunities following graduation. In addition to graduate programs in computer science, Carleton students pursue studies in interdisciplinary areas such as bioinformatics, linguistics, and cognitive science. Students pursuing employment have gone to large companies such as IBM and Microsoft, as well as smaller companies such as Epic Systems and Secure Computing.

Requirements for a Major:

The course requirements are Computer Science 117, 127; Mathematics 110 or 111, 121; Computer Science 177 or Mathematics 236; Computer Science 207, 217, 227, 237; and two additional courses from among: Computer Science courses numbered 240 or above, Mathematics 311, Physics 247 or 343. Although they are not required for the major, Mathematics 232 and a probability and statistics course are recommended. In addition, each senior major must complete an integrative exercise: during fall and winter terms of the senior year, the student will participate on a team of four to seven students working on a faculty-specified project. Potential majors should take Computer Science 127 before the end of the sophomore year.

Students contemplating graduate study in computer science should consider taking additional courses in both computer science and mathematics. Those interested in computer engineering should consider taking physics courses through Electricity and Magnetism, and Electronics.

A guide for majors on the web is available at

Other Courses that Count Toward the Computer Science Major:

Physics 247 Digital Electronics

Physics 343 Electronics

Computer Science Courses:

CS 100. Digital Storytelling Storytelling has been around since the dawn of civilization. How will storytelling evolve in the "Digital Age?" This course explores how computers have, and are, being used to tell stories. We'll study text-based technologies--blogging, the web--and how those models have changed the way we publish and disseminate narratives. We'll also study the roles of audio, video, and images in narrative: computer animation, the ethics of altering digital images, the Story Corps project. Students will use technology (blogs, creating virtual worlds, video) to create and tell their own stories. No previous computer experience is necessary. 6 cr., S/CR/NC, MS, FallA. Csizmar Dalal

CS 107. Explorations in Computer Science This course is designed for students who have never taken a computer science course. It provides an overview of computer technology and an introduction to the fundamental concepts and applications of computer science. We will explore both the technical aspects and the social, political, and ethical aspects of computers and computer technology. Students who have taken Computer Science 117 or higher may not enroll in Computer Science 107. 6 cr., MS, Not offered in 2006-2007.

CS 117. Introduction to Computer Science This course introduces the fundamentals of computer science through problem solving. Students will write programs to solve interesting problems such as processing images. The design and implementation of more extensive projects will introduce students to computer science through such topics as data representation, graphics, recursion, and object-oriented design. No previous programming experience is necessary. 6 cr., MS, Fall,Winter,SpringStaff

CS 127. Data Structures Data structures form the foundation of computer science: they make algorithms more efficient and facilitate problem solving on both small scales and large scales. In this course, we will explore these basic building blocks of computer science and develop computer programs based on these data structures. We will study stacks, queues, trees, linked lists, graphs and hash tables, as well as algorithms for recursion, searching, and sorting. Mathematical methods for analyzing the performance of algorithms will also be addressed. We will apply these concepts in a term-long software design project. Prerequisite: Computer Science 117 or consent of the instructor. 6 cr., MS, Fall,Winter,SpringStaff

CS 177. Mathematics of Computer Science An introduction to some of the mathematical tools crucial to computer science. Topics include logic and proofs; sets, relations, and functions; elementary complexity theory and recurrence relations; basic probability; counting techniques; and graphs. These mathematical tools will be discussed through their application to various topics in computer science, including error-correcting codes, hashing, cryptography, computer graphics, games, and the structure of the Internet and the web. Prerequisites: Mathematics 110 or 111; Computer Science 127 or concurrent registration in Computer Science 127. 6 cr., MS, FallD. Liben-Nowell

CS 207. Computer Organization and Architecture The design and organization of hardware and software. Topics include data representation, digital logic, micro-processor architecture, micro-programming, assembly languages, memory hierarchies, caches, RISC architectures and pipelining. Prerequisite: Computer Science 127 or consent of the instructor. 6 cr., MS, FallJ. Ondich

CS 217. Programming Languages Are there other types of programming languages besides object-oriented ones? This course will survey a number of different programming paradigms in order to do a comparative analysis of features and design. Students will gain experience programming in a variety of programming languages, including functional and logical languages such as Scheme and Prolog. Furthermore, the course will examine such topics in programming language construction as syntax and semantics, mechanisms for parameter passing, typing, scoping, and control structures. Prerequisite: Computer Science 127 or consent of the instructor. 6 cr., MS, WinterD. Musicant

CS 227. Algorithms How to think of good solution methods for solving computational problems and how to find the best methods and prove that they are the best. We'll consider the design and analysis of algorithms: divide and conquer, dynamic programming, greedy method, backtracking, branch-and-bound, and inductive approaches; recurrence relations, applications, complexity theory, NP-completeness. Prerequisites: Computer Science 127; Computer Science 177 or Mathematics 236; Mathematics 121. 6 cr., MS, WinterD. Liben-Nowell

CS 237. Theory of Computation All about computing machines: abstract automata, especially finite state machines, push-down automata, and Turing machines. Formal languages, especially context-free languages. The relationship between automata and languages. Computability and solvability. Prerequisites: Computer Science 127; Computer Science 177 or Mathematics 236 or consent of the instructor. 6 cr., MS, SpringD. Liben-Nowell

CS 257. Software Design Writing good software is difficult. In this course, we will study techniques, tools, and habits that greatly improve your chances of writing software well. Centering around several medium-sized programming projects, this course will investigate code construction techniques, debugging and profiling tools, testing methodologies, UML, principles of object-oriented design, design patterns, and user interface design. Prerequisite: Computer Science 127 or consent of the instructor. 6 cr., MS, SpringJ. Ondich

CS 307. Operating Systems Introduction to the design and construction of operating systems. Sequential and concurrent processes, synchronization and mutual exclusion, memory management techniques, file systems design, security and protection systems, CPU scheduling, input/output device handling, and distributed operating systems. Prerequisite: Computer Science 207 or consent of the instructor. 6 cr., MS, Offered in alternate years. Not offered in 2006-2007.

CS 317. Computer Graphics The raster graphics representation of 2- and 3- dimensional images. Topics include frame buffers, data structures for image storage, geometric transformations, hidden surface algorithms, raytracing, splines, and lighting models. Prerequisites: Computer Science 127, Mathematics 232 or consent of the instructor. 6 cr., MS, Offered in alternate years. Not offered in 2006-2007.

CS 327. Artificial Intelligence How can we design computer systems with behavior that seems "intelligent?" This course will examine a number of different approaches to this question, including intelligent agents (simulated with a robot), machine learning (including neural networks and genetic algorithms), and reasoning with uncertainty. We will also examine search methods, with an interest in computer game playing. The coursework is a mix of problem solving and computer programming based on the ideas that we discuss. Prerequisite: Computer Science 127 or consent of the instructor. 6 cr., MS, FallD. Musicant

CS 337. Computer Networks From the hotspots in coffee shops to the Internet in our homes, computer networking has increasingly pervaded our everyday lives. In this course, we'll study the technical details of computer networks, from local-area to wide-area networks, from the individual connections between machines to networked applications both new and old. Topics include the TCP/IP protocol stack, the OSI reference model, network architecture, protocols and their implementations, routing security, the structure of the Internet, DNS, and emerging applications such as VoIP and peer-to-peer networking. Prerequisite: Computer Science 207 or consent of the instructor. 6 cr., MS, Offered in alternate years. Not offered in 2006-2007.

CS 347. Database Systems Database systems are used in almost every aspect of computing, from storing data for websites to maintaining financial information for large corporations. Intrinsically, what is a database system and how does it work? This course takes a two-pronged approach to studying database systems. From a systems perspective, we will look at the low-level details of how a database system works internally, studying such topics as file organization, indexing, sorting techniques, and query optimization. From a theory perspective, we will examine the fundamental ideas behind database systems, such as normal forms and relational algebra. Prerequisite: Computer Science 127 or consent of the instructor. 6 cr., MS, Offered in alternate years. Not offered in 2006-2007.

CS 357. Natural Language Processing Computers are poor conversationalists, despite decades of attempts to change that fact. This course will provide an overview of the computational techniques developed in the attempt to enable computers to interpret and respond appropriately to ideas expressed using natural languages (such as English or French) as opposed to formal languages (such as C++ or Lisp). Topics in this course will include parsing, semantic analysis, machine translation, dialogue systems, and statistical methods in speech recognition. Prerequisites: Computer Science 127 or permission of the instructor. 6 cr., MS, SpringJ. Ondich

CS 377. Data Mining How does Google understand what it is you're looking for? How does figure out what items you might want to buy? These questions and others are part of machine learning and data mining, two highly related fields at the crossroads of artificial intelligence, database systems, and statistics. Machine learning concerns itself with getting a computer to learn or discover patterns, whereas data mining focuses this task on large databases. Much of the material will be presented through primary source research papers, and the content will include techniques such as classification, clustering, association rules, web mining, collaborative filtering, and others. Prerequisite: Computer Science 127 or consent of the instructor. 6 cr., MS, WinterD. Musicant

CS 395. Computational Aspects of Economics Consider a network where there is a cost for using each link. Suppose we compute the cheapest path connecting a source to a destination, and, for every link L used in the path, pay L's owner some profit plus L's cost. What happens if L's owner is in charge of reporting the cost of L? Can we design "incentive-compatible" algorithms so link owners have no reason to lie about their costs? Topics include this interplay between computer science and economics, the "price of anarchy", and algorithms to compute optimal strategies for competing individuals. Game theory will be a focus throughout. Prerequisites: Programming experience roughly equivalent to Computer Science 117, plus at least one of the following: Computer Science 177, Mathematics 232, or Economics 111. These prerequisites reflect an approximate desired level of familiarity with the course material, and there is considerable flexibility for students with other background; contact the instructor for permission. 6 cr., MS, SpringD. Liben-Nowell

CS 400. Integrative Exercise Senior Computer Science majors work in teams (typically four to seven students per team) on faculty-specified topics. Required of all senior majors. Prerequisite: Senior standing, Mathematics 121, Computer Science 117, 127, 177 (or Mathematics 236); three courses from among Computer Science 207, 217, 227, 237; one course from among Computer Science courses numbered 247 or above or Mathematics 311. 6 cr., S/NC, ND, Fall,WinterStaff

Other Courses Pertinent to the Computer Science:

Physics 247 Digital Electronics

Physics 343 Electronics