SEMAINE 1

INFORMATION ABOUT LECTURES 1-10

This lesson provides information about the course Computer Science: Programming with a Purpose, which is the precursor to Computer Science: Algorithms, Theory, and Machines.

1 lecture

阅读: Information about Lectures 1-10

SORTING AND SEARCHING

We introduce and study classic algorithms for two fundamental problems, in the context of realistic applications. Our message is that efficient algorithms (binary search and mergesort, in this case) are a key ingredient in addressing computational problems with scalable solutions that can handle huge instances, and that the scientific method is essential in evaluating the effectiveness of such solutions.

5 vidéos, 3 lectures

阅读: Getting Started
阅读: Supplements for Lecture 11
Vidéo: Binary search
Vidéo: Insertion sort
Vidéo: Mergesort
Vidéo: Longest repeated substring
阅读: Optional Enrichment on Sorting and Searching
讨论提示: Optional Enrichment on Sorting and Searching

Noté: Sorting and Searching

SEMAINE 2

STACKS AND QUEUES

Our introduction to data structures is a careful look at the fundamental stack and queue abstractions, including performance specifications. Then we introduce the concept of linked structures and focus on their utility in developing simple, safe, clear, and efficient implementations of stacks and queues.

5 vidéos, 2 lectures

阅读: Supplements for Lecture 12
Vidéo: Clients
Vidéo: Strawman implementations
Vidéo: Linked lists
Vidéo: Implementations
阅读: Optional Enrichment on Stacks and Queues
讨论提示: Optional Enrichment on Stacks and Queues

Noté: Stacks and Queues

SEMAINE 3

SYMBOL TABLES

The symbol table abstraction is one of the most important and useful programmer's tools, s we illustrate with several examples in this lecture. Extending the scientific approach of the previous two lectures, we introduce and study binary search trees, a classic data structure that supports efficient implementations of this abstraction.

5 vidéos, 2 lectures

阅读: Supplements for Lecture 13
Vidéo: A design challenge
Vidéo: Binary search trees
Vidéo: Implementation
Vidéo: Analysis
阅读: Optional Enrichment on Symbol Tables
讨论提示: Optional Enrichment on Symbol Tables

Noté: Symbol Tables

SEMAINE 4

INTRODUCTION TO THE THEORY OF COMPUTING

The theory of computing helps us address fundamental questions about the nature of computation while at the same time helping us better understand the ways in which we interact with the computer. In this lecture, we introduce formal languages and abstract machines, focusing on simple models that are actually widely useful in practical applications.

5 vidéos, 2 lectures

阅读: Supplements for Lecture 14
Vidéo: Regular Expressions
Vidéo: DFAs
Vidéo: Applications
Vidéo: Limitations
阅读: Optional Enrichment on Theory of Computing
讨论提示: Optional Enrichment on Theory of Computing

Noté: Theory of Computing

SEMAINE 5

TURING MACHINES

In 1936, Alan Turing published a paper that is widely hailed as one of the most important scientific papers of the 20th century. This lecture is devoted to the two far-reaching central ideas of the paper: All computational devices have equivalent computational power, and there are limitations to that power.

5 vidéos, 2 lectures

阅读: Supplements for Lecture 15
Vidéo: A simple model of computation
Vidéo: Universality
Vidéo: Computability
Vidéo: Implications
阅读: Optional Enrichment on Turing Machines
讨论提示: Optional Enrichment on Turing Machines

Noté: Turing Machines

SEMAINE 6

INTRACTABILITY

As computer applications expanded, computer scientists and mathematicians realized that a refinement of Turing's ideas is needed. Which computational problems can we solve with the resource limitations that are inescapable in the real world? As described in this lecture, this question, fundamentally, remains unanswered.

5 vidéos, 2 lectures

阅读: Supplements for Lecture 16
Vidéo: P and NP
Vidéo: Poly-time reductions
Vidéo: NP-completeness
Vidéo: Living with intractability
阅读: Optional Enrichment on Intractability
讨论提示: Optional Enrichment on Intractability

Noté: Intractability

SEMAINE 7

A COMPUTING MACHINE

Every programmer needs understand the basic characteristics of the underlying computer processor being used. Fortunately, the fundamental design of computer processors has changed little since the 1960s. In this lecture, we provide insights into how your Java code actually gets its job done by introducing an imaginary computer that is similar to both the minicomputers of the 1960s and the microprocessor chips found in today's laptops and mobile devices.

5 vidéos, 2 lectures

阅读: Supplements for Lecture 17
Vidéo: Data Types
Vidéo: Instructions
Vidéo: Operating the machine
Vidéo: Machine language programming
阅读: Optional Enrichment on A Computing Machine
讨论提示: Optional Enrichment on A Computing Machine

Noté: A Computing Machine

SEMAINE 8

VON NEUMANN MACHINES

Continuing our description of processor design and low-level programming, we provide context stretching back to the 1950s and discuss future implications of the von Neumann machine, where programs and data are kept in the same memory. We examine in detail the idea that we design new computers by simulating them on old ones, something that Turing's theory guarantees will always be effective.

4 vidéos, 2 lectures

阅读: Supplements for Lecture 18
Vidéo: A note of caution
Vidéo: Practical implications
Vidéo: Simulation
阅读: Optional Enrichment on von Neumann Machines
讨论提示: Optional Enrichment on von Neumann Machines

Noté: von Neumann Machines

SEMAINE 9

COMBINATIONAL CIRCUITS

Starting with a few simple abstractions (wires that can carry on/off values and switches that can control the values carried by wires), we address in this lecture the design of the circuits that implement computer processors. We consider gates that implement simple logical functions and components for higher-level functions, such as addition. The lecture culminates with a full circuit for an arithmetic/logic unit.

4 vidéos, 2 lectures

阅读: Supplements for Lecture 19
Vidéo: Digital circuits
Vidéo: Adder circuit
Vidéo: Arithmetic/logic unit
阅读: Optional Enrichment on Combinational Circuits
讨论提示: Optional Enrichment on Combinational Circuits

Noté: Combinational Circuits

SEMAINE 10

CENTRAL PROCESSING UNIT

In this lecture, we provide the last part of our answer to the question "How does a computer work?" by developing a complete circuit for a computer processor, where every switch and wire is visible. While vastly different in scale, this circuit, from a design point of view, has many of the same characteristics as the circuits found in your computer and your phone.

4 vidéos, 2 lectures

阅读: Supplements for Lecture 20
Vidéo: Bits, registers, and memory
Vidéo: Program counter
Vidéo: Components and connections
阅读: Optional Enrichment on the CPU
讨论提示: Optional Enrichment on the CPU

Noté: CPU

Niveau	Intermediate
Engagement	10 weeks of study, 2-5 hours/week
Langue	English
Comment réussir	Réussissez tous les devoirs notés pour terminer le cours.
Notes des utilisateurs	4.8 étoiles Note moyenne des utilisateurs 4.8Voir ce que disent les étudiants