Carleton College

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, Fall—A. 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,Spring—Staff

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,Spring—Staff

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, Fall—D. 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, Fall—J. 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, Winter—D. 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, Winter—D. 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, Spring—D. 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, Spring—J. 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, Fall—D. 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, Spring—J. Ondich

CS 377. Data Mining How does Google understand what it is you're looking for? How does Amazon.com 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, Winter—D. 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, Spring—D. 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,Winter—Staff