Today, we’re going to build the ticking heart of every computer - the Central Processing Unit or CPU. The CPU’s job is to execute the programs we know and love - you know, like GTA V, Slack... and PowerPoint. To make our CPU, we’ll bring in our ALU and RAM we made in the previous two episodes, and then, with the help of Carrie Anne’s wonderful dictation, (slowly) step through some clock cycles.
Since Joseph Marie Jacquard’s textile loom in 1801, there has been a demonstrated need to give our machines instructions. In the last few episodes, our instructions were already in our computer’s memory, but we need to talk about how they got there - this is the heart of programming. Today, we’re going to look at the history of programming.
We ended the last episode, Early Programming: Crash Course Computer Science #10, with programming at the hardware level with things like plugboards and huge panels of switches, but what was really needed was a more versatile way to program computers - software!
Algorithms are the sets of steps necessary to complete computation - they are at the heart of what our devices actually do. And this isn’t a new concept. Since the development of math itself, algorithms have been needed to help us complete tasks more efficiently. Today we’re going to look at a couple of modern computing problems, like sorting and graph search, and show how we’ve made them more efficient so you can easily find cheap airfare or map directions.
Carrie Anne is going to start our overview of the fundamental building blocks of programming languages. We’ll start by creating small programs for our very own video game to show how statements and functions work. We aren’t going to code in a specific language, but we’ll show you how conditional statements like IF and ELSE statements, WHILE loops, and FOR loops control the flow of programs in nearly all languages, and then we’ll finish by packaging up these instructions into functions that can be called by our game to perform more and more complex actions.
This video will talk about how HUGE programs with millions of lines of code like Microsoft Office are built. Programs like these are way too complicated for a single person, but instead require teams of programmers using the tools and best practices that form the discipline of Software Engineering. We'll talk about how large programs are typically broken up into function units that are nested into objects known as Object-Oriented Programming, as well as how programmers write and debug their code efficiently, document and share their code with others, and also how code repositories are used to allow programmers to make changes while mitigating risk.
This video excerpt from NOVA, “Smartest Machine on Earth”, explains why computers can be programmed to beat the greatest human chess masters—it’s all in the logic of the game. Computers can use their understanding of the rules of chess to plan many more moves ahead than humans can. But when computers bring that kind of understanding to other situations, such as learning human languages, they lack the intelligence needed to successfully master those tasks.
This video will talk about a fundamental part of all modern computers. The thing that basically everything else uses - the Arithmetic and Logic Unit (or the ALU). The ALU may not have to most exciting name, but it is the mathematical brain of a computer and is responsible for all the calculations your computer does! And it's actually not that complicated.
Are there problems that are too hard even for computers? It turns out that there are. In the chapter on Artificial Intelligence, we'll see that just having a conversation – chatting – is something computers can't do well, not because they can't speak but rather because they can't understand or think of sensible things to say. However, that’s not the kind of hard problem we’re talking about here – it's not that computers couldn’t have conversations, it's more that we don't know just how we do it ourselves and so we can't tell the computer what to do.
In this chapter, we're going to look at problems where it's easy to tell the computer what to do – by writing a program – but the computer can’t do what we want because it takes far too long: millions of centuries, perhaps. Not much good buying a faster computer either: if it were a hundred times faster it would still take millions of years; even one a million times faster would take hundreds of years. That's what you call a hard problem – one where it takes far longer than the lifetime of the fastest computer imaginable to come up with a solution.
If you've ever written a text-based program or typed a formula in a spreadsheet, chances are that at some stage the system has told you there's an error and won't even attempt to follow your instructions.
These "syntax errors" are annoying messages that programmers become excruciatingly familiar with... it means that they didn't follow the rules somehow, even if it's just a tiny mistake.
When you try to compile or run the program, the computer will tell you that there's an error. If it's really helpful, it might even suggest where the error is, but it won't run the program until you fix it.
This might seem annoying, but in fact, by enforcing precision and attention to detail it helps pinpoint mistakes before they become bugs in the program that go undetected until someone using it complains that it's not working correctly.
Every computer device you have ever used, from your school computers to your calculator, has been using algorithms to tell it how to do whatever it was doing. Algorithms are a very important topic in Computer Science because they help software developers create efficient and error-free programs. The most important thing to remember about algorithms is that there can be many different algorithms for the same problem, but some are much better than others!
In this chapter, students will examine algorithms, including searching and sorting algorithms.
Programming--sometimes referred to as coding--is a nuts and bolts activity for computer scientists. While this chapter won't teach you how to program (we've given some links to sites that can do this in the introduction), we are going to look at what a programming language is, and how computer scientists breathe life into a language. From a programmer's point of view, they type some instructions, and the computer follows them. But how does the computer know what to do? Bear in mind that you might be using one of the many languages such as Python, Java, Scratch, Basic or C#, yet computers only have the hardware to follow instructions in one language: a very simple "machine code" that is difficult for humans to read and write. Then if you invent a new programming language, how do you tell the computer how to use it?
In this chapter, we'll look at what happens when you write and run a program, and how this affects the way that you distribute the program for others to use.
At the beginning of a new unit, we jump right into an activity - building a small arrangement of LEGO® blocks and then creating text instructions a classmate could follow to construct the same arrangement. Groups will trade instructions to see if they were clear enough to allow reconstruction of the original arrangement. The wrap-up discussion is used to highlight the inherent ambiguities of human language and call out the need for the creation of a programming language which leaves no room for interpretation.
Students will be able to:- assess the clarity of a set of instructions expressed in human language.- create a set of instructions in human language for building a simple LEGO block arrangement.- identify connections between the ability to program and the ability to solve problems.- describe the ambiguities inherent in human language and the ways programming languages seek to remove those ambiguities.
Note: You will need to create a free account on code.org before you can view this resource.
This is the second day of a three-lesson sequence in which we attempt to show the "art" of programming and introduce the connection between programming and algorithms. In the previous lesson, we established the need for a common language to express algorithms to avoid ambiguity in how instructions would be interpreted. In this lesson, we continue to establish the connection between programming and algorithms, with more emphasis on the "art" of algorithms.
First, students are presented with a new task for the “human machine” - to write a set of instructions to identify the smallest (lowest value) card in a row of cards on the table. Once again we try to establish a set of fundamental commands for doing this and develop a more formal set of “low-level” commands for manipulating playing cards. Students are presented with a "Human Machine Language" that includes five commands and then must figure out how to use these primitive commands to “program” the same algorithm.
At the conclusion, several points about programming can be made, namely:
1. Different algorithms can be developed to solve the same problem.
2. Different programs can be written to implement the same algorithm.
Students will be able to:- trace programs written in the "Human Machine Language".- develop an algorithm to find the smallest playing card in a row of cards- express an algorithm in the "Human Machine Language".- identify the properties of sequencing, selection, and iteration the "Human Machine Language".- evaluate the correctness of algorithms expressed in the "Human Machine Language".
This is the third of three lessons that make the connection between programming and algorithms. In this lesson, students continue to work with the "Human Machine Language" to get creative designing more algorithms for playing cards. One command is added to the language from the previous lesson (SWAP) that allows positions of cards to change. With the addition of swap, the challenge is to design an algorithm that will move the minimum card to the front of the list while keeping the relative order of all the other cards the same. If that is achieved some other Human Machine Language challenges are available.
Students will be able to:- develop an algorithm to solve a new problem with playing cards.- express an algorithm in the Human Machine Language.- identify Sequencing, Selection, and Iteration in a program written the Human Machine Language.- describe the properties of the Human Machine Language that make it a "low level" language.
This lesson is a student's first exposure to programming in App Lab. The lesson begins with a quick reflection prompt. Then students are introduced to the practice of pair programming before beginning to program. For this lesson, the students' view is limited to only a very few simple “turtle” commands to draw graphics on the screen. After a few warm-up exercises, using only combinations of four drawing commands, students must figure out the most “efficient” way to draw an image of a 3x3 grid. The lesson concludes with a sense-making discussion about the meaning of efficiency in programming and the reason behind beginning with such a limited set of programming tools.
Students will be able to:- use App Lab to write programs that create simple drawings with “turtle graphics.”- create a program with a partner following the pair programming model.- explain different ways one might measure the efficiency of a program.
In this lesson, students learn to define and call procedures (in JavaScript, procedures are called “functions”) in order to create and give a name to a group of commands for easy and repeated use in their code. They will be introduced to functions as a form of abstraction that enables them to write code in larger, more logical chunks and focus on what something does, rather than how it does it. As they explore the use of functions through a sequence of activities in App Lab, they will be asked to think about where they see the need for functions and how these functions can make their code clearer or more concise.
At the end of the lesson, students review the concept of abstraction and are introduced to elements of the Create PT in preparation for the Practice PT at the end of the unit.
Students will be able to:- recognize functions in programs as a form of abstraction.- write a program that solves a turtle drawing problem using multiple levels of abstraction (i.e. functions that call other functions within your code).- explain why and how functions can make code easier to read and maintain.- define and call simple functions that solve turtle drawing tasks.
This lesson presents a top-down problem-solving strategy for designing solutions to programming problems. Students use a worksheet to learn about top-down design, and then on paper, design a solution to a new turtle drawing challenge with a partner. Having practiced this approach on paper and in code, students will be presented again with the 3x3 square challenge from an earlier lesson and asked to improve upon their old solution by designing multiple layers of functions.
Students will be able to:- write a complete program with functions that solve sub-tasks of a larger programming task.- explain how functions are an example of abstraction.- use a “top-down” problem-solving approach to identify sub-tasks of a larger programming task.
Students will learn to read App Lab’s API documentation and will use functions that accept parameters in order to complete a series of drawing puzzles which require them to make use of the App Lab API documentation to learn new drawing commands. Many of these commands will require the use of parameters. The final challenge asks students to design a personal monogram making use of the commands they learned during the lesson.
Students will be able to:- use parameters to provide different values as input to procedures when they are called in a program.- use API documentation to assist in writing programs.- define an API as the set of commands made available by a programming language.
In this lesson, students practice using and creating functions with parameters. Students learn that writing functions with parameters can generalize solutions to problems even further. Especially in situations where you feel like you are about to duplicate some code with only a few changes to some numbers, that is a good time to write a function that accepts parameters. In the second half of the lesson, students make a series of modifications to a program that creates an “Under the Sea” scene by adding parameters to functions to more easily add variation to the scene. Lastly, students are introduced to App Lab’s random number functions to supply random values to function calls so the scene looks a little different every time the program runs.
Students will be able to:- write functions with parameters to generalize a solution instead of duplicating code.- identify appropriate situations for creating a function with parameters.- use random numbers as inputs to function calls for the purpose of testing.- add parameters to a function in an existing piece of code to generalize its behavior.
Students learn to use random values and looping to create variation in their drawings and quickly duplicate objects they wish to appear in their digital scenes many times. Students will be presented with a version of the for loop which only enables them to change the number of times the loop runs. This block is essentially a "repeat" block and will be presented that way. Students will also be presented with blocks which enable them to choose a random number within a given range. Together these blocks enable students to create more complex backgrounds for digital scenes by randomly placing simple objects within the background of their scene. Students use these tools to step through the Under the Sea exemplar digital scene.
Students will be able to:- use a loop in a program to simplify the expression of repeated tasks.- identify appropriate situations in a program for using a loop.- use random values within a loop to repeat code that behaves differently each time it is executed.
This lesson attempts to walk students through the iterative development process of building an app (basically) from scratch that involves the use of if statements. Following an imaginary conversation between two characters - Alexis and Michael - students follow the problem solving and program design decisions they make for each step of constructing the app. Along the way, they decide when and how to break things down into functions, and of course, discuss the logic necessary to make a simple game.
if
The last step - writing code that executes an end-of-game condition - students must do on their own. How they decide to use if statements to end the game will require some creativity. The suggested condition - first to score 10 points - is subtly tricky and can be written in many different ways.
At the conclusion of the lesson, there is three practice Create PT-style questions as well as resources explaining the connection between this lesson and the actual Create PT. Depending on how you use these materials they can easily add an additional day to this lesson.
Students will be able to:- write code to implement solutions to problems from pseudocode or description.- follow the iterative development process of a collaboratively created program.- develop and write code for conditional expressions to incorporate into an existing program.- write a large program from scratch when given directions for each step.
This lesson demonstrates how a slight manipulation of a conditional statement can allow for the creation of a new and powerful tool in constructing programs, a while loop. Students are introduced to a while loop by analyzing the flow chart of a conditional statement in which the "true" branch leads back to the original condition. Students design their own flowcharts to represent a real-world situation that could be represented as a while loop, and they learn how to recognize common looping structures, most notably infinite loops. Students then move to App Lab, creating a while loop that runs exactly some predetermined number of times. While learning about creating while loops, students will be introduced to many of the common mistakes early programmers make with while loops and will be asked to debug small programs. They finally progress to putting if statements inside a while loop to count the number of times an event occurs while repeating the same action. This activity will recall the need for counter variables and foreshadows their further use in the following lesson.
Students will be able to:- explain that a while loop continues to run while a boolean condition remains true.- translate a real-life activity with repeated components into a form that could be represented by a while loop.- analyze a while loop to determine if the initial condition will be met, how many times the loop will run, and if the loop will ever terminate.- write programs that use while loops in a variety of contexts.
In this lesson, students are introduced to the return command and learn to write their own functions that return values. Students first complete a simple unplugged activity based on the game Go Fish to introduce the concept of a return value. They will then complete a short sequence of exercises in Code Studio, which introduces preferred patterns for writing functions that return values. At the end of the sequence, students write and use functions that return values in a simple turtle driver app.
Students will be able to:- use the return command to design functions.- identify instances when a function with a return value can be used to contain frequently used computations within a program.- design functions that return values to perform frequently needed computations within a program.
