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.
Restricted to Amherst College students. Limited to 40 students per class (20 per lab). In the Fall, 25 seats per class are reserved for first-year students. Fall and spring semesters. The Department.2020-21: Offered in Fall 2020, Spring 2021
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 stacks, queues, linked lists, programming for graphical user interfaces, and basic topics in probability. A laboratory section will meet once a week to give students practice with programming constructs.
Requisite: COSC 111 or consent of the instructor. Fall semester: Professor Alfeld. Spring semester: The Department.2020-21: Offered in Fall 2020, January 2021, Spring 2021
This course will examine the principles and design choices involved in creating general purpose computer systems. Topics will include instruction set architectures, virtual memory, caching, allocators and garbage collectors, threads and synchronization, file systems, virtual machines, and distributed systems. Projects will involve the implementation and use of these capabilities and abstractions. Students who have taken COSC 161 may also take this course. Students who have taken COSC 261 may not take this course.
Requisite: COSC 112. Fall semester. Professor Kaplan.2020-21: Offered in Fall 2020
A fundamental problem in computer science is that of organizing data so that it can be used effectively. This course introduces basic data structures and their applications. Major themes are the importance of abstraction in program design and the separation of specification and implementation. Program correctness and algorithm complexity are also considered. Data structures for lists, stacks, queues, dictionaries, sets, and graphs are discussed. This course will provide advanced programming experience. It is not open to students who have previously taken COSC 201.
Requisite: COSC 111. Spring semester. Professor Gardner.2020-21: Offered in Fall 2020, Spring 2021
Probability is everywhere in computer science. In networks and systems, it is a key tool that allows us to predict performance, to understand how delay changes with the system parameters, and more. In algorithms, randomization is used to design faster and simpler algorithms than their deterministic counterparts. In machine learning, probability is central to the underlying theory. This course provides an introduction to probability with a focus on computer science applications. We will discuss elementary probability theory, including topics such as discrete and continuous random variables and distributions and Markov chains, and settings in which these are used in computer science (e.g., modeling real-world workload distributions, analyzing computer system performance, and designing and analyzing randomized algorithms).
Requisite: MATH 111 and COSC 112/211. Spring semester. Assistant Professor Gardner.
2020-21: Offered in Spring 2021
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. Omitted 2018-19.2020-21: Not offered
An introduction to the ideas and techniques that allow computers to perform intelligently. The course will discuss methods of adversarial game playing and of solving general problems using heuristic search. It will also discuss the design of agents that learn either from experience or from a provided dataset. The course will cover both theoretical aspects of AI and practical considerations such as noisy sensor readings. Three class meetings per week. Offered in alternate years.
Requisite: COSC 112. Omitted 2018-19.2020-21: Not offered
Machine Learning algorithms allow computers to be taught to perform tasks without being explicitly programmed. This course is an introduction to machine learning and data mining. The course will explore supervised, unsupervised, ensemble and reinforcement learning. Topics may include: decision tree learning, rule learning, neural networks, support vector machines, Bayesian learning, clustering, hidden Markov model learning, and/or deep learning. The material of this course has some overlap with that of Computer Science 241, but it is permissible to take both.
Requisite: COSC 211. Fall semester. Professor Alfeld.2020-21: Offered in Fall 2020
This course is an introduction to data mining, the area of computer science that deals with the development of efficient and accurate algorithms for extracting information from data. Topics may include: mining data streams and time series, the MapReduce/Spark model and large scale data analysis, significant patterns extraction, web and social networks analysis, recommendation systems, sampling and hypothesis testing, and dimensionality reduction. We will use interactive data analysis notebooks and large-scale data processing systems to implement and test data mining algorithms.
Requisite: COSC 211. Spring semester. Assistant Professor Riondato.2020-21: Offered in Spring 2021
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. Omitted 2018-19.2020-21: Not offered
Computing networks are ubiquitous and used for a broad range of purposes. Networks are often complex and dynamic, connecting systems with a range of capabilities. Some computers are permanently connected while others (e.g., mobile devices) routinely leave and rejoin the network. In any case, the network must ensure that data are delivered quickly and reliably from one computer to another. This course will begin with the problem of communicating between two computers, followed by the problems of building generalized networks for different types and varying numbers of computing devices. Topics will include layered network structure, signaling methods, error detection and correction, flow control, routing, and protocol design and verification. Not open to students who have previously taken Computer Science 281. Offered in alternate years.
Requisite: COSC 112 and COSC 211 or consent of the instructor. Fall semester. Professor Kaplan.2020-21: Not offered
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. Omitted 2018-19.2020-21: Not offered
This course addresses the design and analysis of computer algorithms. Topics include: set algorithms such as sorting and searching, graph algorithms, string algorithms, and matrix algorithms. Algorithm design paradigms, including the divide-and-conquer, dynamic programming, and greedy paradigms, will be emphasized. The course will end with a discussion of the theory of NP-completeness and its implications.
Requisite: COSC 112 and COSC 211. Fall semester. Professor Gardner.2020-21: Offered in Fall 2020
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 Pixar's Renderman.
Requisite: COSC 112 or 201 or consent of the instructor. Omitted 2018-19.2020-21: Offered in Fall 2020
This course examines the theory of games in all forms, including traditional non-cooperative simultaneous-play games and their relevance to economics, psychology, and biology; iterated games; combinatorial games such as chess, checkers, and Go; imperfect information games; and stochastic games. The course also considers data structures and algorithms relevant to games, the computational complexity of games, and the use of techniques from artificial intelligence to compute strategies when it is infeasible to compute the optimal strategy. Students will have an opportunity to develop games that incorporate AI and theory.
Requisites: COSC 112 and 201. Omitted 2018-19.2020-21: Not offered
This course will introduce mobile and wearable computing and smart sensing. The number of smartphone users in the world is predicted to grow to 2.5 billion in 2019. The Internet of Things, once called the "next best thing," is already here. Students will learn how to design the next-generation of efficient mobile devices and applications with the user’s interests and privacy in mind. The course will cover different aspects of mobile computing and smart sensing such as ethics, security and privacy, usability, computing in an environment with low resources, and wireless networking. Students will be expected to identify new applications of mobile computing and/or smart sensors. They will learn at least one development framework (Android, Arduino) and use it to develop their course project.
Requisite: COSC 201. Omitted 2018-19.2020-21: Not offered
The recent explosion in the volume of data being collected and curated by computer systems is making possible a new understanding of human behavior and other natural phenomena. This dramatic growth is also challenging traditional data storage and manipulation paradigms. In particular, the growth in the collection and storage of so-called “unstructured” data has precipitated the development of new database technologies. Unlike traditional relational data storage, these so-called NoSQL databases are optimized for the storage and analysis of hierarchical or otherwise non-tabular data in what are often distributed layouts. The course will explore this dramatic paradigm shift by examining the inherent limitations of traditional relational databases and how the newer class of databases proposes to address these limitations. Projects will center around experimental comparisons of relational database operations to operations implemented in the Map Reduce paradigm. Offered in alternate years.
Requisites: COSC 112 and 201. Omitted 2018-19. The Department.2020-21: Not offered
Computer systems are complex structures of multiple hardware and software components, with each component affecting the performance of every computation. To measure and improve performance requires a full understanding of how a system's components interact and the unexpected ways that changes in one component may affect others.
In this course we will develop methods for measuring computational performance that account for these complex interactions. We will optimize computations first by empirically identifying the greatest opportunities for improvement and then by evaluating those optimizations through proper measurement and analysis.
Topics will include compiler optimizations, memory hierarchy performance, probe effects, cache contention, parallel bottlenecks and scaling, and performance analysis techniques.
Requisite COSC 171 and 211. Spring semester. Professor Kaplan.2020-21: Offered in January 2021
There is an ongoing arms race between hackers and defenders in the cyber world. This course introduces concepts of computer security including exploitation, diagnosis, and protection. Topics will range from program exploits like buffer overflow attacks and privilege escalation to analysis of recent real-world attacks to discussions about the ethics of hacking. We will also cover security protocols such as those for authentication (proving that you are who you say you are), password checking, and cryptography.
Requisite: COSC 171 or consent of the instructor. Omitted 2018-19.2020-21: Not offered
Independent reading course.
Fall and spring semesters. The Department.2020-21: Offered in Spring 2021
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. The Department.2020-21: Offered in Spring 2021
Computer operating systems are responsible for allowing multiple running programs to share hardware resources. The policies that dictate how those resources are shared determine the system's ability to provide good performance, fair sharing, isolation between programs, and predictable behavior. There are many interacting policy choices that determine these properties, and measuring the effect of each requires careful empirical experimentation and analysis. Research papers will describe and analyze policies that control processor scheduling, memory allocation and caching, disk scheduling and placement, network bandwidth allocation, and power consumption. The policies may be specialized for different types of systems, such as servers and mobile devices. We will design and perform experiments to further evaluate the policies, comparing them and analyzing their behavior. Offered in alternate years.
Requisite: COSC 112, 201, and 261. Omitted 2018-19.2020-21: Not offered
Open to seniors with consent of the Department.
Fall semester. The Department.2020-21: Offered in Fall 2020