2012-2013 Computer Science Courses

Though science has continued to reveal, with increasing precision, the ways in which patterns of matter and energy arrange themselves into life, the mind has largely eluded physical explanation. How does thinking arise from brain cells, and how can thought control the body? Researchers in artificial intelligence (AI) believe that the best way to understand the mind is to reproduce it in a machine. They have been exploring ways to program computers to behave intelligently since the middle of the last century. How far has the field of AI come since then, and what are its prospects for the future? In this course, we will examine in detail the major paradigms of AI research, from symbolic approaches such as knowledge representation, propositional and predicate logic, and search methodologies to more recent approaches that focus on adaptation and learning, such as neural networks, genetic algorithms, artificial life, and robotics. We will also investigate the idea of swarm intelligence and machine creativity and consider some important philosophical questions surrounding AI, including consciousness, the mind-body problem, and the Turing Test.

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.

This course explores the principles of programming language design through the study and implementation of interpreters, which are computer programs that process other programs as input. A famous computer scientist once remarked that if you don't understand interpreters, you can still write programs—and you can even be a competent programmer—but you can't be a master. We will begin by studying functional programming using the strangely beautiful and recursive programming language Scheme. After getting comfortable with Scheme and recursion, we will see how to design our own languages by starting from a high-level description and systematically deriving a low-level implementation through the application of a series of program transformations. Along the way, we will become acquainted with the lambda calculus (the basis of modern programming language theory), scoping mechanisms, continuations, lazy and nondeterministic evaluation, and other topics if time permits. We will use Scheme as our “meta-language” for exploring these issues in a precise, analytical way, similar to the way in which mathematics is used to describe phenomena in the natural sciences. Our great advantage over mathematics, however, is that we can test out our ideas about languages, expressed in the form of interpreters, by directly executing them on the computer. Permission of the instructor is required. No prior knowledge of Scheme is needed, but at least one semester of prior programming experience is expected.

From social networking via the iPhone, Facebook, and Twitter to massively multiplayer online games, computer technology plays an ever-increasing role in our daily lives. Where may this phenomenon be taking us in the immediate (and not-so-immediate) future? Is there (or should there be) anything we can (or should) do about it? The miniaturization of electronic computers and the resulting increase in computing power, decrease in short-term cost to harness that power, and ubiquity of computer networks brings people and places together, making distances formerly thought of as insurmountable evermore trivial. With the advent of gigabit fiber-optic networks, smart phones, flip cameras, and RFID tags, information of all kinds (text, voice, images, movies, and more) can flow around the world—between people and objects and back again—in an instant. In this course, we will consider how information can be represented using bits on digital computers and how it can be communicated accurately, efficiently, and “automatically” on the Internet. We will consider some historical context: How does the rise of the Internet compare with the development of the printing press, the telegraph, radio, and television? We will focus on the evolution (or, some would say, revolution) in new media and how that leads to what journalist Bob Garfield refers to as the “Chaos Scenario”: the Internet's effect on traditional media (newspapers, magazines, books, radio, television, film, quaint objects known as “records,” you name it) and marketing as it all migrates online. In many ways, the plethora of smaller, cheaper, faster networked devices improves our quality of life. But we will also consider the dark side of a highly connected society: the more smart phones, the more workaholics; the more cellphone calls, text messages, and e-mails exchanged, the less privacy; the more iPads, the more music and video piracy; and the greater reach of the Internet, the greater the distribution of spam, pornography, and the likelihood of cyberterrorism. To tie many of these themes together, we will read some dystopian cyberpunk fiction that may make your hair (virtual or otherwise) stand on end. This is not a technical course, though at times we will discuss some details that lie behind certain crucial technologies; in particular, the Internet and the World Wide Web.

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, artificial neural networks, genetic algorithms and artificial life, Turing machines, and quantum computation. 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.

This course is a journey analogous to space exploration. Our infinite cosmos will be the set of natural numbers. Our exploratory rocket ships will be computer programs of our own design. The planets possibly bearing alien life forms are different classes of prime numbers.

More literally, this course is a research driven introduction to elementary number theory and its application to computer-network security. We will write a series of computer programs of increasing sophistication whose aim will be to identify patterns among prime numbers. In some cases we will search for empirical evidence in support of well established theories (for example, the Prime Number Theorem), in other cases we will be analyzing and interpreting data in an effort to discover new theorems and their applications (for example, regarding "safe primes").

We will pose philosophical questions regarding the nature of modern mathematics (and, therefore, computer science). For instance, to what extent can a computer be used to prove theorems? Is there a fundamental difference between theorems that seems to require "insight" for their proof (for example, using a non-constructive proof by contradiction to establish the infinitude of primes) as opposed to those that correspond to more algorithmic arguments?

We will investigate what it means to be random. Can randomness be generated by an algorithmic process? We will see examples of how some problems that appear the be very difficult may be solved quickly using random numbers with the caveat that the answer we get is only "probably" true. We discuss the philosophical and practical implications of this approach. In particular, we will contrast on the one hand, the ease with which random numbers can be harnessed to discover primes, and on the other, the challenge of finding divisors of composite numbers. We will also consider the Web-shaking implications if the latter problem turns out to be less difficult than it appears.

