Friends! In the introduction, we will remind you (or tell you whoever) about the structure of the CS50. The course lasts 12 weeks. Every week there are two lectures, as well as all sorts of seminars and explanations. We will publish articles like this one as soon as the lectures are ready. It will contain a brief description of the lectures, notes on “shorts” and additional information, as well as translations of practical assignments. The zero week lectures covered the following issues:
Binary number system.
ASCII
Algorithms and algorithmic thinking
Compilers
Scratch language
Boolean Expressions
Conditions
Cycles
Variables
Functions
Arrays
Streams
Events
Week 0 goals:
Understand how information can be represented digitally.
Learn basic software constructs and concepts.
Create your own animation, game or interactive activity using Scratch.
Impress your friends =).
CS50 Week 0 (Lecture 1-2): notes
Algorithms
We hope you have already watched the lectures and understood that the algorithm breaks down the solution of problems (various problems, mathematical ones or “how to get to metro station N”) into steps. Moreover, each step must be completed in a finite amount of time, and there must be a certain number of steps themselves. Also, the next step depends on the previous one. You can read more about algorithms, for example, here . If you know English, here is a wonderful TED animation by David Malan: https://youtu.be/6hfOvs8pY1k Although in general the information in the video repeats that in the lecture =).
Binary number system
We have 10 fingers and the system is decimal. That is, we can represent any number, no matter how large, using the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Depending on where the number is in the number, it can mean different things : if this digit is the last, then it is located in the units place, the penultimate one is in the tens place, even further to the left is in the hundreds place, and so on. Essentially, any number can be written as a sum of digits, each of which is multiplied by ten to a certain power. In the case of units - zero. For example, 1573 = 3*10 0 + 7*10 1 +5*10 2 +1*10 3 . The number by which the digits are multiplied is called the base of the number system. For the decimal system, the base is logically ten. The computer has no fingers, but there are two states: conditionally “current is flowing” and “current is not flowing”, zero and one. Accordingly, all numbers (and information in general) in computer memory consist of only two digits - 0 and 1. Their location, as in the case of the decimal number system, indicates the digit. Only now the number can be decomposed into the sum of digits multiplied not by powers of ten, but by powers of two. 0 in binary = 0 1 in binary = 1 2 in binary = 10 7 10 =111 2 Learn to convert from binary to decimal. You probably already understand how this is done - we simply take the digit of the number starting from the rightmost one and multiply it by the base to the power corresponding to its digit, and add everything up with each digit. Example: Let's find the decimal analogue of the binary number 101101 2 The rightmost one = 1*2 0 The next zero = 0*2 1 The third one from the right = 1*2 2 The fourth one = 1*2 3 ... and so on 101101 2 = 1*2 0 + 0*2 1 + 1*2 2 + 1*2 3 + 0*2 4 + 1*2 5 = 1 + 0 + 4 + 8 + 0 + 32 = 45 10 Imagine eight light bulbs arranged in a row. Each of them has its own switch. Each of the light bulbs is a discharge. What can you imagine, remember the very first lecture (there is such a device there) or here is a widget for you: http://cdn.cs50.net/2016/x/psets/0/pset0/bulbs.html Play with it, practice “feeling” it binary system. Converting from decimal to binary. Here, too, everything is very simple, if you understand the essence. Here we have the number 57 10 . To convert it to the binary system, you need to determine what maximum power of two does not exceed this number. 2 6 = 64. This is clearly too much. But 2 5 = 32. Now we have determined the most significant digit. 32 10= 100000 2 . Now we are looking for the next digit. 57-32 = 25. Now for 25 we are looking for a power of two that does not exceed 25. 2 4 = 16. This means that our next digit is also equal to 1. 32+16 = 48 10 = 110000 2 . 57 – 48 = 9. 2 3 = 8, this is less than 9. This means the next digit will also be one. 32 + 16 + 8 = 56 10 = 111000 2 . 57-56 = 1, that is, there is only one power left, 2 0 . Thus 57 10 = 111001 2 . If suddenly something remains unclear, you can read more in the Wikibook, and if you are strong in English, here is a small addition to the lecture.
ASCII
The computer only understands zeros and ones, and its memory can be represented as a very long string of light bulbs with switches, as you saw above. We already understand how to represent numbers in a computer. What about the rest of the information? Letters, pictures? Let's say there are 26 letters in the English alphabet. That is, theoretically, we can represent letters with numbers from 0 to 25, only in the binary system. The following question arises: how can we understand whether we have a lowercase letter or an uppercase one? What about punctuation marks? Invisible signs like spaces? In short, we need a coding system, Cap! In the 1960s, there were many different schemes that encoded characters. The lack of uniformity proved to be a problem, and in 1963, the American Standards Institute, ANSI, developed and introduced the ASCII (American Standard Code for Information Interchange) encoding scheme. Each ASCII character consists of seven bits, or seven bits, each of which can take the value 0 or 1. 7 bits can hold numbers from 0 to 127 in binary, meaning we have 128 numbers to encode characters. It would seem that this is enough to encode written English speech? Let's count: az - 26 options AZ - 26 more 0-9 - 10 ,;:~& and other punctuation marks - 32 And one more space. Total - 95 characters. The remaining 33 vacant options are used for so-called control characters, such as line feed or carriage return: https://ru.wikipedia.org/wiki/ASCII#/media/File:ASCII_Code_Chart.svg It is important to distinguish between characters 0-9 and numeric values 0 -9. Characters 0-9 are represented by ASCII values 48-57. It's interesting to note that the rightmost four bits of these ASCII values are binary representations of the numeric values 0-9. This somewhat simplifies the way to convert between ASCII values and their actual numeric values. Let's start programming?
Scratch
So, Scratch. You were told about this visual programming language and its basic commands in the lecture. To try out Scratch for yourself, follow the link and click “Join”. Once registered, you can start programming online. Yes, by the way, today Scratch is partly Russified. The help, however, is still in English. If you wish, you can play and also look at the code of student projects that were demonstrated in the lecture. Here's Pikachu Pastry Catch . Or a project with sorting waste into different containers: https://scratch.mit.edu/projects/71161586/ David and the company ask you not to worry if you think that you cannot do such complex projects: this level already requires some skill .
Exercise
To better understand the processes that happen in Scratch, you can download the source code for several projects from here . Play around and see. Learning someone else's code is very useful. This is one of the best ways to find out what is inside those programs that you yourself have not yet matured into. Once you begin to understand how these applications work, you can safely move on.
Now it's time to do something yourself. The challenge is to have fun while also implementing a small project from scratch. It could be animation, game, interactive action.
Project requirements:
The program must contain at least two sprites (characters, images), and one of them must definitely not be a cat =).
There must be at least three scripts (actions).
At least one condition, one loop, and one variable must be executed.
At least one sound must be included in the program.
That is, in essence, your project will be more complex than those written in the lecture, but simpler than the demonstrated toys about Pikachu and garbage collection. So your project will probably use several dozen puzzles that make up the Scratch code. If something doesn't work out, you may need to change your approach to solving the problem. The main thing is to go without fear! We invite you to ask questions and share your projects in the comments.
Scratch: a quick guide to action
The sprite is the central object of the project. Any character - a cat, a plane, a ball - is a sprite. If you added two different cats, these are two different sprites. Each sprite has scripts that describe its behavior. These are action blocks. Costumes are what objects look like. The sprites themselves are essentially just drawings. Each sprite can have multiple costumes. To create a sprite, you either need to select its original costume from the Scratch library, draw your own in the built-in editor, upload any image, or even take a photo using your webcam and upload it. All sprites are placed on the so-called stage. The stage is essentially our canvas, the setting for the program. You can also attach sounds from the library to a sprite or scene, or you can load them or record them yourself using a microphone. To start executing the program, you need to click on the green flag in the upper right corner of the scene window. But before doing this, you need to place the following block in the program: And attach some blocks to it, as to a designer part. For example: In this case, when you click on the flag, the sprite to which the actions are attached takes 50 steps and meows. We have a lot of blocks. They are divided into three tabs: scripts, costumes and sounds. Let's make a simple program with a condition. If it is fulfilled, the cat will meow; if it is not fulfilled, it will remain silent. Operators are indicated in green. Those that test whether a condition is true or false have sharp corners on the sides. Condition testing structures and loops are shown in orange. They have special holes where you can place other blocks.
Cycles:
Repeat an infinite number of times: Repeat something a certain number of times: Repeat an action if the condition is met: You can create variables in the Data block. In the example below, we created a variable x, and immediately there were actions that can be done with it. You can set the scope of variables: for all sprites or for one. The green flag is not the only action. Also in the Events section you can find a number of other control conditions. For example, you can choose what to do when you click on a button or on the sprite itself with the mouse. If you need additional information, you can find it, for example, here .
We hope you have already watched the lectures and understood that the algorithm breaks down the solution of problems (various problems, mathematical ones or “how to get to metro station N”) into steps. Moreover, each step must be completed in a finite amount of time, and there must be a certain number of steps themselves. Also, the next step depends on the previous one. You can read more about algorithms, for example, here . If you know English, here is a wonderful TED animation by David Malan: https://youtu.be/6hfOvs8pY1k Although in general the information in the video repeats that in the lecture =).
We have 10 fingers and the system is decimal. That is, we can represent any number, no matter how large, using the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Depending on where the number is in the number, it can mean different things : if this digit is the last, then it is located in the units place, the penultimate one is in the tens place, even further to the left is in the hundreds place, and so on. Essentially, any number can be written as a sum of digits, each of which is multiplied by ten to a certain power. In the case of units - zero. For example, 1573 = 3*10 0 + 7*10 1 +5*10 2 +1*10 3 . The number by which the digits are multiplied is called the base of the number system. For the decimal system, the base is logically ten. The computer has no fingers, but there are two states: conditionally “current is flowing” and “current is not flowing”, zero and one. Accordingly, all numbers (and information in general) in computer memory consist of only two digits - 0 and 1. Their location, as in the case of the decimal number system, indicates the digit. Only now the number can be decomposed into the sum of digits multiplied not by powers of ten, but by powers of two. 0 in binary = 0 1 in binary = 1 2 in binary = 10 7 10 =111 2 Learn to convert from binary to decimal. You probably already understand how this is done - we simply take the digit of the number starting from the rightmost one and multiply it by the base to the power corresponding to its digit, and add everything up with each digit. Example: Let's find the decimal analogue of the binary number 101101 2 The rightmost one = 1*2 0 The next zero = 0*2 1 The third one from the right = 1*2 2 The fourth one = 1*2 3 ... and so on 101101 2 = 1*2 0 + 0*2 1 + 1*2 2 + 1*2 3 + 0*2 4 + 1*2 5 = 1 + 0 + 4 + 8 + 0 + 32 = 45 10 Imagine eight light bulbs arranged in a row. Each of them has its own switch. Each of the light bulbs is a discharge. What can you imagine, remember the very first lecture (there is such a device there) or here is a widget for you: http://cdn.cs50.net/2016/x/psets/0/pset0/bulbs.html Play with it, practice “feeling” it binary system. Converting from decimal to binary. Here, too, everything is very simple, if you understand the essence. Here we have the number 57 10 . To convert it to the binary system, you need to determine what maximum power of two does not exceed this number. 2 6 = 64. This is clearly too much. But 2 5 = 32. Now we have determined the most significant digit. 32 10= 100000 2 . Now we are looking for the next digit. 57-32 = 25. Now for 25 we are looking for a power of two that does not exceed 25. 2 4 = 16. This means that our next digit is also equal to 1. 32+16 = 48 10 = 110000 2 . 57 – 48 = 9. 2 3 = 8, this is less than 9. This means the next digit will also be one. 32 + 16 + 8 = 56 10 = 111000 2 . 57-56 = 1, that is, there is only one power left, 2 0 . Thus 57 10 = 111001 2 . If suddenly something remains unclear, you can read more in the Wikibook, and if you are strong in English, here is a small addition to the lecture.
The computer only understands zeros and ones, and its memory can be represented as a very long string of light bulbs with switches, as you saw above. We already understand how to represent numbers in a computer. What about the rest of the information? Letters, pictures? Let's say there are 26 letters in the English alphabet. That is, theoretically, we can represent letters with numbers from 0 to 25, only in the binary system. The following question arises: how can we understand whether we have a lowercase letter or an uppercase one? What about punctuation marks? Invisible signs like spaces? In short, we need a coding system, Cap! In the 1960s, there were many different schemes that encoded characters. The lack of uniformity proved to be a problem, and in 1963, the American Standards Institute, ANSI, developed and introduced the ASCII (American Standard Code for Information Interchange) encoding scheme. Each ASCII character consists of seven bits, or seven bits, each of which can take the value 0 or 1. 7 bits can hold numbers from 0 to 127 in binary, meaning we have 128 numbers to encode characters. It would seem that this is enough to encode written English speech? Let's count: az - 26 options AZ - 26 more 0-9 - 10 ,;:~& and other punctuation marks - 32 And one more space. Total - 95 characters. The remaining 33 vacant options are used for so-called control characters, such as line feed or carriage return: https://ru.wikipedia.org/wiki/ASCII#/media/File:ASCII_Code_Chart.svg It is important to distinguish between characters 0-9 and numeric values 0 -9. Characters 0-9 are represented by ASCII values 48-57. It's interesting to note that the rightmost four bits of these ASCII values are binary representations of the numeric values 0-9. This somewhat simplifies the way to convert between ASCII values and their actual numeric values. Let's start programming?
So, Scratch. You were told about this visual programming language and its basic commands in the lecture. To try out Scratch for yourself, follow the link and click “Join”. Once registered, you can start programming online. Yes, by the way, today Scratch is partly Russified. The help, however, is still in English. If you wish, you can play and also look at the code of student projects that were demonstrated in the lecture. Here's Pikachu Pastry Catch . Or a project with sorting waste into different containers: https://scratch.mit.edu/projects/71161586/ David and the company ask you not to worry if you think that you cannot do such complex projects: this level already requires some skill .
Each sprite has scripts that describe its behavior. These are action blocks. Costumes are what objects look like. The sprites themselves are essentially just drawings. Each sprite can have multiple costumes. To create a sprite, you either need to select its original costume from the Scratch library, draw your own in the built-in editor, upload any image, or even take a photo using your webcam and upload it. All sprites are placed on the so-called stage. The stage is essentially our canvas, the setting for the program. You can also attach sounds from the library to a sprite or scene, or you can load them or record them yourself using a microphone. To start executing the program, you need to click on the green flag in the upper right corner of the scene window. But before doing this, you need to place the following block in the program: 
And attach some blocks to it, as to a designer part. For example: 
In this case, when you click on the flag, the sprite to which the actions are attached takes 50 steps and meows. We have a lot of blocks. They are divided into three tabs: scripts, costumes and sounds. Let's make a simple program with a condition. If it is fulfilled, the cat will meow; if it is not fulfilled, it will remain silent. Operators are indicated in green. Those that test whether a condition is true or false have sharp corners on the sides. Condition testing structures and loops are shown in orange. They have special holes where you can place other blocks.
Repeat something a certain number of times: 
Repeat an action if the condition is met: 
You can create variables in the Data block. In the example below, we created a variable x, and immediately there were actions that can be done with it. You can set the scope of variables: for all sprites or for one. 
The green flag is not the only action. Also in the Events section you can find a number of other control conditions. For example, you can choose what to do when you click on a button or on the sprite itself with the mouse. If you need additional information, you can find it, for example, here .
GO TO FULL VERSION