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.
We’re going to take a step back from programming and discuss the person who formulated many of the theoretical concepts that underlie modern computation - the father of computer science himself: Alan Turing. Normally, we try to avoid “Great Man" history in Crash Course because, truthfully, all milestones in humanity are much more complex than an individual or single lens.
Often files are way too large to be easily stored on hard drives or transferred over the Internet - the solution, unsurprisingly, is to make them smaller. Today, we’re going to talk about lossless compression, which will give you the exact same thing when reassembled, as well as lossy compression, which uses the limitations of human perception to remove less important data. From listening to music and sharing photos, to talking on the phone and even streaming this video right now the ways we use the Internet and our computing devices just wouldn’t be possible without the help of compression.
This video will talk about how we organize the data we use on our devices. You might remember last episode, Intro to Algorithms: Crash Course Computer Science #13, we walked through some sorting algorithms, but skipped over how the information actually got there in the first place! And it is this ability to store and access information in a structured and meaningful way that is crucial to programming. From strings, pointers, and nodes, to heaps, trees, and stacks, get ready for an ARRAY of new terminology and concepts.
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.
Computers draw lines and circles during many common tasks, such as using an image editor. But how does a computer know which pixels to darken to make a line?
Students will discover two common algorithms used to draw a line between two points and a circle of a given radius.
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.
This chapter is about guarding against errors in data in its many different forms — data stored on a hard drive, on a CD, on a floppy disk, on a solid state drive (such as that inside a cellphone, camera, or MP3 player), data currently in RAM (particularly on servers where the data correctness is critical), data going between the RAM and hard drive or between an external hard drive and the internal hard drive, data currently being processed in the processor or data going over a wired or wireless network such as from your computer to a server on the other side of the world. It even includes data such as the barcodes printed on products or the number on your credit card.
If we don't detect that data has been changed by some physical problem (such as a small scratch on a CD, or a failing circuit in a flash drive), the information will just be used with incorrect values. A very poorly written banking system could potentially result in your bank balance being changed if just one of the bits in a number was changed by a cosmic ray affecting a value in the computer's memory! If the barcode on the packet of chips you buy from the shop is scanned incorrectly, you might be charged for shampoo instead. If you transfer a music file from your laptop to your MP3 player and a few of the bits were transferred incorrectly, the MP3 player might play annoying glitches in the music. Error control codes guard against all these things, so that (most of the time) things just work without you having to worry about such errors.
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.
