NUSH CS1131 Notes

CS1131 Notes Computational Thinking I Chapters 2 thru 12 This is a compilation of concepts taught in CS1131. Made by LQ who is very stressed and tired and depressed right now Links of All LQ Notes: LQ Notes Links Document Topic Topic 1: Algorithms Topic 2: Number Bases Topic 3: Turtle Topic 4: For Loops and Variables Topic 5: If Statements Topic 6: Excel Disclaimer References from NUS High CS1131 Coursemology are made. Hence, please do not share this set of notes outside of your NUS High Y1 Schoolmates. Take everything in this set of notes with a pinch of salt as there is neither enough time nor manpower to check through the notes fully. The order of topics in this set of notes is not completely accurate to how they were taught in Labs, but should contain similar content. If you spot any mistakes, please do inform me if you can. Thanks :) All the best for your exams! ~LQ (24 Sep)

Topic 1: Algorithms In CS1131, 2 main types of algorithms are covered - Linear Search, and Binary Search. 1.1 What is an algorithm? An algorithm is a step by step list of instructions that, if followed exactly, will solve the problem under consideration . An algorithm should be exact (i.e. the result produced should perfectly solve the problem), general (i.e. the algorithm should not fail to function for any specific input), and should terminate (i.e. the algorithm will eventually finish running). However, an algorithm isn’t necessarily fast. 1.2 Linear Search A linear search is simply searching for the value by going through each possible value one by one . Consider the following problem: Problem A computer chooses a number at random, between 1 and 10, inclusive. You get to input a number, and the computer will tell you if the number is correct or wrong. How should you obtain the correct number? Solution In this case, we can perform Linear Search. We first check if the number is 1. If the computer says that it’s wrong, we continue by checking 2, then 3, and as such until we reach the correct number. This is Linear Search. 1.3 Binary Search Binary Search works on a problem where you know if your guess is too high, too low, or correct. We can check the mid-value of the possible range, and as such reduce the range by half accordingly. This sounds complicated at first, but it is better illustrated with an example and a diagram. Consider the following problem:

Problem A computer chooses a number at random, between 1 and 16, inclusive. You get to input a number, and the computer will tell you if the number is too high, too low, or correct. How should you obtain the correct number? Solution In this case, we can perform Binary Search. Let’s assume the computer chose 13. First, we check the mid-value of the range, 1 to 16. The mid-value is 8. The computer will say it’s too low. Now, the possible range is from 9 to 16. Hence, we check the new mid-value, 12. The computer then says it’s still too low. We then continue repeating this process, halving the possible range each step, until we reach the answer. This is what it will look like, illustrated: Blue refers to the possible values, green is the correct value, and orange is the value we’re guessing currently. Note that Linear Search could still be applied here, but it will take much longer, on average. This is Binary Search.

Topic 2: Number Bases Bases? Like… Acids and Bases? No, not that. Number Bases are essentially different ways to represent a number. 2.1 Decimal (Base-10) The base system we use on a day-to-day basis is called the decimal number system. Since deci means 10, it means that the decimal system is made of 10 digits (i.e. from 0 to 9). We also call the decimal number system the base-10 number system. Hence, we denote numbers written in base-10 with a subscript “10” when dealing with multiple types of bases, to avoid confusion. (e.g. 63 10 ) 2.2 Binary (Base-2) The Binary number system, or base-2 number system, only has 2 digits, 0 and 1. This is the system computers use to store data, and is what allows most, if not all electronics to work. To figure out what binary numbers mean, we first need to know how decimal numbers work. As shown below, we can break down a number like 6942 into a single digit, multiplied by a power of 10. This is how binary numbers work, too, but instead of powers of 10, it uses powers of 2 (Hence, base-2). In decimal, 1000 represents 10 3 , since there are 3 trailing zeros. However, in binary, 1000 will represent 2 3 , or 8. In this similar fashion, we can construct the following table: Binary Decimal

1 1 10 2 100 4 1000 8 10000 16 100000 32 1000000 64 10 n 2 n Now, let’s try translating 101 2 into decimal. Note: we denote binary numbers with a subscript “2”, like 101 2 , to avoid confusion. Solution: 101 2 = 100 2 + 1 2 = 4 10 + 1 10 = 5 10 To convert a decimal number into binary, we do the same thing, but in reverse. We break down the number into its powers of 2, Take the example 69 10 . Solution: 69 10 = 64 10 + 4 10 + 1 10 = 1000000 2 + 100 2 + 1 2 = 1000101 2 2.3 Octal (Base-8) The octal base system, or base-8 system, consists of the digits 0 to 7. It functions on a similar logic to how base-2 and base-10 systems work. Recall how in base-2, each new place value is a new power of 2. In base-8, it would be a new power of 8 instead. Octal Decimal

1 1 10 8 100 8 2 1000 8 3 10 n 8 n It is worth noting that if you have something like 30 8 , it simply means 3 8 × 10 8 . (which is equivalent to 3 10 × 10 8 ) Let’s try translating 514 8 into decimal. Solution: 514 8 = 5 8 × 100 8 + 1 8 × 10 8 + 4 8 × 1 8 = 5 10 × 64 10 + 1 10 × 8 10 + 4 10 × 1 10 = 320 10 + 8 10 + 4 10 = 332 10 2.3 Hexadecimal (Base-16) The hexadecimal base system, or base-16 system, consists of the digits 0 to 9, as well as the letters A to F. It functions on a similar logic to how base-2 and base-10 systems work. Hexadecimal Decimal A 10 B 11 C 12 D 13 E 14 F 15 Again, recall how in base-2, each new place value is a new power of 2. In base-16, it would be a new power of 16 instead. Everything else follows the same logic.

Topic 3: Turtle (hmph mewos are better than turtles) Turtle is a commonly used (and very useful) python library . It contains code written by someone else that you can use to draw certain graphics. 3.1 Basic Turtle Functions Here are a few basic turtle functions. Before coding, we should always write import turtle to