Week 1 History and Fundamental Principles Part 1 CS 100 PRINCIPLES OF COMPUTING Dr Ghada Abdelmoumin TOPICS AND AGENDA Class Introduction Syllabus Overview CANVAS Walkthrough Discuss Logistics Piazza What is computing What is computation What is a computer Principles Algorithms Computability Data Structure and Automation History Computer evolution Beautiful minds A life investment in your future A framework by Mason to become Creativity Abstraction Data Algorithms Programming Internet and Societal Impact MASON CORE Better scholar Better professional Better citizen Better thinker Better communicator Better Citizen Better Future Through this course you are going to develop computational thinking What is computational thinking Check Learning com Creating a sequence of instructions to solve a problem MASON CORE Decomposition Break complex problems into small manageable problems Pattern recognition Find similarities among and within problems Abstraction Focus on the important information and ignore irrelevant details Algorithm Develop a step by step solution to the problem Source BBC BITSIZE Computational Thinking Techniques Image is a courtesy of BBC BITSIZE FUNDAMENTAL CONCEP TS Computing Computer Computation Computability Algorithm Self learned Explore on your own Data Structure Automation FUNDAMENTAL CONCEP TS Computing The use or the operation of a computer Oxford Dictionary The study or use of computers Cambridge Dictionary In a general way we can define computing to mean any goal oriented activity requiring benefiting from or creating computers Brookshear Synonymous counting and calculating Thesaurus Computer Science An Overview by J Glenn Brookshear and Dennis Brylow FUNDAMENTAL CONCEP TS Computation The action of mathematical calculation Oxford Dictionary The act or action of computing Cambridge Dictionary A process evoked when a computational agent acts on its inputs under the control of an algorithm ACM Peter J Dennings argues in his opening statement that It is one of those questions that will never be fully settled be cause new discoveries and maturing understandings consta ntly lead to new insights and questions about existing model s It is like the fundamental questions in other fields for example what is life AN ALGORITHM Algorithms are the recipes that feed the hungry machines some are quick snacks others are elaborate ten course meals Documentary Film Al Khawarizmi Father of Mathematics and Computers Source Medium Computer Science Basics Algorithms AN ALGORITHM Abdullah Muhammad bin Musa al Khwarizmi 780 850 a Persian Muslim scholar who invented the Arabic numeral system Examine the image below Can you tell what is the algorithm he used to simplify counting AN ALGORITHM Problem 1 Make a Peanut Jelly Sandwich Approach Computational Thinking Decomposition Pattern Recognition Abstraction Algorithm Means Algorithmic thinking Step by Step Instructions End Source Inspirit Scholars Begin 1 Put two pieces of bread on a plate 2 Use a knife to spread peanut butter onto one piece of bread 3 Use a knife to spread jelly onto the other piece of bread 4 Put the pieces of bread together to make a sandwich 5 Take a bite AN ALGORITHM Problem 1 Make a Falafel Sandwich Approach Computational Thinking Decomposition Pattern Recognition Abstraction Algorithm Means Algorithmic thinking Step by Step Instructions Begin End 1 Put two pieces of bread on a plate 2 Use a knife to spread peanut butter onto one piece of bread 3 Use a knife to spread jelly onto the other piece of bread 4 Put the pieces of bread together to make a sandwich Source Inspirit Scholars AN ALGORITHM Problem 2 Finding the cost of shirts The shirt you want to buy from Amazon costs 12 00 How much will 2 of those shirts cost What computation do we have to do 1 cost of shirt 2 12 Al Khw rizm for finding the cost What would a general algorithm look like for any number of those shirts 1 cost of shirt shirt 12 What would a generalizing algorithm look like for any number of those shirts 1 cost of shirt shirt cost Sources Dr Zaman s and Dr Kamberi s slides Begin End Begin End Begin End AN ALGORITHM Problem 2 Finding the square root What is the square root of 18 What computation do we have to do Al Khw rizm for finding the square root Begin 1 Pick any number X a guess 2 Repeat 1 Calculate 2 Set 3 If the results is close enough 2 1 2 1 Stop End What would a generalizing algorithm look like for any number Can you solve for 18 AN ALGORITHM Problem 2 Finding the square root Can you solve for 18 Begin 1 Pick any number X a guess 2 Repeat 1 2 1 Calculate 2 Set 3 If the results is close enough 2 1 Stop End 1 S 18 2 x 4 the input some guess 3 one iteration of the algorithm 4 xnext x s x 5 xnext 4 18 4 6 if x 2 is close to S then 7 quit x 4 25 x2 S 0 0625 Quit No try one more iteration AN ALGORITHM Problem 2 Finding the square root Can you solve for 18 Begin 1 Pick any number X a guess 2 Repeat 1 2 1 Calculate 2 Set 3 If the results is close enough 2 1 Stop End Can you solve for 1 Pick a Guess x 3 1 S 18 2 x 4 25 the input after one iteration 3 second iteration of the algorithm 4 xnext x s x 5 xnext 4 25 18 4 25 6 if x 2 is close to S then 7 quit x 4 24264 x2 S 0 000054 Quit AN ALGORITHM Problem 3 Calculate the Trajectory One computer scientist wants to launch a t shirt into the hands of a person on stage What is the launch angle Begin 1 Look the algorithm up Al Khw rizm for finding the trajectory 2 Device a step by step solution End Given 1 Distance from Gosling to Ellison 80 m 2 Stage elevation 2 m 3 T shirt speed at launch 20 m sec Sources Dr Soundararajan s slides Can you write the step by step solution AN ALGORITHM A recipe to perform a calculation with numbers Turing Revolution A finite set of instructions carried out in a specific order to perform a particular task simplilearn The question is Who write these instructions People AI If so who carries out these instructions The Computer The most important question are all tasks computable Computability COMPUTABILIT Y Hilbert A mathematical problem is computable if it can be solved in principle by a computing device Literally all mathematical problems were solvable Computability G del Turing and Church 1930 Not really Turing 1936 clearly and abstractly thought about what it means for a machine to carry out a computational task Aha The Turing Machines TM TM is a simple abstract computational devices to help investigate the extent and limitation of what can be computed Stanford