Computer Science: Algorithms, Theory, and Machines from Coursera

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. People who are interested in digging deeper into the content may wish to obtain the textbook Computer Science: An Interdisciplinary Approach (upon which the course is based) or to visit the website introcs.cs.princeton.edu for a wealth of additional material.

This course does not offer a certificate upon completion.

What's inside

Syllabus

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Demystifies computation, building awareness of substantial intellectual underpinnings and rich history of computer science

Emphasizes relationships between applications programming, theory of computation, real computers, and the field's history and evolution

Taught by Robert Sedgewick and Kevin Wayne, recognized researchers and educators in computer science

Provides insights into the fundamental design of computer processors, crucial for understanding how code gets its job done

Introduces classic algorithms and theoretical models, fostering a deep understanding of computer science principles

Requires no prior knowledge of computer science, making it accessible to beginners in the field

Reviews summary

Solid introduction to computer science fundamentals

Learners say that this Princeton University course gives a solid and comprehensive introduction to computer science. The instructors break down the fundamentals of algorithms, theory, and machines. They also tell the origin stories of the field, which students enjoy. While the course is short, it manages to pack in a lot of information in a short amount of time. The only downside is that it doesn't offer any programming assignments.

Varies depending on experience

"The course is very interesting. But, it also is very difficult from week 4 on."

"this was actually quite hard but knowledgable course .I learned a lot from this ."

"Beware the course goes really deep. It will only take quoted 20 hours if you merely watch the videos, skim through the textbook amd guess your way through the grading tests."

"The latter half covers theoretical concepts like the Turing Machine, Intractability and the design of the CPU."

Excellent introductory course

"Excellent introductory course to theoretical concepts of Computer Scirence."

"This is a very good course on general computer science theories."

"A solid introduction to Computer Science."

"The course is great and it really drills down to the basic of computers."

Not available

"Very elementary course in computer science."

"I Didn't get any Certificate"

"we are not provided any certificate"

"The book was a marvelous introduction to Computer Science."

None

"I really enjoyed this class - I wish it had weekly assignments like Programming with a Purpose and the Algorithms courses do."

"Programming assignments would have made the course more challenging and fun."

"The harder to gain the knowledge, the higher the chances it stays there for good."

"To sum up - just make this course harder to pass with more hands on exercises and circuits to build :)"

Relatively short

"This course is a life-changer for me."

"A short but very rich course"

"Its one thing to understand the content that you are delivering, its another to be able to package it into something that you can teach others."

"this course might require a healthy amount of work on your part."

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in Computer Science: Algorithms, Theory, and Machines with these activities:

Review basic Java programming concepts

Show steps

Ensure a strong foundation by refreshing your knowledge of basic Java programming concepts.

Browse courses on Java Programming

Show steps

Review online tutorials or documentation.
Solve simple coding exercises.

Join a study group for combinatorial circuits

Show steps

Engage with other learners and solidify your understanding of combinatorial circuits through group discussions and problem-solving.

Show steps

Find or create a study group with peers.
Review course materials and prepare questions.
Meet regularly to discuss concepts and solve problems.

Read Introduction to the Theory of Computing

Show steps

Expand your knowledge by delving into the foundations of theoretical computer science with this classic textbook.

View Introduction to the Theory of Computation on Amazon

Show steps

Read a chapter and summarize the key concepts.
Solve the chapter's exercises.

Five other activities

Expand to see all activities and additional details

Show all eight activities

Practice binary search and mergesort

Show steps

Reinforce your understanding of classic algorithms by solving problems on platforms like LeetCode or HackerRank.

Browse courses on Sorting and Searching

Show steps

Choose a problem related to binary search or mergesort.
Implement the algorithm in your preferred programming language.
Test your implementation with various inputs.

Build a linked list from scratch

Show steps

Deepen your understanding of data structures by implementing a linked list from scratch in your preferred programming language.

Show steps

Design the node structure for your linked list.
Implement the basic operations (e.g., add, remove, search).
Test your implementation with various inputs.

Develop a presentation on von Neumann machines

Show steps

Demonstrate your understanding of computer architecture by creating a presentation that explains the principles of von Neumann machines.

Browse courses on Computer Architecture

Show steps

Research the topic and gather relevant information.
Create visual aids and organize your presentation.
Practice delivering your presentation.

Build a virtual machine simulator

Show steps

Develop a deeper understanding of processor design by building a simulator for a simple virtual machine.

Browse courses on Turing Machines

Show steps

Choose a tutorial or online resource.
Implement the basic components of the virtual machine.
Test your simulator with various programs.