Topics in elementary number-theory include: unique factorization, modular arithmetic, Euler's phi function, Fermat's Little Theorem, primitive roots, quadratic residues and Gauss' Law of Quadratic Reciprocity. Cryptology topics include: Diffie-Hellman key exchange, RSA encryption, El Gamal signatures, pseudorandom number generators, zero-knowledge proofs, and applications of these to electronic voting and digital currency. Algorithmic topics include: modular exponentiation, probabilistic prime testing, factorization and discrete logarithms, and the theory of NP-completeness.

There is no one single prerequisite for this course, but students should have either at least one semester of programming experience (preferably in Python; but C, C++, or Java should be fine) or some experience with mathematical proof (for example, one semester of college-level mathematics such as Discrete Mathematics). Cross listed with Mathematics. Intermediate, permission of instructor required.

A modern database system is a collection of interrelated facts recorded on digital media and a set of computer programs to access those facts. In the 21st century, databases have become ubiquitous via the Web and “cloud computing” to the point that users may not even realize where their data is stored, how it is accessed, and who has access to it. This course attempts to shed light on why and how our society has become so dependent on information-processing by examining software (and, to a lesser extent, hardware) techniques that lead to the efficient storage and retrieval of information. We will illustrate these principles by designing databases using open-source platforms (such as MySQL) and by designing Web sites to manipulate those databases using client-side technologies (such as HTML, CSS, Javascript and AJAX) and server-side programming languages (such as PHP and Python). Major topics include relational database design, query languages (such as SQL, XQuery and XSLT), the object-relational model, ACID properties, and the client-server paradigm. Each student will be responsible for designing and implementing a Web-accessible database application of her or his choosing, using open-source database software and a Web-application programming language such as PHP, Python, or Ruby. Students will work on their projects throughout the course and will demonstrate them to the rest of the class at the close of the semester. We will also consider Web-application frameworks such as Ruby on Rails and Django. In addition to regular reading assignments, there will be several problem sets and short programming assignments. There will also be a more substantial programming assignment used to illustrate issues pertaining to the practical implementation of database systems. Suggested conference topics include data mining, database privacy, geographical information systems (GIS), and the implementation of a miniature database system. Permission of the instructor is required. Students should be familiar with the basics of HTML and have at least one semester of programming experience.

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 out on both real and simulated robots. Students will have many opportunities for extended exploration through open-ended laboratory 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++.

Though science has continued to reveal, with increasing precision, the ways in which patterns of matter and energy arrange themselves into life, the mind has largely eluded physical explanation. How does thinking arise from brain cells, and how can thought control the body? Researchers in artificial intelligence (AI) believe that the best way to understand the mind is to reproduce it in a machine. They have been exploring ways to program computers to behave intelligently since the middle of the last century. How far has the field of AI come since then, and what are its prospects for the future? In this course, we will examine in detail the major paradigms of AI research, from symbolic approaches such as knowledge representation, propositional and predicate logic, and search methodologies to more recent approaches that focus on adaptation and learning, such as neural networks, genetic algorithms, artificial life, and robotics. We will also investigate the idea of swarm intelligence and machine creativity and consider some important philosophical questions surrounding AI, including consciousness, the mind-body problem, and the Turing Test.

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.

This course explores the principles of programming language design through the study and implementation of interpreters, which are computer programs that process other programs as input. A famous computer scientist once remarked that if you don't understand interpreters, you can still write programs—and you can even be a competent programmer—but you can't be a master. We will begin by studying functional programming using the strangely beautiful and recursive programming language Scheme. After getting comfortable with Scheme and recursion, we will see how to design our own languages by starting from a high-level description and systematically deriving a low-level implementation through the application of a series of program transformations. Along the way, we will become acquainted with the lambda calculus (the basis of modern programming language theory), scoping mechanisms, continuations, lazy and nondeterministic evaluation, and other topics if time permits. We will use Scheme as our “meta-language” for exploring these issues in a precise, analytical way, similar to the way in which mathematics is used to describe phenomena in the natural sciences. Our great advantage over mathematics, however, is that we can test out our ideas about languages, expressed in the form of interpreters, by directly executing them on the computer. Permission of the instructor is required. No prior knowledge of Scheme is needed, but at least one semester of prior programming experience is expected.

