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

Computer Science (CS)

Chair: Associate Professor David R. Musicant

Professors: Jack Goldfeather, Jeffrey R. Ondich

Associate Professor: David R. Musicant

Assistant Professors: Amy Csizmar Dalal, David Liben-Nowell

Computer Science studies the computational structures and processes that appear throughout the natural and human worlds. The study of those processes (known as algorithms) can lend insight into the functioning of our brains, the structure of our genes, the mechanisms by which people form communities, and many other questions in a wide range of disciplines. At the same time, an understanding of algorithms and the structure of data can help us create a tremendous variety of useful software tools. Carleton’s computer science curriculum is designed to provide students with a balance between theoretical study and the practical application of theory to the design and construction of software.

Since computer science plays a key role in our world, we recommend Introduction to Computer Science (CS 111) for all Carleton students. We also offer introductory-level courses on specific topics, such as Life in the Age of Networks (CS 108).

Those who choose to major in computer science find many opportunities following graduation. Carleton Computer Science graduates who pursue employment in the computing industry find jobs in a many different roles and at a wide variety of companies. In addition to graduate programs in computer science, Carleton CS majors seeking further education have pursued graduate study in areas such as bioinformatics, linguistics, cognitive science, and law.

Requirements for a Major

The course requirements are Mathematics 111; Computer Science 111, 201, 202, 204, 208, 251, 252, and 254; and two additional courses from among: Computer Science courses numbered 200 or above, Mathematics 311, and Physics 247. Although they are not required for the CS major, we recommend that our students take as many mathematics and statistics courses as possible. In addition, each CS 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 111, Mathematics 111, and at least one of Computer Science 201, 202, 204, and 208 by the end of the sophomore year.

Students contemplating graduate study in computer science should consider taking additional courses in both mathematics (ideally the full Calculus sequence plus Mathematics 215 and 232) and computer science. Those interested in computer engineering should consider taking physics courses through Electricity and Magnetism and Electronics.

A guide for majors is available on the Computer Science Web site.

Computer Science Courses

CS 108. Life in the Age of Networks This course investigates how the social, technological, and natural worlds are connected, and how the study of networks sheds light on these connections. A network is a collection of entities linked by some relationship: people connected by friendships (e.g. Facebook); web pages connected by hyperlinks; species connected by the predator-prey relationships. We will emphasize the efficient synthesis and processing of large amounts of data in asking questions about networks in a variety of fields. Topics include: how Google works; "six degrees of separation"; species extinction; the spread of fads through society. No background in computer science or programming is required or expected. No prerequisites. Students who have received credit for Computer Science 111 or above are not eligible to enroll in Computer Science 108. 6 cr., MS, Offered in alternate years. FallD. Liben-Nowell

CS 111. Introduction to Computer Science This course will introduce you to computer programming and the design of algorithms. By writing programs to solve problems in areas such as image processing, text processing, and simple games, you will learn about recursive and iterative algorithms, complexity analysis, graphics, data representation, software engineering, and object-oriented design. No previous programming experience is necessary. Students who have received credit for Computer Science 201 or above are not eligible to enroll in Computer Science 111. No prerequisites. 6 cr., MS, Fall,Winter,SpringStaff

CS 201. Data Structures Think back to your favorite assignment from Introduction to Computer Science. Did you ever get the feeling that "there has to be a better/smarter way to do this problem?" The Data Structures course is all about how to store information intelligently and access it efficiently. How can Google take your query, compare it to billions of web pages, and return the answer in less than one second? How can one store information so as to balance the competing needs for fast data retrieval and fast data modification? To help us answer questions like these, we will analyze and implement stacks, queues, trees, linked lists, graphs and hash tables. Students who have received credit for a course for which Computer Science 201 is a prerequisite are not eligible to enroll in Computer Science 201. Prerequisite: Computer Science 111 or consent of the instructor. 6 cr., MS, Fall,Winter,SpringStaff

CS 202. 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 111; Computer Science 111. 6 cr., MS, Fall,SpringD. Liben-Nowell

