Computer Science
Year: Show curriculum in:

Amherst College Computer Science for 2012-13

105 Demystifying the Internet

This course provides an introductory survey of topics in computer science that are related to the Internet. Students will become familiar with the history and underlying structure of the Internet and with technologies such as email, web browsers, search engines, and web page design tools. We will learn about the science behind the technology: topics to be addressed include network design and network protocols, modern encryption methods, and applications of algorithmics and artificial intelligence to the design of search engines. Some time will also be spent considering social issues such as privacy, worms and viruses, spam, cookies, and encryption policy. Three class meetings per week, with occasional in-class lab sessions. This course does not provide prerequisite credit for any computer science course, nor does it count towards the computer science major. No previous experience with computers is required.

Limited to 40 students. Spring semester. Professor C. McGeoch.

2014-15: Not offered
Other years: Offered in Fall 2008, Spring 2010, Spring 2013

111 Introduction to Computer Science I

This course introduces ideas and techniques that are fundamental to computer science. The course emphasizes procedural abstraction, algorithmic methods, and structured design techniques. Students will gain a working knowledge of a block-structured programming language and will use the language to solve a variety of problems illustrating ideas in computer science. A selection of other elementary topics will be presented, for example: the historical development of computers, comparison and evaluation of programming languages, and artificial intelligence. A laboratory section will meet once a week to give students practice with programming constructs. Two class hours and one one-hour laboratory per week.

Fall semester. Professor Kaplan.  Spring semester:  Professors Kaplan and Rager.

2014-15: Offered in Fall 2014 and Spring 2015
Other years: Offered in Fall 2007, Spring 2008, Fall 2008, Spring 2009, Fall 2009, Spring 2010, Fall 2010, Spring 2011, Fall 2011, Spring 2012, Fall 2012, Spring 2013, Fall 2013, Spring 2014

112 Introduction to Computer Science II

A continuation of COSC 111. This course will emphasize more complicated problems and their algorithmic solutions. The object-oriented programming paradigm will be discussed in detail, including data abstraction, inheritance and polymorphism. Other topics will include linked lists and trees and the use of finite-state machines in algorithm design. A laboratory section will meet once a week to give students practice with programming constructs. Two class hours and one one-hour laboratory per week.

Requisite: COSC 111 or consent of the instructor. This course is the appropriate starting point for most students with some prior programming experience.  Fall semester: Professor Rager. Spring semester: L. McGeoch.

2014-15: Offered in Fall 2014 and Spring 2015
Other years: Offered in Fall 2007, Spring 2008, Fall 2008, Spring 2009, Fall 2009, Spring 2010, Fall 2010, Spring 2011, Fall 2011, Spring 2012, Fall 2012, Spring 2013, Fall 2013, Spring 2014

161 Computer Systems I

This course will provide an introduction to computer systems, stressing how computers work. Beginning with Boolean logic and the design of combinational and sequential circuits, the course will discuss the design of computer hardware components, microprocessing and the interpretation of machine instructions, assembly languages, and basic machine architecture. The course will also introduce operating systems topics, basic memory management, and topics in network communication. Projects will include the design of digital circuits and the simulation of operating system and network processes.

This course has no requisite and no programming experience is required. Fall semester. Professor Kaplan.

2014-15: Offered in Fall 2014
Other years: Offered in Spring 2008, Fall 2008, Fall 2009, Fall 2010, Fall 2011, Fall 2012, Fall 2013

201 Data Structures and Algorithms I

This course is the first part of a two-semester sequence examining data structures (ways of organizing data so that it can be used effectively) and algorithms (the methods that can be used to manipulate data). The use of appropriate data structures and algorithms can often dramatically reduce the computational work needed to solve a problem. Topics examined in this course will include proof techniques, run-time analysis, heaps, hash tables, sorting, searching, and divide-and-conquer algorithms. The course will provide advanced programming experience and will emphasize the use of abstraction in program design.

Requisite: COSC 111. Spring semester. Professor C. McGeoch.

2014-15: Offered in Spring 2015
Other years: Offered in Fall 2007, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014

231 Programming Language Paradigms

