MIT Python Programming #7

Lesson 7: Lists and mutability, dictionaries, pseudocode, introduction to efficiency

Massachusetts Institute of Technology (Open Course Ware): Introduction to Computer Science and Programming

View the complete course at: http://ocw.mit.edu/6-00F08

Introduction to Computer Science & Programming Class Notes

Lists and mutability, dictionaries, pseudo code, introduction
to efficiency

Lesson 6 we discussed lists. Lists are mutable.

Ivys [ 1 ] = -15    The object 1 within the
Ivys list is now given a value of -15

Ivys = [ 'Yale', '-1', 'Princeton' ]     (Original
Statement)
Ivys [ 1 ] = -15
print Ivys
[ 'Yale', -15, 'Princeton' ]

Items in a list are objects.
L1 = [ 1, 2, 3 ]
L2 = L1
print L2
[ 1, 2, 3 ]
L1 [ 0 ] = 4
print L1
[ 4, 2, 3 ]
print L2
[ 4, 2, 3 ]

L1 and L2 are both bound to the same object.

a = 1
b = a
a = 2
print b
1
Printing b returns 1. Why is this so? In the example of L1 and L2 we
stated that the existing object(list) is defined as 1, 2, 3. We then appended
the object(list) to change the 1 to the integer 4. In the example a and b we
first assigned the value of 1 to the a. We then assigned the same object to b.
(b = a). In the final statement we assigned the value of 2 to a. This was a
assignment different object and not an append to a current object. (L1 L2
example we appended an object within the list).

Mutable Types

Dictionaries

Like lists, dictionaries are mutable. Like lists they can be heterogeneous.
(contain strings, numbers, other dictionaries, etc)
Unlike lists, they are not ordered.

Generalized Indexing
Every element of a dictionary is a <key, value>
Example:
if showDicts ( ) :      Defines a
function
EtoF = { 'one' : 'un', 'soccer' : "football" }    
Think of this as English to French.
print EtoF ( 0 )
"traceback error……"
Dictionaries are not ordered. Print EtoF ( 0 ) makes a request to print
the first item. Since dictionaries are not ordered their is not first item.

Dictionaries are NOT ORDERED.
Lists
& Strings are ORDERED

If you define a value within a list and them make a call to that value a call
is made in a linear fashion.
List = Is my value defined in the first item? What about the second? Third?
Forth? …….etc.

Dictionaries use a "magical" function for finding the value bound by a key.
It is called HASHING.

Hashing – Values can be retrieved in Constant Time(stored
in memory). Values attached to keys are found instantly. More on hashing later
in term).

How do you use the idea of functions to organize code? So far this term we
have done this implicitly.

Lets focus on using functions explicitly.
We will do this by:
Finding the length of a hypotenuse of a right triangle.

Pseudo Code
Write a description of the steps to be taken for the code. Simply going to write
what we are going to do.

Pseudo Code – Hypotenuse Length of a Right Triangle
– input value for base as a float
–    "         "   
"     height  "    "
– square root of b*b + h*h (solve as float in hypothesis)
– print something out

Hypotenuse

Use pseudo code.
– Write out the steps
– A good programmer will go back and modify pseudo code when it is needed during
programming.
– Use it to define the flow of control. What are the basic modules? What
information needs to be passed between these modules in order to make the code
work?

Efficiency (Orders of Growth)
– Important consideration when designing code.
– Best to use code that works initially then later code can be rewritten to be
more efficient.

Efficiency Example: Google processes 10,000,000,000 pages.

Brute Force Methods are not efficient.

Clever(original) algorithm are difficult to develop. Better to take a problem
and map into a class of algorithms that are familiar.

Efficiency is defined by the algorithm.
Efficiency maps problems into class of algorithms.
Efficiency is a measure of SPACE and TIME.

Space is defined as the amount of memory used.

This course will focus on time.

How long does it take an algorithm to run?
To define the time of the algorithm as this question: What is the # of basic
steps as a function of input size?

Random Access Model
Random access model states that all algorithms are defined as being accessed in
constant time, no matter the data type.
Obviously this is not true but merely a way of representing EFFICIENCY TIME.
Some functions are linear, as well as arithmetic equations are not within
constant time. Use of Random Access Model is for better understanding of
Efficiency Time.

Random Access Model (Define Efficiency Time)
– Best Case (Minimum # Computations)
– Worst Case (Maximum # Computations)
– Expected Case (Average # Computations)

Best practices of measuring Efficiency Time focus on Worst Case analysis.

The above is my personal notes in regards to this class to help me in the
learning process.

0
  Related Posts