Duke University

Overview

Computer Science has made great strides in the last hundred years since it emerged as an independent discipline is the first half of the 20th century. This course gives a conceptual overview of this progress by highlighting some of the greatest ideas that computer science has contributed to modern scientific inquiry. We explore what these ideas mean beyond the technical details that sometimes obscure them, where they came from, and how they have embellished scientific thought.

Lectures

LSRC A155. Mondays and Wednesdays @ 1:45 - 3:00 pm

Lectures are in person. Masks are mandatory.

Syllabus

Since this course is being taught for the first time, the syllabus will evolve over time. We will pick a theme and spend 2-3 lectures exploring it before moving on the next theme. The themes listed below are some examples.

• Algorithms: Computability

We start our journey by talking about the idea of algorithms, which has existed for a very long time and predates computers by thousands of years. We also talk about how computer science evolved as a discipline from two very distinct views of algorithms, the mathematician's and the engineer's, that have squarely put computer science at the intersection of pure and applied science. Finally, we talk about the halting problem and how it's undecidability is strongly tied to notions of incompleteness that straddle mathematics and philosophy.

• Computing Machines: Physical and Formal Computers

We continue straddling the divide between practical computer science, as embodied by physical computers that started off as giant machines that could only handle a few bits of information, and theoretical computer science, which captures the very concept of computation through a range of formalisms such as Turing machines and recursive functions, which surprisingly turn out to be equivalent.

• Algorithms II: Efficient Computation

After having explored computation as an abstract concept, and realized that there are problems that are not computable at all, we now turn our attention to efficient computation. We establish polynomial-time computation as the gold standard of efficient algorithms, explore the greatest unsolved mystery in computer science in the form of the P vs NP problem, and then realize how this problem is much more than just a statement about polynomial-time computation.

• Randomness

The use of randomness is an important concept in computer science, so much so that random bits are considered a resource much like time and space for an algorithm. We explore how randomness can be used to define interactive proof frameworks such as probabilistically checkable proofs and zero knowledge proofs.

• Computing at Large Scale

Our survey of large scale computation spans the theoretical understanding of distributed computation to the history of high performance computing.

• Cryptography

We discuss basic concepts in cryptography including the Diffie Hellman protocol and the RSA cryptosystem. We also touch upon other related concepts such as one way functions and secure multiparty computation. Finally, we talk about blockchains and cryptocurrency.

• Artificial Intelligence

We start with the early history of artificial intelligence including the Turing test and its various critiques, We then discuss classical search and optimization paradigms in AI.

• Machine Learning

We continue our journey in AI by focusing on the concept of a descriptive model of computing by learning from examples rather than the traditional prescriptive model in algorithm design. We then talk about the three main paradigms in machine learning: supervised learning, unsupervised learning, and reinforcement learning. Finally, we give a brief overview of the idea of artificial neural networks.

• Databases

We focus on data models, particularly the relational data framework, and its relationship to first order logic. We then explore the basics of transaction processing.

• Networks

We talk about the history of computer networks, and how the modern Internet evolved from early attempts to create networked systems. We then talk about the network stack abstraction and network protocols.

• Computing and the Sciences

In the last part of our course, we briefly talk about how computer science interacts with other sciences. In particular, we talk about quantum computation and other models of computation inspired by the natural sciences.

Evaluation

The evaluation will be based on homework assignments and exams.

Homework

Problems will be added to the homework assignment sheet (on Sakai) over the course of the semester (about 1 per week). You need to submit 10 homework problems at least 5 homework problems (edited: 10/18) by LDOC (December 3, 2021). To make sure you stay on track, you need to meet the following intermediate submission targets:

• At least 3 problems 2 problems (edited: 9/21) by the end of September.

• At least 6 problems 4 problems (edited: 10/18) by the end of October.

• At least 9 problems by the end of November. (edited: 10/18)

For every missed submission target, you will lose credit for one homework problem that you scored the least on. For instance, if you fail to meet two of the three submission targets, and eventually submit only 8 problems, then you will get credit for the 6 out of the 8 problems on which your score is highest.

Exams

There will be two exams on Nov 12 and Nov 19. Each exam will account for 25% of the final grade. Both exams will be untimed take home exams with a 24 hour window. The first exam (on Nov 12) will include the topics covered in lecture till Oct 6. The second exam (on Nov 19) will include the topics covered in lecture from Oct 11 onward. There will be no final exam.

Reading Project

There will a reading project that students will have to do in teams of 3-4. This involves choosing any topic of interest in computer science, reading about it, and presenting to the class in a 15 min presentation. We will have the presentations on Nov 29 and Dec 1. The topic can be a new aspect of a topic covered in class, or something completely new. Please submit your project team and proposed topic with a short description by Nov 1. The reading project and presentation will account for 25% of the course grade.

Overall Grade

The overall grade will be calculated as follows:

• Two units, one each, from the two exams

• One unit from the top 5 HW answers

• One unit from the next 5 HW answers (you are free to submit only 5 answers in which case this unit will be the one to get dropped)

• One unit from reading project

The final grade will be based on the best 4 out of these 5 units. Each unit will account for 25% of the grade.