The main purpose of a programming language is to provide a natural way to express algorithms and computational structures. The meaning of “natural” here is controversial and has produced several distinct language paradigms; furthermore the languages themselves have shaped our understanding of the nature of computation and of human thought processes. We will explore some of these paradigms and discuss the major ideas underlying language design. Several languages will be introduced to illustrate ideas developed in the course. Topics will include functional programming, declarative programming, and programming for concurrency and distributed computing. Offered in alternate years.

Requisite: COSC 112.  Fall semester.  Professor Rager.

2014-15: Offered in Spring 2015
Other years: Offered in Fall 2008, Spring 2011, Fall 2012

241 Artificial Intelligence

An introduction to the ideas and techniques that allow computers to perform intelligently. The course will discuss methods of representing knowledge and methods of solving general problems using heuristic search.  It will also discuss the design of algorithms that learn and generalize from experience.  Other topics will be chosen to reflect the interests of the class and may include: communicating in English, game playing, probabilistic reasoning, planning, vision and speech recognition, computers modeled on neurons, and the possibility and implications of the existence of non-human intelligence. Three class meetings per week. Offered in alternate years.

Requisite: COSC 112. Omitted 2012-13.

 

2014-15: Not offered

261 Computer Systems II

This course will examine the principles and design choices involved in creating the software and hardware systems on which ordinary computer programs rely. It will develop advanced topics in computer processor architecture, cover the design of operating systems and runtime systems, and provide an introduction to programming language compilers. Architectural topics will include pipelines, out-of-order execution, symmetric multithreading, and multi-core cache management. Topics in operating and runtime systems will include virtual memory, file systems, linkers and loaders, virtual machines, memory allocators, and garbage collectors. Projects will involve the implementation of key concepts and structures.

Requisite: COSC 111 and 161. Spring semester. Professor Rager.

2014-15: Offered in Spring 2015
Other years: Offered in Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014

281 Networks and Cryptography

Computing networks have fundamentally changed the ways in which we use computers. The ubiquity of networks and their broad range of uses have created substantial challenges in the area of computer communication. Not only must data be delivered quickly and reliably from one computer to another, but in many cases that data must also be secure from eavesdroppers. Moreover, the recipient of the information often needs to be sure of the identity of the sender. Encryption can be used to achieve both security and authentication of information. This course will begin with the problem of communicating between two computers, followed by the problem of building generalized networks for an arbitrary number of computers. Networking topics will include layered network structure, signaling methods, error detection and correction, flow control, routing, and protocol design and verification. We will then examine in detail a variety of encryption schemes, how they can be used, and how secure they are. Cryptographic topics will include classical cryptosystems, the data encryption standard, public-key cryptography, key escrow systems, and public policy on encryption. Offered in alternate years.

Requisite: COSC 112 or 201. Spring semester.  Professor Kaplan.

2014-15: Offered in Spring 2015
Other years: Offered in Spring 2008, Spring 2009, Fall 2010, Spring 2013

301 Data Structures and Algorithms II

This course continues the exploration of data structures and algorithms that is begun in COSC 201. Topics include balanced search trees, amortized algorithms, graph data structures and algorithms, greedy algorithms, dynamic programming algorithms, NP completeness, and case studies in algorithm design.

Requisite: COSC 112 and 201. Fall semester.  Professor L. McGeoch.

2014-15: Offered in Fall 2014
Other years: Offered in Fall 2007, Fall 2008, Fall 2009, Fall 2010, Fall 2011, Fall 2012, Fall 2013

321 Computer Graphics

This course will explore the algorithms used to create “realistic” three-dimensional computer images.  Major topics will include object representations (polygons, curved surfaces, functional models), rendering algorithms (perspective transformations, hidden-surface removal, reflectance and illumination, shadows, texturing), and implementation techniques (scan conversion, ray tracing, radiosity).  Students will create images using OpenGl and Pixar's Renderman.

Requisite: COSC 112 or 201 or consent of the instructor.  Omitted 2012-13.

2014-15: Not offered

338H Mobile Computing

In the last decade, smartphones, tablets, and other mobile devices have transformed our society by offering easy and continuous access to information and high-speed computation. The focus on mobile computing has raised new questions in the areas of networking, security, and hardware.  Even the process of programming has shifted, with the creation of mobile "apps" requiring increased attention to design, robustness, and efficiency.