CS 204. Software Design It’s easy to write a mediocre computer program, and lots of people do it. Good programs are quite a bit harder to write, and are correspondingly less common. In this course, we will study techniques, tools, and habits that will improve your chances of writing good software. While working on several medium-sized programming projects, we 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 111 or consent of the instructor. 6 cr., MS, WinterJ. Ondich

CS 208. Computer Organization and Architecture Computer processors are extraordinarily complex systems. The fact that they work at all, let alone as reliably as they do, is a monumental achievement of human collaboration. In this course, we will study the structure of computer processors, with attention to digital logic, assembly language, performance evaluation, computer arithmetic, data paths and control, pipelining, and memory hierarchies. Prerequisites: Computer Science 111 or consent of the instructor. 6 cr., MS, FallA. Csizmar Dalal

CS 231. Computer and Network Security Hackers, phishers, and spammers---at best they annoy us, at worst they disrupt communication systems, steal identities, bring down corporations, and compromise sensitive systems. In this course, we'll study various aspects of computer and network security, focusing mainly on the technical aspects as well as the social and cultural costs of providing (or not providing) security. Topics include cryptography, authentication and identification schemes, intrusion detection, viruses and worms, spam prevention, firewalls, denial of service, electronic commerce, privacy, and usability. Prerequisite: Computer Science 201, 202 or 204 or 208. 6 cr., MS, Not offered in 2009-2010.

CS 251. 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 201 or consent of the instructor. 6 cr., MS, FallD. Musicant

CS 252. Algorithms A course on techniques used in the design and analysis of efficient algorithms. We will cover several major algorithmic design paradigms (greedy algorithms, dynamic programming, divide and conquer, and network flow); applications of those techniques to a variety of domains (natural language processing, economics, computational biology, and data mining, for example); and computational complexity, particularly NP-completeness, including how to cope algorithmically when confronted with intractable problems. Prerequisites: Computer Science 201; Mathematics 111; Computer Science 202 or Mathematics 236. 6 cr., MS, WinterD. Liben-Nowell

CS 254. Automata and Computability An introduction to the theory of computation, emphasizing an understanding of what problems can and cannot be solved by computers. Topics include formal models of computation, including finite-state automata, pushdown automata, and Turing machines; formal languages, including regular expressions and context-free grammars; and computability and uncomputability. Time permitting, we will discuss computational and mathematical applications, like parsing and Godel's incompleteness theorem. Prerequisites: Computer Science 201; Computer Science 202 or Mathematics 236. 6 cr., MS, SpringJ. Ondich

CS 311. 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 201, Mathematics 232 or consent of the instructor. 6 cr., MS, Offered in alternate years. Not offered in 2009-2010.

CS 321. 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 201 or consent of the instructor. 6 cr., MS, Offered in alternate years. SpringD. Musicant

CS 322. 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 201 and 202 or permission of the instructor. 6 cr., MS, Offered in alternate years. Not offered in 2009-2010.

CS 324. 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 201 or consent of the instructor. 6 cr., MS, Offered in alternate years. Not offered in 2009-2010.

CS 331. 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 208 or consent of the instructor. 6 cr., MS, Offered in alternate years. FallA. Csizmar-Dalal

CS 332. Operating Systems The thing that we call a computer is actually a complex collection of interacting devices. To ensure that these devices work together effectively without excessive human intervention, people have developed operating systems software that coordinates the behavior of the devices and gives programmers ways to control those devices. This course will address the fundamental problems that operating systems need to solve, including those concerned with process management, file organization, memory management, and input/output control. We will also study the structure of the Linux operating system. Prerequisites: Computer Science 208 or consent of the instructor. 6 cr., MS, Offered in alternate years. SpringJ. Ondich

CS 334. 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 201 (127) or consent of the instructor. 6 cr., MS, Offered in alternate years. WinterD. Musicant

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 111, 201, 202 (or Mathematics 236); one course from among Computer Science 204 or 208; two courses from among Computer Science 251, 252 and 254; one course from among Computer Science courses numbered 260 or above or Mathematics 311. 6 cr., S/NC, ND, Fall,WinterStaff

Other Courses Pertinent to Computer Science:

Physics 247 Digital Electronics

Physics 343 Electronics