Monthly Subscription Starting at AED 99 + VAT

Computer Science: Algorithms, Theory, and Machines
  • Level Professional
  • Duration 20 hours
  • Course by Princeton University
  • Offered by

About

This course introduces the broader discipline of computer science to people having basic familiarity with Java programming. It covers the second half of our book Computer Science: An Interdisciplinary Approach (the first half is covered in our Coursera course Computer Science: Programming with a Purpose, to be released in the fall of 2018). Our intent is to demystify computation and to build awareness about the substantial intellectual underpinnings and rich history of the field of computer science. First, we introduce classic algorithms along with scientific techniques for evaluating performance, in the context of modern applications. Next, we introduce classic theoretical models that allow us to address fundamental questions about computation, such as computability, universality, and intractability. We conclude with machine architecture (including machine-language programming and its relationship to coding in Java) and logic design (including a full CPU design built from the ground up). The course emphasizes the relationships between applications programming, the theory of computation, real computers, and the field's history and evolution, including the nature of the contributions of Boole, Shannon, Turing, von Neumann, and others. All the features of this course are available for free. No certificate will be offered upon completion.

Modules

INFORMATION ABOUT LECTURES 1–10

    • 1 Readings
Show info about module content

1 Readings

  • Information about Lectures 1–10

LECTURE 11: SORTING AND SEARCHING

    • 5 Videos
    • 3 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Sorting and Searching

5 Videos

  • A typical client
  • Binary search
  • Insertion sort
  • Mergesort
  • Longest repeated substring

3 Readings

  • Getting Started
  • Supplements for Lecture 11
  • Optional Enrichment on Sorting and Searching

LECTURE 12: STACKS AND QUEUES

    • 5 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Stacks and Queues

5 Videos

  • APIs
  • Clients
  • Strawman implementations
  • Linked lists
  • Implementations

2 Readings

  • Supplements for Lecture 12
  • Optional Enrichment on Stacks and Queues

LECTURE 13: SYMBOL TABLES

    • 5 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Symbol Tables

5 Videos

  • APIs and clients
  • A design challenge
  • Binary search trees
  • Implementation
  • Analysis

2 Readings

  • Supplements for Lecture 13
  • Optional Enrichment on Symbol Tables

LECTURE 14. INTRODUCTION TO THE THEORY OF COMPUTING

    • 5 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Theory of Computing

5 Videos

  • Overview
  • Regular Expressions
  • DFAs
  • Applications
  • Limitations

2 Readings

  • Supplements for Lecture 14
  • Optional Enrichment on Theory of Computing

LECTURE 15. TURING MACHINES

    • 5 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Turing Machines

5 Videos

  • Context
  • A simple model of computation
  • Universality
  • Computability
  • Implications

2 Readings

  • Supplements for Lecture 15
  • Optional Enrichment on Turing Machines

LECTURE 16. INTRACTABILITY

    • 5 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Intractability

5 Videos

  • Reasonable questions
  • P and NP
  • Poly-time reductions
  • NP-completeness
  • Living with intractability

2 Readings

  • Supplements for Lecture 16
  • Optional Enrichment on Intractability

LECTURE 17. A COMPUTING MACHINE

    • 5 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • A Computing Machine

5 Videos

  • Overview
  • Data Types
  • Instructions
  • Operating the machine
  • Machine language programming

2 Readings

  • Supplements for Lecture 17
  • Optional Enrichment on A Computing Machine

LECTURE 18. VON NEUMANN MACHINES

    • 4 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • von Neumann Machines

4 Videos

  • Perspective
  • A note of caution
  • Practical implications
  • Simulation

2 Readings

  • Supplements for Lecture 18
  • Optional Enrichment on von Neumann Machines

LECTURE 19. COMBINATIONAL CIRCUITS

    • 5 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Combinational Circuits

5 Videos

  • Building blocks
  • Boolean algebra
  • Digital circuits
  • Adder circuit
  • Arithmetic/logic unit

2 Readings

  • Supplements for Lecture 19
  • Optional Enrichment on Combinational Circuits

LECTURE 20. CENTRAL PROCESSING UNIT

    • 4 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • CPU

4 Videos

  • Overview
  • Bits, registers, and memory
  • Program counter
  • Components and connections

2 Readings

  • Supplements for Lecture 20
  • Optional Enrichment on the CPU

Auto Summary

Explore the fascinating world of computer science with this comprehensive course focused on algorithms, theoretical models, and machine architecture. Designed for those with basic Java knowledge, it delves into performance evaluation, computability, and CPU design while highlighting the contributions of pioneers like Boole and Turing. Offered by Coursera, this professional-level course spans 1200 hours and is available for free, though no certificate is provided. Ideal for anyone looking to deepen their understanding of the intellectual foundations of computer science.

Robert Sedgewick
Instructors

Robert Sedgewick

Kevin Wayne
Instructors

Kevin Wayne