Difference between revisions of "Guides"

From CS 61A Wiki
Jump to: navigation, search
(Environment diagrams)
(Sequences)
Line 68: Line 68:
  
 
== Sequences ==
 
== Sequences ==
 +
=== Reversing tuples ===
 +
[https://piazza.com/class/hoxc5uu6sud761?cid=639 Source: Spring 2014 Piazza (639)]
 +
 +
'''Student Question'''
 +
 +
Why does [::-1] tuple work while the tuple [0:3:-1] doesn't?
 +
 +
I thought the -1 after the second semicolon meant that the interpreter is going to read the indexes "backwards".
 +
 +
'''Student Answer'''
 +
 +
The syntax of slicing is <tt>tup[start:end:step]</tt>:
 +
<ul><li>start from index <tt>start</tt> and end just before index <tt>end</tt>, incrementing the index by <tt>step</tt> each time
 +
</li><li>if no <tt>step</tt> is provided, <tt>step</tt> = 1
 +
</li><li>if <tt>step</tt> is positive, default values if not provided: <tt>start</tt> = 0, <tt>end</tt> = <tt>len(tup)</tt>
 +
</li><li>if <tt>step</tt> is negative, default values if not provided: <tt>start</tt> = -1, <tt>end</tt> = one position before the start of the string
 +
</li></ul>
 +
 +
<pre>&gt;&gt;&gt; (1, 2, 3)[::-1] # start at index -1, end one position before the start of the string
 +
(3, 2, 1)
 +
&gt;&gt;&gt; (1, 2, 3)[0:3:-1] # start at 0 and go to 3, but step is negative, so this doesn't make sense and an empty tuple is returned
 +
()
 +
</pre>
 +
 +
This is a helpful visualization from http://en.wikibooks.org/wiki/Python_Programming/Strings#Indexing_and_Slicing:
 +
<blockquote>
 +
To understand slices, it's easiest not to count the elements themselves. It is a bit like counting not on your fingers, but in the spaces between them. The list is indexed like this:
 +
<pre>Element:    1    2    3    4
 +
Index:    0    1    2    3    4
 +
        -4    -3    -2    -1
 +
</pre>
 +
</blockquote>
 +
More info about slicing at http://stackoverflow.com/a/13005464/2460890.
 +
 +
=== Slicing with negative step ===
 +
[https://piazza.com/class/hoxc5uu6sud761?cid=702 Source: Spring 2014 Piazza (702)]
 +
 +
'''Student Question'''
 +
 +
if the third example returns an empty tuple because you can't take negative steps from 0 to 4, shouldn't the second example also return an empty tuple?
 +
 +
Can someone explain why each example returns the respective answers?
 +
 +
Thanks
 +
 +
<pre>>>> x= (1,2,3,4)
 +
>>> x[0::-1]
 +
(1,)
 +
>>> x[::-1]
 +
(4, 3, 2, 1)
 +
>>> x[0:4:-1]
 +
()
 +
>>> x[1::-1]
 +
(2, 1)</pre>
 +
 +
'''Instructor Answer'''
 +
 +
(For reference, the notation is <tt>x[start:end:step]</tt>)
 +
 +
Python does something a very strange when the step is negative: if you omit the arguments to start and end, Python will fill them with what makes sense for a negative step. In the simple case of <tt>x[::-1]</tt>, Python fills in the start with <tt>len(x)-1</tt> and the end with <tt>-(len(x)+1)</tt>. The end term is strange, but remember that the end term isn't included. We therefore can't use 0, but we can't use -1 either, since that clearly refers to the last element of the tuple. We need to fully wrap the negative index around, to refer to the element "before" the 0th index. This way, Python will start at the end of the tuple and proceed to the beginning of the tuple.
 +
 +
That's why <tt>x[0:4:-1]</tt> doesn't make sense: how can we start at 0 and end at 4, if we're proceeding backwards?
 +
 +
And that's why <tt>x[0::-1]</tt> makes sense (albeit, in a strange way): Python is proceeding from the 0 index to the beginning of the list. It includes the start index, which is why you see a 1 pop up.
 +
 +
Let me know if that was confusing!
 +
 
== Recursion ==
 
== Recursion ==
 
== Data abstraction ==
 
== Data abstraction ==

Revision as of 20:17, 15 June 2014

Higher-order functions

Environment diagrams

Environment Diagram Rules

Source: Spring 2014 Piazza (131)

Environment Diagrams are very important in our understanding of how the computer interprets our code.

We will test you on this in every exam.

It will never go away.

Given that, master it as quickly as you can! :)

Below are the rules I follow when drawing environment diagrams. If you understand and faithfully follow these rules when drawing them, you'll never get them wrong.

One thing you haven't learned yet is nonlocal. You can skip that particular step for now (step 2 of Assignment).

Post here if you have any questions!

You can also take a look at this link for some examples of environment diagrams: http://albertwu.org/cs61a/notes/environments

For a different perspective on the rules, check out: http://markmiyashita.com/cs61a/sp14/environment_diagrams/rules_of_environment_diagrams/

A handout with detailed instructions on drawing environment diagrams is also available here (linked on the bottom of the course homepage): http://inst.eecs.berkeley.edu/~cs61a/sp14/pdfs/environment-diagrams.pdf

Environment Diagram Rules
=========================

Creating a Function
--------------------
1. Draw the func <name>(<arg1>, <arg2>, ...)
2. The parent of the function is wherever the function was defined
   (the frame we're currently in, since we're creating the function).
3. If we used def, make a binding of the name to the value in the current frame.

Calling User Defined Functions
------------------------------
1. Evaluate the operator and operands.
2. Create a new frame; the parent is whatever the operator s parent is.
   Now this is the current frame.
3. Bind the formal parameters to the argument values (the evaluated operands).
4. Evaluate the body of the operator in the context of this new frame.
5. After evaluating the body, go back to the frame that called the function.

Assignment
----------
1. Evaluate the expression to the right of the assignment operator (=).
2. If nonlocal, find the frame that has the variable you re looking for,
   starting in the parent frame and ending just before the global frame (via
   Lookup rules). Otherwise, use the current frame. Note: If there are multiple
   frames that have the same variable, pick the frame closest to the current
   frame.
3. Bind the variable name to the value of the expression in the identified
   frame. Be sure you override the variable name if it had a previous binding.

Lookup
------
1. Start at the current frame. Is the variable in this frame?
   If yes, that's the answer.
2. If it isn't, go to the parent frame and repeat 1.
3. If you run out of frames (reach the Global frame and it's not there), complain.

Tips
----
1. You can only bind names to values.
   No expressions (like 3+4) allowed on environment diagrams!
2. Frames and Functions both have parents.

Sequences

Reversing tuples

Source: Spring 2014 Piazza (639)

Student Question

Why does [::-1] tuple work while the tuple [0:3:-1] doesn't?

I thought the -1 after the second semicolon meant that the interpreter is going to read the indexes "backwards".

Student Answer

The syntax of slicing is tup[start:end:step]:

  • start from index start and end just before index end, incrementing the index by step each time
  • if no step is provided, step = 1
  • if step is positive, default values if not provided: start = 0, end = len(tup)
  • if step is negative, default values if not provided: start = -1, end = one position before the start of the string
>>> (1, 2, 3)[::-1] # start at index -1, end one position before the start of the string
(3, 2, 1)
>>> (1, 2, 3)[0:3:-1] # start at 0 and go to 3, but step is negative, so this doesn't make sense and an empty tuple is returned
()

This is a helpful visualization from http://en.wikibooks.org/wiki/Python_Programming/Strings#Indexing_and_Slicing:

To understand slices, it's easiest not to count the elements themselves. It is a bit like counting not on your fingers, but in the spaces between them. The list is indexed like this:

Element:     1     2     3     4
Index:    0     1     2     3     4
         -4    -3    -2    -1

More info about slicing at http://stackoverflow.com/a/13005464/2460890.

Slicing with negative step

Source: Spring 2014 Piazza (702)

Student Question

if the third example returns an empty tuple because you can't take negative steps from 0 to 4, shouldn't the second example also return an empty tuple?

Can someone explain why each example returns the respective answers?

Thanks

>>> x= (1,2,3,4)
>>> x[0::-1]
(1,)
>>> x[::-1]
(4, 3, 2, 1)
>>> x[0:4:-1]
()
>>> x[1::-1]
(2, 1)

Instructor Answer

(For reference, the notation is x[start:end:step])

Python does something a very strange when the step is negative: if you omit the arguments to start and end, Python will fill them with what makes sense for a negative step. In the simple case of x[::-1], Python fills in the start with len(x)-1 and the end with -(len(x)+1). The end term is strange, but remember that the end term isn't included. We therefore can't use 0, but we can't use -1 either, since that clearly refers to the last element of the tuple. We need to fully wrap the negative index around, to refer to the element "before" the 0th index. This way, Python will start at the end of the tuple and proceed to the beginning of the tuple.

That's why x[0:4:-1] doesn't make sense: how can we start at 0 and end at 4, if we're proceeding backwards?

And that's why x[0::-1] makes sense (albeit, in a strange way): Python is proceeding from the 0 index to the beginning of the list. It includes the start index, which is why you see a 1 pop up.

Let me know if that was confusing!

Recursion

Data abstraction

Time complexity

Mutability

Mutable data-structures

Object-oriented programming

Iterables, iterators and generators

Scheme

Streams

Logic

Python syntax and semantics

Student guides

How to learn Computer Science

Source: Spring 2014 Piazza (241)

If you've never programmed before, or if you've never taken a class quite like 61A before, things right now might be scary. Everything is strange and new and there quite a lot to take in all at once. So if you're having a hard time so far, here are a few articles that might help.

Note: these articles are pretty long, so feel free to read them in multiple sittings.

At the beginning, everything seems a bit scary in CS. Michelle Bu, a Berkeley alum and a crazy good hacker, shares one of her experiences when she was a wee n00b in 21 Nested Callbacks.

Start here! "A Beginner's Guide to Computer Science" Written by Berkeley's own James Maa. James is known for his killer walkthroughs (check out his Productivity guide). This article gives you some background on learning CS and then provides a practical guide on how to learn effectively.

How do we learn? Mark Eichenlaub explains in this Introduction to Learning Theory. This is quite possibly the best introduction to Learning Theory.

Sometimes, you're stuck and you end up really, really frustrated. Marcus Geduld explains Why do we get frustrated when learning something?

Composition

Debugging

Miscellaneous