Week 10

Be sure to take the last quiz while it is open!

You will want to start preparing for the final now. The final is cumulative, covering all of the material from the course. If you want to get a head start on studying, the best thing to do is go back and review the earlier quizzes and assignments.

Upon finishing this learning module, you should be able to:

• Describe what quantum computing is and why we are interested in it
• Argue why some problems cannot be solved by an algorithm
• Write python code to do simple data processing

To enable timely grading, new submissions of late work will not be accepted after the deadline for the last written assignment.

Algorithm of the Week: Computability

Read chapter 10 of the Nine Algorithms book. It explores the idea of computability and how we know some things are uncomputable—and have known since before there were computers!

Then, read the Computability supplement, which has a video that briefly recaps the Halting Problem and has an optional video with more information about Turing machines.

The Future of Computing

Read chapter 11 in Welcome to CS, on the Limits and Future of Computing. It discusses the algorithmic and engineering limitations computation faces, as well as one possible future technology: quantum computing.

Optionally, read this more detailed description of how quantum computing works.