Python Programming: An Introduction to Computer Science

  1. Computers and Programs
    • A computer is a universal information-processing machine
    • Computer science is the study of what can be computed: design, analysis, and experimentation
    • Computer system comprised of: 1) CPU, the brain 2) CPU acts on data and programs in main memory (RAM), 3) More permanent memory in secondary memory devices
    • All languages share property of having precise syntax (form) and semantics (meaning)
    • Programs usually written in human-orientated or high-level languages
    • These are compiled or interpreted for computer to understand
    • Python program is sequence of commands (statements)
  2. Writing Simple Programs
    • Writing programs requires systematic approach
      • Problem Analysis: study problem to be solved
      • Program specification: deciding exactly what program will do
      • Design: writing an algorithm in pseudo code
      • Implementation: Translating the design into a programming language
      • Testing/Debugger: Finding and fixing errors in the program
      • Maintenance: keeping program up to date with evolving needs
    • Many simple programs follow the input, process, output (IPO) pattern
    • Programs composed of statements built from identifiers and expressions
    • Identifiers are names
    • Expressions produce data and are composed of: 1) literals, 2) variables, 3) operators
    • Operators: +, -, *, /, **
    • Assigning variables is done through = sign.
    • Can do multiple assignments at once
    • Definite loops executes a known number of times: for loops
  3.   Computing with Numbers
    • Computer represents particular kinds of information with data types
    • Data types determines what kind of values an object can have
    • whole number usually int (integer) and fractional values usually by float
    • additional mathematical functions can be imported from the math library
    • loop accumulator pattern good for computing sum or product of a sequence of values
    • both int and floats are represented on underlying computer using a fixed-length sequence of bits (-2^31 to 2^23 – 1 range for ints on 32 bit machine)
    • Python automatically converts one data type to another in certain situations
    • can explicitly convert using int(), float(), round()
  4. Objects and Graphics
    • An Object is entity that combines data and operations
    • Its data is stored in instance variables and operations are called methods
    • every object is an instance of some class
    • An instance is created by calling a constructor method
    • An object’s attributed are accessed via dot notation
    • Accessor methods return information and mutator methods change the values of an instance
    • An important consideration in graphical programming is choice of appropriate coordinate system
    • situation where two variables refer to same object is called aliasing
  5. Sequences: Strings Lists, and Files
    • Strings are sequences of characters
    • Strings and Lists can be manipulated with built-in sequence operations: +, *, [], [:], len
    • lists are more general than strings: can contain values of any type and are mutable (modifiable)
    • Strings are represented in computer as numeric codes: ASCII and Unicode are standards: ord and chr to translate between
    • Encoding data is encryption: there are public keys and private key systems
    • format method good for formatting strings
    • text files are multi-line strings stored in secondary memory
    • can read with read(), readline(), and readlines(). possible to iterate through lines with a loop
    • when processing finished, file should be closed
  6. Defining Functions
    • function is a kind of subprogram used for reducing code duplication and helping add structure of modularity
    • parameters allow functions to have changeable parts
    • parameters appearing in function definition are formal parameters
    • parameters in the function call are actual parameters
    • A function call initiates four steps: calling program suspended, values of parameters are assigned to formal parameters, body of function is executed, control returns immaterially following function call
    • The scope of a variable is in area of program where i may be referenced
    • formal parameters and local variables are local to function
    • functions can communicate information back through return. If no return, returns None
    • python passes parameters by value, if passed object is mutable then changes made to the object may be visible to the caller
  7. Decision Structures
    • Decision structures allow programs to execute different sequences for different cases
    • if for simple decisions, if-else for two-way and if-elif-else for multiway
    • decision based on evaluation of conditions: <, <=, !=, ==, >, >=
    • try-except helps make programs for “bulletproof”
    • algorithms incorporating decisions can become complicated.
    • usually a number of solutions are possible, careful thought should be given to produce a correct, efficient, and understandable program
  8. Loop Structures and Booleans
    • For loop is a definite loop through a sequence
    • while loop is indefinite. as long as condition is true
    • indefinite loop can be used for interactive loops
    • sentinel loop goes until a special input is entered. special input should not be processed
    • loops can be nested, best to consider one at a time
    • breaks can be used to exit a loop
    • other data types can be used where a bool is expected
  9. Simulation and Design
    • Simulations can help answer questions regarding probabilistic chances e.g. Monte Carlo
    • Top-down design: 1) Express an algorithm in terms of smaller problems 2) Develop an interface for each of the smaller problems 3) Express the algorithm in terms of its interfaces with the smaller problems 4) repeat the process for each of the smaller problems
    • Unit testing is process of trying out each component independently
    • Spiral development is creating simple prototype and gradually adding more features
    • Design is combination of art and science. Practice is best way to become better
  10. Defining Classes
    • An object comprises a collection of related data (instance variables) and a set of operations (methods) to manipulate that data
    • data and operations are attributes
    • Every object is an instance of some class
    • Python class definitions is a collection of function definitions
    • every method has special first parameter, self, referring to object which method is being applied
    • __init__ is the constructor for a class and initializes the instance variables of an object
    • defining new objects can simplify structure of program by allowing single variable to store a constellation of related data
    • correctly designed classes provide encapsulation
    • objects can represent real world objects and their complex behaviors
    • internal details are hidden inside the class definition so parts of program don’t need to know how an object is implemented
    • instance variables should be accessed or modified through interface methods
  11. Data Collections
    • List object is mutable sequence of arbitrary objects, items can be changed by assignment
    • Similar to arrays in other languages, but more flexible. vary size and heterogeneous
    • lists can be sorted with customized key functions. can sort lists of arbitrary objects
    • Classes can use lists to maintain collections stored as instance variables. often times more flexible than using separate instance variables
    • An entire program can be viewed as a collection of data and set of operations — and object
    • A Python dictionary implements arbitrary mapping from keys into values
  12. Object-Orientated Design
    • Object-orientated design (OOD) is the process of developing a set of classes to solve a problem
    • OOD looks for objects wheras top-down looks for functions
    • Some guidelines
      • Look for object candidates
      • Identify instance variables
      • Think about interfaces
      • Refine nontrivial methods
      • Design iteratively
      • Try out alternatives
      • Keep it simple
    • Useful to separate model and view components
    • Three fundamental principles that make software object orientated
      • Encapsulation: separating the implementation details of an object from how object is used
      • Polymorphism: different classes may implement methods with the same signature. Allow single line of code to call different methods in different situations
      • Inheritance: new class can be derived from existing class sharing methods among classes
  13. Algorithm Design and Recursion
    • Computer scientists analyze the time efficiency of an algorithm by considering how many steps the algorithm requires as a function of the input size
    • Linear search scans require time linearly proportional to size of collection while binary search algorithms require time proportional to the log of the collection size
    • Functions are recursive if it refers to itself: 1) There must be one or more base cases that require no recursion and 2) All chains of recursion must eventually reach a base case
    • Sequences can be considered recursive structures containing a first item followed by a sequence
    • Recursion is more general than iteration
    • problems solvable in theory but not practice are called intractable
    • some problems are in principle unsolvable
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s