Eng 1D04 Lecture Notes: Everything up to Recursion

15 Pages
Unlock Document

McMaster University
Engineering (General)
William Farmer

Wednesday January 12 ∙ Values are the information (data) stored and manipulated by computer programs o Booleans: true and false o Machine Integers: small integers o Floating Point Numbers: rational numbers in scientific notation o Strings: sequences of characters o Lists: sequences of values o Functions: represent mathematical functions ∙ There are various ways that common mathematical objects and other data are represented in programming languages ∙ Expressions are syntactic entities that denote a value o Atomic Expression: an identifier or a literal o Compound Expression: formed by applying an operator to other expressions o ***The value of an expression is obtained by evaluation the expression ∙ Data Type (Type for Short): a syntactic entity that denotes a collection of values of similar form o “boo1”: true and false o “int”: machine integers o “float”: floating point numbers o “str” set of strings o “list”: lists o A type error happens when a value of one type is used where a value of another is expected o Types are used in Python to catch type errors at run-time ∙ Variable: a linguistic entity whose meaning can vary; a name bound to a value o The name serves as an expression that denotes the value, names  identifiers ∙ Constant: a linguistic entity whose meaning is fixed (read-only variable) o Implemented as a variable whose value is never changed (immutable variables) o E.g “true” and “false” in python o The name of a user-defined constant is written in all capitals, e.g. “PI” ∙ Statement: a syntactic entity that states something to be done o Effect obtained by executing a statement o A program is a sequence of statements o A compound statement is a statement composed of other statements o E.g. “for”, “while”, “if”, “try-except”, “def” ∙ Modes of Program Execution: o INTERPRETED directly line by line; (supports interaction and debugging, generally slower than executing compiled code) o COMPILED into BYTE CODE for a machine that is either interpreted or compiled; (programs are more portable, but byte code is slower than native code) o COMPILED into NATIVE MACHINE CODE; (machine code is optimized ot run fast, code development is more difficult) o Python programs can be executed by all three of these modes ∙ Coding Conventions: a set of guidelines for indentation, comments, naming conventions, etc o For standardization of communication with other programmers o Improves understandability and maintainability ∙ Software Development Process: o Problem Analysis o Requirements Specification –the most important step o Design o Implementation o Testing and Verification o Delivery and Maintenance ∙ Any design that satisfies a software product’s requirements specification should be acceptable to the product’s client  TRUE Wednesday January 19 2011th ∙ Number Systems: the idea of a number is one of the strongest and most important threads in the history of mathematics ∙ The family of number systems includes o Natural: numbers for counting o Integers: for counting forwards and backwards o Rations: for measuring o Real Numbers: for solving geometric problems o Complex Numbers: for solving algebraic problems o Surreal Numbers: for “total happiness” o Closely related to each other; addition/multiplication is defined in each system ∙ Computer application is most importantly the processing of number-based computations ∙ Decimal versus Binary: o Base 10: 0,1,2,3,4,5,6,7,8,9 o Base 2: 0,1 o Position of place value specifies magnitude o (86409) = 10)(1) + (0)(10) + (4)(100) + (6)(1000) + (8)(10000) 0 1 2 3 4 o (86409) = 10)(10 ) + (0)(10 ) + (4)(10 ) + (6)(10 ) + (8)(10 ) o (10101101) = (2)(1) + (0)(2) + (1)(4) + (1)(8) + (0)(16) + (1)(32) + (0)(64) + (1) (128) = 173\ 0 1 2 3 4 5 6 o (10101101) = (2)(2 ) +(0)(2 ) + (1)(2 ) + (1)( 2 ) + (0)(2 ) + (1)(2 ) + (0)(2 ) + (1)(2 ) ∙ What is the binary number 1011 in decimal? 11 ∙ Representation of Numbers in Different Bases: o Common bases are 2,8,10, and 16 n k o (a n n−1...1 a0)b= ∑ a k k=0 ∙ What is the binary number 11101011 equal to in hexadecimal: EB ∙ Machine Integers: o Signed magnitude approach ∙ First bit 0 for positive 1 for negative ∙ Has the problem of two zeros ∙ Most computers actually use 2’s complement o 2’s complement ∙ Has a single 0 ∙ Have one negative number without a corresponding positive number ∙ Positive numbers look as one would expect ∙ Negative numbers have 1 as most significant bit ∙ Negate a number by inverting its bits adding 1 ∙ x + (-x) = 0 ∙ 8-bit machine integers: a type of integers where each member of the type is represented as an 8-bit binary number o Includes representations for a finite range of integers: -128 to +127 (arithmetical operations can lead to overflow and underflow) o The two’s complement representation can be used with n-bit integers for all n>=2 ∙ Numeric Types: a type of value that represents anumber system o Python Contains the follow built-in numeric types: int( 32-bit), long (all) float (64-bit), complex (fpairs of 64-bit floating numbers) ∙ Type of Conversion: often convenient to convert a value from one type of another o Python contains several built-in type conversion functions (int, long, float, str, bool) o Python implicitly converts values in numeric expressions of mixed type to resolve type conflicts ∙ Value of “narrower” type is converted to the “wider” type ∙ Module: a Python program that can be used as a unit (e..g math module) o Imported into the python interpreter or into another module using the import statement o A function, variable, constant, etc. named x in a module m is accessed by the expression m.x o A module named m can be created by simply putting a Python program into a file named m.py Wednesday January 26 2011 ∙ Sequence: a mapping from the natural numbers to some set of values o Finite: ends o Infinite: never ending ∙ Operations on finite Sequences o The length o Concatenation o Repetition o I member o Slice ∙ Sequence Type: type of values that represent finite sequences ∙ Graphemes: units of a writing system ∙ ASCII: 128 characters (94 printable and 33 non) represented by 7- or 8-bits ∙ Unicode: intended to represent the graphemes of the world’s major writing systems o Over 107000 characters from 90 writing systems o 8-, 16-, or 32- bits ∙ A string is finite sequence of characters ∙ Type str represents immutable strings of ASCII characters ∙ A literal of type str is a finite sequence of characters surrounded by single or double quote marks ∙ In Python, character is a string of length 1 (ord numeric code; chrASCII character) ∙ Nonprintable (escape) characters are represented with backslash notation (\n for newline) ∙ Python includes a string formatting operator for inserting formatted values into strings (%) ∙ The type Unicode represents immutable strings of (16/32 bit) Unicode characters) ∙ List: finite sequence of values (can have different types, strings can be represented by lists in Python) o Type list represents lists o A literal of type list is a finite sequence of values surrounded by square brackets and separated by commas o Mutable ∙ Input/Output (I/O) o A program is useless unless it can process input or output o Input to and output from a program usually involves three stages:  External input (OS)program input (prog) internal input  Internal output (prog) program output (OS) External Output o External input is information received from an input device such as a keyboard or mouse file o External output is information sent to a output device such as a screen or printer o Program input and output are usually strings or files ∙ File: a finite sequence of data stored on a persistence data storage device (characters or bits) o Text files, binary files, various extensions (.exe, .txt, .doc, .jpg, .PDF….) o Files allow sharing of data between programs, users, computers, storage devices o Can be very large (store more info than can be placed in memory at one time) o Can use files for both input and output – files are more efficient than other data structures for large amounts of input and output ∙ File processing in Python o Opening a file: filevar = open(filename,mode), where filename is the name of a file as a string and mode is either “r” for read or “w” for write o Reading from a file: string = filevar.read(); string = filevar.readline(); list=filevar. readlines() o Writing to a file: filevar.write(string); filevar.writeliens(list) o Closing a file: filevar.close() ∙ Standard Input:the input to a command line interface entered by a user ∙ Standard Output: the output to a command line interface presented to a user o Standard input and output are represented in python as files: sys.stdin; sys.stdout ∙ The Python input operator is a special case of sys.stdin.readline() ∙ The Python print operator is a special case of sys.stdout.write(string) ∙ Alan Turing: a brilliant British mathematician, logician, and computer scientist o In 1937 developed a model of computation based on the idea of Turing machine o Lead the British team during WW2 that broke the code of the Germna Enigma Machine o 1945 designed the Automatic Computing Engine (ACE) electronic computer o 1950 devised the Turing test for determining whether a software system exhibits intelligence o The Turing Award (given by the Association for Computing Machinery (ACM) since 1966) is the highest award in computing Wednesday February 2 , 2011 ∙ Object: a mutable, active value that combines data and operations and communicates via message passing. o An object’s data is a set of variables called fields (they define the object’s state, the set of info stored in the object) o An object’s operations is a set of functions called methods (define the object’s behaviour) o Accesor: a method that retrieves information about the state of an object (aka, a selector or getter) win1.getHeight(), win1.getwidth() o Mutator: method that modifies the state of an object (aka, a setter) win1.setBackground(“lighblue”); win1.setCoords(0,0,100,100) ∙ Classes: a template for a type of object o A member of this type is called an instance of the class; win1=graphics.GraphWin(); circ = graphics.Circle(Point(50,50), 10) o An instance of class is created by calling the class’s constructor, which has the same name as the class itself o Constructor creates a new object of type ClassName and then class the class’s _init__ method to initialize the fields of the object ∙ Object-Oriented Programming: a program consists of a collection of class definitions and behaves as a collection of interacting objects that: 1. send and receive messages. 2. provide and use services o i.e. C#, Java, C++, Smalltalk, OCaml, Python o An application of modularity ∙ Graphics Module includes classes that enable the user to create: Window objects for displaying graphics; graphics objects such as points, lines, circles, etc. (can be draw on window objects) o Origin is in the upper left corner ∙ Donald Knuth: brilliant American computer scientist and Professor Emeritus at Stanford University; wrote the classic multi-volume “Art of Computer Programming” in 1968 that describes and analyzes a wide selection of algorithms (based on rigorous mathematical techniques); created the “TeX” computer typesetting program; wrote “Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness”; Recived the Turing Award in 1974 th Wednesday February 9 , 2011 ∙ Problem – Code Duplication is bad, it can make the program: long and verbose; expensive to maintain; hard to understand; hard to reuse o Replace similar pieces of code by modular code units ∙ Mathematical Functions: one of the most fundamental values in mathematics and computing o A function is a rule f: I  O that associates members of inputs with members of outputs  Every input is associated with AT MOST one output; some inputs may not be associated with an output o A function is a value (Set) f ⊆ I × O such that if (x,y), (x,y’) are elements of f then y = y’ o Each function has a domain I and a range O ∙ Functions in Python: represents a mathematical function as a value that can be applied as a rule; in other languages, rules that represent functions are called – procedures, subroutines, or methods ∙ Functions are subprograms that: are defined and applied by the program developed; reduce code duplication; improve software quality o Since functions are “first-class” values in Python, a function can itself take functions as input and return functions as output (not possible in most other languages) ∙ Function Defintion: form – def FUNCTIONNAME(p ,…p ): 1 2 statement 1 . . staement n ∙ Formal Parameters: (p …p ) represent inputs to the function; when the function is 1 m called, they become local variables of the function call o If m = 0, the function takes no input o Output of a function is returned using the state of: return value ∙ Function Application: an expression of the form FUNCTIONNAME(a ,…a ); also cal1ed m function calls or function invocations o (a ,1a ) mre called the actual parameters of the function application: values are inputs to a function, must match the formal parameters p when i the application is evaluated o Side Effect: the evaluation of a function application may cause the program’s state to be modified ∙ Evaluation of a Function Application: four steps ( “call by value” evaluation strategy) o Calling program’s execution is suspended o Formal parameters are bound to values of actual parameters o Body of function is executed o Output value of function is returned to the calling program and the calling program’s execution is resumed o **If no value is explicitly returned by the function, the special object None is returned ∙ Namespace: a mapping from names to programming entities (the same name may be in different namespaces). o Examples: set of built-in names, set of global names in a module, set of global names in a class, set of global names in an object, set of local names in a function o The name x in a namespace for the set of global names in a module/class/object named n are accessed via an expression: n.x ∙ Scope: a region of a program where a namespace is accessible; the scope in which a name is declared determine what namespace the name is in o Scopes are nested: innermost scope contains local names of the function; middle scope contains the global names of the module; outermost scope contains the built-in names o A variable created outside of the innermost scope is read-only within the innermost scope – trying to write to it creates a new local variable in the innermost scope ∙ Principal of Least Privilege: the principle that a subject shoul
More Less

Related notes for ENGINEER 1D04

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.