2014-2015 Computer Science Courses
First-Year Studies: Privacy vs. Security in a Networked World
The Internet was developed at the height of the Cold War as a way to maintain a robust communication system in the event of a nuclear attack. It is ironic, then, that the same technology may put us at risk of 21st-century security threats such as electronic surveillance, aggregation and mining of personal information, and cyberterrorism. In this seminar, we contrast doomsday myths popularized by movies such as War Games with more mundane scenarios such as total disruption of electronic commerce. Along the way, we address questions such as: Does modern technology allow people to communicate secretly and anonymously? Can a few individuals disable the entire Internet? Can hackers launch missiles or uncover blueprints for nuclear power plants from remote computers on the other side of the world? We will also investigate other computer security issues, including spam, computer viruses, and identity theft. Meanwhile, with our reliance on cell phones, text messages, and electronic mail, have we unwittingly signed ourselves up to live in an Orwellian society? Or can other technologies keep “1984” at bay? Our goal is to investigate if and how society can strike a balance so as to achieve computer security without substantially curtailing rights to free speech and privacy. Along the way, we will introduce the science of networks and describe the underlying theories that make the Internet at once tremendously successful and so challenging to regulate. Part of the course will be devoted to learning cryptology—the science (and art) of encoding and decoding information to enable private communication. We will conclude with a discussion of how cutting-edge technologies, such as quantum cryptography and quantum computing, may impact the privacy of electronic communications in the near future. We will hold several informal debates on current topics, such as whether Edward Snowden should be viewed as a hero or a traitor, the ethics of Wikileaks and Anonymous, and whether law-enforcement officials should be required to obtain warrants before examining smartphones.
The Computational Beauty of Nature
This course will explore the concepts of emergence and complexity within natural and artificial systems. Simple computational rules interacting in complex, nonlinear ways can produce rich and unexpected patterns of behavior and may account for much of what we think of as beautiful or interesting in the world. Taking this as our theme, we will investigate a multitude of topics, including fractals and the Mandelbrot set, chaos theory and strange attractors, cellular automata such as Wolfram's elementary automata and Conway's Game of Life, self-organizing and emergent systems, formal models of computation such as Turing machines, artificial neural networks, genetic algorithms, and artificial life. The central questions motivating our study will be: How does complexity arise in nature? Can complexity be quantified and objectively measured? Can we capture the patterns of nature as computational rules in a computer program? What is the essence of computation, and what are its limits? Throughout the course, we will emphasize computer experimentation rather than programming, using the computer as a laboratory in which to design and run simulations of complex systems and observe their behaviors.
Introduction to Computer Science: The Way of the Program
This course is an introduction to computer science and the art of computer programming using the elegant, yet easy-to-learn, programming language Python. Students will learn the principles of problem solving with a computer while gaining the programming skills necessary for further study in the discipline. Throughout the course, we will emphasize the power of abstraction and the benefits of clearly written, well-structured programs. We will begin with basic procedural programming and work our way up to object-oriented concepts such as classes, methods, and inheritance. Along the way, we will explore the fundamental concepts of algorithms and their efficiency, binary representations of data, digital logic, and recursion. Other topics include introductory computer graphics, file processing, sorting and searching algorithms, basic data structures such as lists, dictionaries, and binary trees, and some principles of game design and implementation. Weekly laboratory sessions will reinforce the concepts covered in class through extensive hands-on practice at the computer.
Physicists and philosophers have been trying to understand the strangeness of the subatomic world as revealed by quantum theory since its inception back in the 1920s; but it wasn't until the 1980s—more than a half-century after the development of the theory—that computer scientists first began to suspect that quantum physics might hold profound implications for computing, as well, and that its inherent weirdness might possibly be transformed into a source of immense computational power. This dawning realization was followed soon afterward by key theoretical and practical advances, including the discovery of several important algorithms for quantum computers that could potentially revolutionize (and disrupt) the cryptographic systems protecting practically all of our society’s electronic banking, commerce, telecommunications, and national security systems. Around the same time, researchers succeeded in building the first working quantum computers, albeit on a very small scale. Today, the multidisciplinary field of quantum computing lies at the intersection of computer science, mathematics, physics, and engineering and is one of the most active and fascinating areas in science—with potentially far-reaching consequences for the future. This course will introduce students to the theory and applications of quantum computing from the perspective of computer science. Topics to be covered will include bits and qubits, quantum logic gates and reversible computing, Deutsch’s algorithm, Grover's search algorithm, Shor’s factoring algorithm, and applications to cryptography. No advanced background in physics, mathematics, or computer programming is necessary beyond a basic familiarity with linear algebra. We will study the quantitative, mathematical theory of quantum computing in detail but will also consider broader philosophical questions about the nature of physical reality, as well as the future of computing technologies. Prerequisite: one semester of linear algebra or equivalent mathematical preparation.
Compilers: How Computers Execute Their Programs
Compilers are often known as translators—and for good reason: Their job is to take programs written in one language and translate them to another language (usually assembly or machine language) that a computer can execute. It is perhaps the ideal meeting between the theoretical and practical sides of computer science. Modern compiler implementation offers a synthesis of: (1) language theory: how languages (both natural languages and programming languages) can be represented on, and recognized by, a computer; (2) software design and development: how practical software can be developed in a modular way—e.g., how components of one compiler can be connected to components of another compiler to form a new compiler; and (3) computer architecture: understanding how modern computers work. During the semester, we will write a program implementing a nontrivial compiler for a novel programming language (partly of our own design). Topics we will cover along the way include the difference between interpreters and compilers, regular expressions and finite automata, context-free grammars and the Chomsky hierarchy, type checking and type inference, contrasts between syntax and semantics, and graph coloring as applied to register allocation. Conference work will allow students to pursue different aspects of compilers such as compilation of object-oriented languages, automatic garbage collection, compiler optimizations, and applications of compiler technology to natural-language translation. Permission of the instructor is required. Students should have already taken at least one semester of computer programming (C, C++, or Java) and, preferably, a course in computer architecture.
Bio-Inspired Artificial Intelligence
The field of artificial intelligence (AI) is concerned with reproducing the abilities of human intelligence in computers. In recent years, exciting new approaches to AI have been developed, inspired by a wide variety of biological structures and processes that are capable of self-organization, adaptation, and learning. Examples of these new approaches include evolutionary computation, artificial neural networks, autonomous robots, and swarm intelligence. This course will provide a hands-on introduction to the algorithms and techniques of biologically-inspired AI, focusing primarily on evolutionary systems, neural networks, and robotics from both a theoretical and practical standpoint. Topics to be covered include genetic algorithms, genetic programming, supervised and unsupervised neural network learning, reinforcement learning, reactive- and behavior-based robot control, evolutionary robotics, and developmental robotics. Throughout the course, we will use the Python programming language to implement and experiment with these techniques in detail and to test them on both real and simulated robots. Students will have many opportunities for extended exploration through open-ended lab exercises and conference work. No previous knowledge of Python or robot hardware is needed, but students should be comfortable programming in a high-level, object-oriented language such as Java or C++.
Collaborative Software Development
Donald E. Knuth, one of the world’s most distinguished computer scientists, has said both that “computer programs are fun to write” and “software is hard.” The goal of this course is to give students a taste of what it is like to design and develop real software. The quotes by Knuth illustrate two themes of this course that are not necessarily at odds: The challenge of writing good software should not offset the pleasure derived from writing it. Some of the main topics that we will cover include: the power of abstraction, the separation of design from implementation, version control, the selection of development environments, the creative use of existing software libraries and tools, the benefits of a flexible approach, the role of maintaining good documentation, and, most importantly, how to write software in teams. No place is the adage “there is no substitute for experience” more relevant than in software engineering. With that in mind, this course is intended to be hands-on. Design and development techniques will be taught primarily by designing and developing a semester-long, collaborative software project. Examples of project categories include (but are not limited to) digital games and mobile applications. Specific topics include: design patterns, including Model-View-Controller; separating user-interface particulars from core algorithms; wireframe techniques; alpha vs. beta testing; using distributed, collaborative software versioning tools such as github; the role of abstract data types and precise API specification; code reviews; workshopping; the less heralded but crucially important roles of documentation writers, software testers, and project managers. Permission of the instructor is required. Students should have studied at least one semester of computer programming. Preference will be given to seniors who apply as a team, in advance, with a concrete proposal.