From social networking via the iPhone, Facebook, and Twitter to massively multiplayer online games, computer technology plays an ever-increasing role in our daily lives. Where may this phenomenon be taking us in the immediate (and not-so-immediate) future? Is there (or should there be) anything we can (or should) do about it? The miniaturization of electronic computers and the resulting increase in computing power, decrease in short-term cost to harness that power, and ubiquity of computer networks brings people and places together, making distances formerly thought of as insurmountable evermore trivial. With the advent of gigabit fiber-optic networks, smart phones, flip cameras, and RFID tags, information of all kinds (text, voice, images, movies, and more) can flow around the world—between people and objects and back again—in an instant. In this course, we will consider how information can be represented using bits on digital computers and how it can be communicated accurately, efficiently, and “automatically” on the Internet. We will consider some historical context: How does the rise of the Internet compare with the development of the printing press, the telegraph, radio, and television? We will focus on the evolution (or, some would say, revolution) in new media and how that leads to what journalist Bob Garfield refers to as the “Chaos Scenario”: the Internet's effect on traditional media (newspapers, magazines, books, radio, television, film, quaint objects known as “records,” you name it) and marketing as it all migrates online. In many ways, the plethora of smaller, cheaper, faster networked devices improves our quality of life. But we will also consider the dark side of a highly connected society: the more smart phones, the more workaholics; the more cellphone calls, text messages, and e-mails exchanged, the less privacy; the more iPads, the more music and video piracy; and the greater reach of the Internet, the greater the distribution of spam, pornography, and the likelihood of cyberterrorism. To tie many of these themes together, we will read some dystopian cyberpunk fiction that may make your hair (virtual or otherwise) stand on end. This is not a technical course, though at times we will discuss some details that lie behind certain crucial technologies; in particular, the Internet and the World Wide Web.

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, artificial neural networks, genetic algorithms and artificial life, Turing machines, and quantum computation. 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.

This course is a journey analogous to space exploration. Our infinite cosmos will be the set of natural numbers. Our exploratory rocket ships will be computer programs of our own design. The planets possibly bearing alien life forms are different classes of prime numbers.

More literally, this course is a research driven introduction to elementary number theory and its application to computer-network security. We will write a series of computer programs of increasing sophistication whose aim will be to identify patterns among prime numbers. In some cases we will search for empirical evidence in support of well established theories (for example, the Prime Number Theorem), in other cases we will be analyzing and interpreting data in an effort to discover new theorems and their applications (for example, regarding "safe primes").

We will pose philosophical questions regarding the nature of modern mathematics (and, therefore, computer science). For instance, to what extent can a computer be used to prove theorems? Is there a fundamental difference between theorems that seems to require "insight" for their proof (for example, using a non-constructive proof by contradiction to establish the infinitude of primes) as opposed to those that correspond to more algorithmic arguments?

We will investigate what it means to be random. Can randomness be generated by an algorithmic process? We will see examples of how some problems that appear the be very difficult may be solved quickly using random numbers with the caveat that the answer we get is only "probably" true. We discuss the philosophical and practical implications of this approach. In particular, we will contrast on the one hand, the ease with which random numbers can be harnessed to discover primes, and on the other, the challenge of finding divisors of composite numbers. We will also consider the Web-shaking implications if the latter problem turns out to be less difficult than it appears.

Topics in elementary number-theory include: unique factorization, modular arithmetic, Euler's phi function, Fermat's Little Theorem, primitive roots, quadratic residues and Gauss' Law of Quadratic Reciprocity. Cryptology topics include: Diffie-Hellman key exchange, RSA encryption, El Gamal signatures, pseudorandom number generators, zero-knowledge proofs, and applications of these to electronic voting and digital currency. Algorithmic topics include: modular exponentiation, probabilistic prime testing, factorization and discrete logarithms, and the theory of NP-completeness.

There is no one single prerequisite for this course, but students should have either at least one semester of programming experience (preferably in Python; but C, C++, or Java should be fine) or some experience with mathematical proof (for example, one semester of college-level mathematics such as Discrete Mathematics). Cross listed with Mathematics. Intermediate, permission of instructor required.

A modern database system is a collection of interrelated facts recorded on digital media and a set of computer programs to access those facts. In the 21st century, databases have become ubiquitous via the Web and “cloud computing” to the point that users may not even realize where their data is stored, how it is accessed, and who has access to it. This course attempts to shed light on why and how our society has become so dependent on information-processing by examining software (and, to a lesser extent, hardware) techniques that lead to the efficient storage and retrieval of information. We will illustrate these principles by designing databases using open-source platforms (such as MySQL) and by designing Web sites to manipulate those databases using client-side technologies (such as HTML, CSS, Javascript and AJAX) and server-side programming languages (such as PHP and Python). Major topics include relational database design, query languages (such as SQL, XQuery and XSLT), the object-relational model, ACID properties, and the client-server paradigm. Each student will be responsible for designing and implementing a Web-accessible database application of her or his choosing, using open-source database software and a Web-application programming language such as PHP, Python, or Ruby. Students will work on their projects throughout the course and will demonstrate them to the rest of the class at the close of the semester. We will also consider Web-application frameworks such as Ruby on Rails and Django. In addition to regular reading assignments, there will be several problem sets and short programming assignments. There will also be a more substantial programming assignment used to illustrate issues pertaining to the practical implementation of database systems. Suggested conference topics include data mining, database privacy, geographical information systems (GIS), and the implementation of a miniature database system. Permission of the instructor is required. Students should be familiar with the basics of HTML and have at least one semester of programming experience.

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 out on both real and simulated robots. Students will have many opportunities for extended exploration through open-ended laboratory 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++.