CMSC 11_ Notes.pdf

CMSC 11 - 2 (Lecture) Introduction to Computer Science UNIT 1: THE WAY OF THE PROGRAM, VARIABLES, EXPRESSIONS, AND i. Simple problems are not solvable by any STATE...

CMSC 11 - 2 (Lecture) Introduction to Computer Science UNIT 1: THE WAY OF THE PROGRAM, VARIABLES, EXPRESSIONS, AND i. Simple problems are not solvable by any STATEMENTS algorithm. ii. Problems are intractable. “ Think like a Computer Scientist “ iii. Algorithm take too long or require too much memory to solve problems. Computer Scientist as: Mathematicians: Use formal languages to (c) Experimentation denote ideas (computations) - scientists rely on this when problems Engineers: Design things, assembling are too complex or ill-defined to lend components into systems and evaluating trafeoffs to analysis. among alternatives - this is where they implement Scientists: Observe behavior of complex systems and study resulting systems, form hypotheses, and test predictions. behavior. - it is needed to verify and refine the PROBLEM SOLVING analysis. - Most Important Skill of a Computer Scientist - The ability to: COMPUTING - formulate problems - this is where the skills and knowledge of - Think creative solutions computer science is being applied. - Express solutions clearly & accurately Examples: - Best way to practice this skill is through the mobile computing process of learning to program networking human-computer interaction Edsger Disjktra artificial intelligence - A famous computer scientist computational science (using - “Computers are to Computer Science what powerful computes to model telescope are to astronomy” scientific processes) databases and data mining Computer Scientists software engineering - uses numerous techniques of investigation web and multimedia design to answer fundamental question of management information systems computer science computer security THREE (3) MAIN TECHNIQUES PYTHON PROGRAMMING LANGUAGE (a) Design Python - one way of demonstrating a problem - an example of a high-level programming can be solved language. - Develop solution - an interpreted language; Python - Algorithm: a step-by-step process programs are executed by an interpreter. for achieving the desired result High-level language (b) Analysis - portable - the process of examining algorithms - can run on different kinds of computers with and problems mathematically few or no modifications - important part of computer science Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science  TWO (2) PROGRAMS THAT PROCESS - Bugs: programming errors (HIGH-LEVEL LANGUAGE TO LOW-LEVEL - the process of tracking bugs / programming LANGUAGE): errors down. Interpreter - reads a high-level program and executes it. THREE (3) KINDS OF ERRORS - does what the program says - processes the program a little at a time, 1. SYNTAX ERROR alternately reading and performing - Syntax: the structure of a program computations. and the rules about the structure - are produced when python is Compiler translating the source code into byte - reads the program and translates it code. completely before the program starts - indicates that there is something running. wrong with the syntax of the program. Source Code - the high level Example: - Incorrect indention Object Code - Single parenthesis - the translated program - Leaving out a symbol (colon, - the executable command or brackets) -------------------------------------------------------------------- - Misspelling a keyword - Missing a keyword What is program? - Else clause without an if - Leading zero in an integer Program - a sequence of instructions that specified [SyntaxError: invalid syntax] how to perform a computation: - mathematical; solving a system 2. RUNTIME ERROR equation or finding the roots of a - Errors that does not disappear until polynomial after the program has started - symbolic; searching and replacing running text in a document or compiling a - Rare in simple programs program (strangely enough) - Exceptions - indicate that something ❖ Input: exceptional (and bad) had get the data from the keyboard, a happened file, or some other device - Most messages include: ❖ Output: - Information about where the display data on the screen or send error occurred and what data to a file or other device functions were executing ❖ Conventional Execution: check for certain conditions and Example: execute the appropriate sequence of - Infinite recursion statements - Division by zero ❖ Repetition: perform some action - Performing an operation on repeatedly, usually with some variation incompatible types - Using identifier which has not DEBUGGING been defined Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science  - Accessing a list element or A. Assignment Statements dictionary value which - it creates a new variable and gives it doesn’t exist a value - Trying to access a file which Token - one of the basic elements of the doesn’t exist syntactic structure of a program, a word in a natural language Prevention: consider all possible values that a variable could contain especially when processing Augmented Assignment user input. - combines an assignment statement with an operator to make the 3. SEMANTIC ERROR statement more concise. - The meaning of the program (its semantics) is wrong. Augmented Assignment Operators - Identifying this can be tricky - It requires working backward by += looking at the output of the program -= and trying to figure out what it is *= doing. /= //= -------------------------------------------------------------------- %= **= BASICS OF PYTHON Print () B. Variable Names - a function that displays a result on the - Should be meaningful since they screen document what the variable is used - print statement for. Values and Types: General rule: Variable names can be as long as Value you like - one of the basic units of data (number or They can contain both letters and string) that a program manipulates. numbers Type They should not begin with a - a category of values number - type() It is legal to use uppercase letters, - can be used to identify a value in the but it is conventional to use only interpreter lower case for variable names The underscore character, _, can Example: appear in a name; often used in - int() names with multiple words such as - float() your_name or - str() airspeed_of_unladen_swallow Variable Do not use reserved keywords as - a name that refers to a value variable names - Manipulating variables; one of the most powerful features of programming Important Python 3 Keywords: language. False None Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science  True and D. Operators and Operands as assert Operators break - specials symbols that represent class computations. continue def del E. Order of Operations: Rules of elif Precedence else except Python follows PEMDAS: finally for Parentheses, Exponentiation, Negation, from Multiplication, Division, Integer Division, global Modulo, Addition, Subtraction if import F. String Operations in Addition & Multiplication is - work with strings lambda - perform concatenation & repetition nonlocal - use comma (,) to concatenate int() not & str() or pass G. Comments raise - are information in a program that is return meant for another programmers (or try anyone reading the source code). while - has no effect on the execution of the with program. yield - used for documenting source code. - starts with # - (single line) and ‘’’ - C. Expressions and Statements (block comment) Expression - a combination of values, variables, and operators. Example: - A value all by itself - A variable Statement - A unit of code that the Python interpreter can execute Example: - Print and Assignment Script - contains a sequence of statements. Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science  UNIT 2: FUNCTIONS >>> Before using the functions in the module, we first use the import statement to Function create the module object - named sequence of statements that performs a computation >>> After creating the module object, you - defined by specifying the name and the can access any of its functions or variables sequence of statements. by using this general format: - Format: name_of_function(argument) module_name.function_name() - ‘takes’ an argument and ‘returns’ a result module_name.variable Return value: result >>> Dot notation Argument: an expression that appears MATH MODULE between the parentheses of a function call - built-in python module that contains usual mathematical formulas and values int() function - converts values into integers COMPOSITION - throws an error if it cannot convert - how variables, expressions, and statements value to integer are combined - always rounds down - ability of programming languages where small building blocks are taken and WHY FUNCTIONS? composed together - You can put an arbitrary expression Creating a new function anywhere except: - gives you an opportunity to name a group the left side of an assignment of statements statement (has to be a variable - makes your program easier to read and name). debug any other expression on the left side is a syntax error Functions - can make a program smaller by eliminating CREATE YOUR OWN FUNCTIONS repetitive code Function definition Dividing a long program into functions - specifies the name of a new function and - allows you to debug the parts one at a the sequence of statements that execute time and then assemble them into a when the function is called working whole General format: Well designed functions def function_name(parameter): - are often useful for many programs. Once body_of_code you write and debug one, you can reuse it. def - keyword that indicates that this is a MODULE function definition - a file that contains a collection of related Function_name - name of the function that functions will be used to call it by (parameter) - the expected arguments that module object: contains the functions and it will take. Can be empty variables defined in the module Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science  body_of_code - composition of codes that - a box with the name of a function the function will do when called beside it and the parameter and variables of the function inside it. Rules for function names - frames are arranged in a stack that Letters, numbers, and underscore are legal, indicates which function called but first character cannot be a number which,and so on. Keywords should not be used as the name of a function Traceback Avoid having a variable and a function - Python prints the names of all the sharing the same name functions involved if an error occurs during a function call. FLOW OF EXECUTION FRUITFUL AND VOID FUNCTIONS Execution - always begins at the first statement of the program. Fruitful Functions Statements - are executed one at a time, in order - functions that return results from top to bottom. Example: the math function Function definitions - do not alter the flow of the - return value will cease to exist if it is program, but statements inside the function are not not assigned to a variable executed until the function is called. Function call - like a detour in the flow of Void Function execution. - functions that perform an action but don’t Instead of going to the next statement, the return a value flow jumps to the body of the function, runs Example: the print_lyrics() functions the statements there, and then comes back - if assigned to a variable, that to pick up where it left off. variable will hold the special value None PARAMETER AND ARGUMENTS Parameter - a variable in a function definition a placeholder does not have a concrete value Argument - value passed when a function is called Function parameters and variables are local - meaning they only exist and are accessible inside of the function definition Stack Diagrams - used to keep track of which variables can be used where - show the value of each variable, but they also show the function each variable belongs to - each function is represented by a frame Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science  UNIT 3: CONDITIONALS AND RECURSION else: statement_block MODULO (%) - divides two numbers and returns the Note: Only one of the statements will be executed remainder. per run of the program. - can be used when: - Finding x % y BRANCHES - Getting the rightmost digits - the alternative statements FLOOR DIVISION (//) CHAINED CONDITIONALS - divides two numbers and rounds down the result Note: 1. if - can be on its own BOOLEAN EXPRESSION elif and else - cannot be - an expression that is either True or False. 2. elif - must come after an if before an else (I) EQUAL-TO (==) 3. You can have multiple elif but only one else - a relational operator that compares 4. else statement - optional two operands and produces True if equal and False if not. NESTED CONDITIONALS - conditionals inside a conditional THREE (3) LOGICAL OPERATORS - not encouraged to use - makes code cluttered and hard to read AND, OR, NOT General Syntax: CONDITIONAL EXECUTION if condition: statement_block CONDITIONAL STATEMENTS if condition_2: - gives us the ability to check conditions and statement_block change the behavior of the program. LOGICAL OPERATORS If statement - the simplest conditional statement - often help avoid using nested conditionals COMPOUND STATEMENT - a statement with a header and indented RECURSION body. - the process when a function that calls itself - the body must have at least one statement - use pass statement if you haven’t RECURSIVE FUNCTION thought of what to code yet. - a function that calls itself ALTERNATIVE EXECUTION INFINITE RECURSION - the second form of the if statement - happens if a recursion never reaches a - there are two possibilities and the condition base case determines which one gets executed. - recursive calls go on forever and the program never terminates. General Syntax: Example: def recurse (): If condition: recurse () statement_block Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science Note: a program with infinite recursion won’t CALLING FRUITFUL FUNCTIONS actually run forever - the interpreter will throw an error when INTERACTIVE MODE maximum recursion depth has been - python will show the result immediately in reached. the terminal KEYBOARD INPUT SCRIPT MODE - explicitly call print () to see their return value input () - the built-in function that stops the program INCREMENTAL DEVELOPMENT and waits for the user to type something. - used to create more complex programs - Writing a prompt is good practice when - a technique in programming wherein you using this function create and test code in increments - test the code in each step \n - can save a lot of debugging time - a sequence that represents a new line - causes a line break Syntactically correct - there is no error in the code and it runs - you can test it before you make it more complicated UNIT 4: FRUITFUL FUNCTIONS Example: RETURN VALUE 𝑥 = −𝑏 ± 𝑏^2 − 4𝑎𝑐 2𝑎 - this is what is being generated when calling a function - can be assigned to a variable or use as part STEPS: of an expression 1. Create an outline of the functions (w/ - can ba a variable or expression parameters and return value) 2. Calculate b^2 and 4ac Variable: area_of_a_circle = area (2) 3. Get the square root Expression: double_area = 2 * area(2) 4. Get the value of the numerator double_area 5. Divide numerator by 2a and return x 25.132741228718345 6. Improve readability and/ or efficiency Return Statement Key Aspects: - useful in each branch of a conditional 1. Making small incremental changes - helps locate where a potential error Note: once a return statement is executed, could come from the function terminates 2. Temporary variables - can be used to hold temporary DEAD CODE values - code after the return statement or any code 3. Once you have a working program, you can that will never be executed improve your program’s structure FRUITFUL FUNCTION FUNCTION CALLING - ensure all the possible paths/branches in a - you can call a function within a function call function hit a return statement Example: sqrt (abs(-4)) Note: Python provides the abs () function Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science COMPOSITION UNIT 5: ITERATION / LOOPS - the ability of a function to call one function from within another. ITERATION - the process of doing something again and BOOLEAN FUNCTIONS again until a condition is met. - convenient for hiding complicated tests inside functions Python - provides us with two (2) statements that - common to give boolean function names easily perform iteration: that sound like yes/no questions. for while LEAP OF FAITH - an alternative being used instead of COUNTED LOOPS: for Loop following the flow of execution. - “Assume” General Syntax: for in : Variable - can be any variable name Sequence - an ordered collection of items you want to iterate (i.e. a string, a list) PYTHON SEQUENCES - positionally ordered - Elements - are accessed by specifying their indices Indexing - accessing an element in a sequence using its index - use bracket variablename [index]: to access an element QUICK INTRO TO LISTS List - a data type in python used to store multiple values in a single variable range () - a function that generates a list of numbers - only accept integer arguments Three (3) ways to call range () function: i. range (start, stop) ii. range (start, stop, step) iii. range (stop) Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science  start while loop - included in the list - used when the number of iterations is not - should be greater than stop known in advance - Addition: start = 0 - used to continuously ask input from the user - Multiplication: start = 1 Controlling Loops: break stop - excluded Break statement - stop + 1 - allows you to exit the loop - used to terminate the loop based on a stepsize certain condition - increments - can be negative Continue statement - allows you to skip the current iteration and enumerate () run to the next one - function that returns a list of pairs - used to skip an iteration based on certain - the index and its associated element conditions TUPLE Nested Loops - the pair of values it returns - loops can be nested in other loops - built-in data type - Inner loop - Outside loop -> outer loop MULTIVALUED ASSIGNMENT Infinite Loops - assign multiple variables at once as long as - occurs if a loop never terminates there are an equal number of values to - Commonly happens if the condition never match with the storage variables. returns False or if the counter variable never changes General Syntax: Tip: ctrl+c - exit the loop while : Condition - an expression that returns either True or False While Loop - only iterates if the condition returns True 1. Evaluate condition 2. If True: execute body 3. Evalate condition, then repeat process 4. Once condition return False, the while loop will terminate. for Loop - used when the number of iterations is known Notes by: Ma. Christie Jude L. Tarre Bachelor of Science in Computer Science