## 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).

### 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

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.*

MAY

2011