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, betw