Implement a small compiler

Show steps

Challenge yourself by building a fully functional compiler for a simple programming language.

Browse courses on Compilers

Show steps

Design the syntax and semantics of your language.
Implement the lexical analyzer and parser.
Generate intermediate code or assembly.

Career center

Learners who complete Computer Science: Algorithms, Theory, and Machines will develop knowledge and skills that may be useful to these careers:

Computer Architect

Computer Architects design and develop the hardware and software that make up computers. This course may be useful for Computer Architects because it provides a deep understanding of machine architecture, including machine-language programming and logic design.

See salaries and explore the career path for Computer Architect

Computer Scientist

Computer Scientists conduct research in the field of computer science and develop new technologies. This course may be useful for Computer Scientists because it provides a broad overview of computer science, including algorithms, theory, and machines, which are essential for conducting research in the field.

See salaries and explore the career path for Computer Scientist

Machine Learning Engineer

Machine Learning Engineers design and develop machine learning models to solve real-world problems. This course may be useful for Machine Learning Engineers because it covers the theoretical foundations of computation, including Turing machines and intractability, which are essential for understanding the limitations and capabilities of machine learning.

See salaries and explore the career path for Machine Learning Engineer

Artificial Intelligence Engineer

Artificial Intelligence Engineers design and develop artificial intelligence systems. This course may be useful for Artificial Intelligence Engineers because it provides a strong foundation in algorithms, theory, and machines, which are essential for understanding and developing artificial intelligence systems.

See salaries and explore the career path for Artificial Intelligence Engineer

Information Security Analyst

Information Security Analysts plan and implement security measures to protect an organization's computer systems and data. This course may be useful for Information Security Analysts because it provides a strong foundation in computer science principles, including algorithms, theory, and machines, which are essential for understanding and protecting computer systems.

See salaries and explore the career path for Information Security Analyst

Data Scientist

Data Scientists use data to solve business problems and make predictions. This course may be useful for Data Scientists because it provides a strong foundation in algorithms, theory, and machines, which are essential for understanding and manipulating data.

See salaries and explore the career path for Data Scientist

Robotics Engineer

Robotics Engineers design, build, and maintain robots. This course may be useful for Robotics Engineers because it provides a strong foundation in computer science principles, including algorithms, theory, and machines, which are essential for understanding and developing robots.

See salaries and explore the career path for Robotics Engineer

Data Analyst

Data Analysts collect, analyze, and interpret data to help organizations make informed decisions. This course may be useful for Data Analysts because it provides a strong foundation in algorithms, theory, and machines, which are essential for understanding and manipulating data.

See salaries and explore the career path for Data Analyst

Web Developer

Web Developers design and develop websites and web applications. This course may be useful for Web Developers because it provides a foundation in computer science principles, including algorithms, theory, and machines, which are essential for understanding and developing web applications.

See salaries and explore the career path for Web Developer

Computer Systems Analyst

Computer Systems Analysts study an organization's current computer systems and procedures, and design ways to make them more efficient and effective. This course may be useful for Computer Systems Analysts because it provides a solid foundation in computer science principles, including algorithms, theory, and machines.

See salaries and explore the career path for Computer Systems Analyst

Database Administrator

Database Administrators maintain and optimize databases, ensuring that data is accurate, secure, and accessible. This course may be useful for Database Administrators because it covers data structures, including symbol tables and binary search trees, which are essential for managing and organizing data.

See salaries and explore the career path for Database Administrator

Systems Administrator

Systems Administrators maintain and operate computer systems and networks. This course may be useful for Systems Administrators because it provides a solid foundation in computer science principles, including algorithms, theory, and machines, which are essential for understanding and managing computer systems.

See salaries and explore the career path for Systems Administrator

Computer Programmer

Computer Programmers write and maintain computer programs. This course may be useful for Computer Programmers because it provides a broad overview of computer science, including algorithms, theory, and machines, which are essential for understanding and developing computer programs.

See salaries and explore the career path for Computer Programmer

Software Developer

Software Developers design, develop, test, and maintain software applications. This course may be useful for Software Developers because it provides a broad overview of computer science, including algorithms, theory, and machines, which are essential for understanding and developing software systems.

See salaries and explore the career path for Software Developer

Software Engineer

Software Engineers design, develop, test, and maintain computer systems and applications. This course may be useful for Software Engineers because it introduces the broader discipline of computer science, covering classic algorithms, theoretical models, machine architecture, and logic design.

See salaries and explore the career path for Software Engineer