Explore

Computer Science: Algorithms, Theory, and Machines

Approx. 20 hours to complete

Save Course

Go to Course

Course Summary

This course covers the fundamentals of computer science theory, algorithms, and machines. You'll learn about different machine models and their capabilities, and how to apply algorithms to solve problems efficiently.

Key Learning Points

Understand the basics of computer science theory, including Turing machines and complexity theory
Learn about different types of algorithms and how to analyze their efficiency
Explore different machine models and their capabilities

Learning Outcomes

Ability to analyze the efficiency of algorithms
Understanding of different machine models and their capabilities
Improved problem solving skills

Prerequisites or good to have knowledge before taking this course

Basic programming knowledge
Familiarity with mathematical concepts

Course Difficulty Level

Intermediate

Course Format

Online
Self-paced

Similar Courses

Algorithms, Part I
Discrete Optimization

Related Education Paths

Notable People in This Field

Scott Aaronson
Andrew Ng

Related Books

Description

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.

Outline

INFORMATION ABOUT LECTURES 1–10
Information about Lectures 1–10

SORTING AND SEARCHING
A typical client
Binary search
Insertion sort
Mergesort
Longest repeated substring
Getting Started
Supplements for Lecture 11
Optional Enrichment on Sorting and Searching
Sorting and Searching

STACKS AND QUEUES
APIs
Clients
Strawman implementations
Linked lists
Implementations
Supplements for Lecture 12
Optional Enrichment on Stacks and Queues
Stacks and Queues

SYMBOL TABLES
APIs and clients
A design challenge
Binary search trees
Implementation
Analysis
Supplements for Lecture 13
Optional Enrichment on Symbol Tables
Symbol Tables

INTRODUCTION TO THE THEORY OF COMPUTING
Overview
Regular Expressions
DFAs
Applications
Limitations
Supplements for Lecture 14
Optional Enrichment on Theory of Computing
Theory of Computing

TURING MACHINES
Context
A simple model of computation
Universality
Computability
Implications
Supplements for Lecture 15
Optional Enrichment on Turing Machines
Turing Machines

INTRACTABILITY
Reasonable questions
P and NP
Poly-time reductions
NP-completeness
Living with intractability
Supplements for Lecture 16
Optional Enrichment on Intractability
Intractability

A COMPUTING MACHINE
Overview
Data Types
Instructions
Operating the machine
Machine language programming
Supplements for Lecture 17
Optional Enrichment on A Computing Machine
A Computing Machine

VON NEUMANN MACHINES
Perspective
A note of caution
Practical implications
Simulation
Supplements for Lecture 18
Optional Enrichment on von Neumann Machines
von Neumann Machines

COMBINATIONAL CIRCUITS
Building blocks
Boolean algebra
Digital circuits
Adder circuit
Arithmetic/logic unit
Supplements for Lecture 19
Optional Enrichment on Combinational Circuits
Combinational Circuits

CENTRAL PROCESSING UNIT
Overview
Bits, registers, and memory
Program counter
Components and connections
Supplements for Lecture 20
Optional Enrichment on the CPU
CPU

Summary of User Reviews

Learn about algorithms, theory, and machines with this course on Coursera. Users have praised the course for its comprehensive content and engaging instructors.

Key Aspect Users Liked About This Course

Comprehensive content

Pros from User Reviews

Engaging instructors
In-depth explanations
Challenging assignments

Cons from User Reviews

Difficult for beginners
Some technical issues with the platform
Limited interaction with instructors

Recommended for you

2021 Data Science & Machine Learning with R from A-Z Course

Become a professional Data Scientist with R and learn Machine Learning, Data Analysis + Visualization, Web Apps + more! NOTE: The additional content will focus on Machine Learning....

Save Course

Algorithms Bootcamp in C++

Recursion, backtracking, dynamic programming and data structures (linked lists, queues, stacks and binary search trees) Chapter 1: Recursion theory behind recursion (recursive function calls)...

Save Course

CS50's Introduction to Artificial Intelligence with Python

Learn to use machine learning in Python in this introductory course on artificial intelligence. AI is transforming how we live, work, and play....

Save Course

Foundations of Computer Science

Welcome to Introduction to Programming: Visual Basic. In the course sequence you will learn to write programs that utilize both procedural and object oriented techniques to solve business problems....

Save Course