This half-credit course explores the opportunities and challenges of mobile computing, with an emphasis on programming for mobile devices.  Students will complete projects in the iOS and Android environments.

Requisite: COSC 112.  Limited to 12 students.  Fall semester.  Professors Kaplan and L. McGeoch.

2014-15: Not offered
Other years: Offered in Fall 2012

341 Applied Algorithms

We will look at recent advances in the design and analysis of data structures and algorithms, with an emphasis on real-world applications.  Topics to be covered include approximation algorithms and heuristics for NP-hard problems; combinatorial optimization; new analysis techniques; and methods of algorithm engineering and experimental analysis of algorithms.  The specific problem domains to be studied will vary from year to year, to reflect the state of the art in algorithm research.  Students will read and present research papers and carry out small research projects to evaluate algorithm performance in realistic scenarios.

Requisite: COSC 201.  Omitted 2012-13.

2014-15: Not offered

371 Compiler Design

An introduction to the principles of the design of compilers, which are translators that convert programs from a source language to a target language. Some compilers take programs written in a general-purpose programming language, such as C, and produce equivalent assembly language programs. Other compilers handle specialized languages. For instance, text processors translate input text into low-level printing commands. This course examines techniques and principles that can be applied to the design of any compiler. Formal language theory (concerning regular sets and context-free grammars) is applied to solve the practical problem of analyzing source programs.

Topics include: lexical analysis, syntactic analysis (parsing), semantic analysis, translation, symbol tables, run-time environments, code generation, optimization, and error handling. Each student will design and implement a compiler for a small language. Offered in alternate years.

Requisite: COSC 112 and 161. Omitted 2012-13.

2014-15: Not offered

390, 490 Special Topics

Independent reading.

Fall and spring semesters.

2014-15: Offered in Fall 2014 and Spring 2015
Other years: Offered in Fall 2009, Fall 2010, Fall 2011, Spring 2012, Fall 2012, Spring 2013, Fall 2013, Spring 2014

401 Theoretical Foundations of Computer Science

This course covers basic mathematical concepts that are essential in computer science, and then uses them to teach the theory of formal languages and machine models of languages. The notion of computability will be introduced in order to discuss undecidable problems. The topics covered include: regular, context-free and context-sensitive languages, finite state automata, Turing machines, decidability, and computational complexity. Offered in alternate years.

Requisite: None, although analytical aptitude is essential. Spring semester.  Professor L. McGeoch.

2014-15: Offered in Spring 2015
Other years: Offered in Spring 2009, Fall 2010, Spring 2013

450 Seminar in Computer Science

The topic changes from year to year.  The topic for fall 2012 is "Combinatorial Optimization Algorithms."  We will examine algorithms for a range of optimization problems, including linear programming, matching, computation of network flows, and integer programming.  Many of the algorithms are both surprising and efficient. Topics will include the simplex algorithm, duality, primal-dual algorithms, and cutting-plane algorithms.

Requisite: COSC 121 and 201.  Fall semester.  Professor L. McGeoch.

2014-15: Offered in Fall 2014
Other years: Offered in Fall 2008, Spring 2011, Fall 2012

461 Advanced Operating Systems

Computer operating systems are responsible for allowing multiple users and their programs to share the hardware resources of a single machine. The policies implemented in an operating system determine its ability to provide good performance, fair sharing, isolation between programs, and predictable behavior. There are many policy choices that determine these properties, and measuring their effect requires empirical experimentation and analysis.

This course will examine both basic and advanced policies that can be used to control process scheduling, memory management, disk scheduling, network bandwidth allocation, and power consumption. We will design and perform experiments to evaluate these policies, comparing them and analyzing their behavior. Experiments will involve both simulation and in-kernel implementation. Offered in alternate years.

Requisite: COSC 261 and either COSC 112 or 201.  Omitted 2012-13.

2014-15: Not offered

498, 499 Senior Departmental Honors

Open to seniors with consent of the Department.

Fall semester. The Department.

2014-15: Offered in Fall 2014
Other years: Offered in Fall 2009, Fall 2010, Fall 2011, Fall 2012, Fall 2013