CS61A

Function

The principle of designing a function:

Give each function exactly a job
Don’t repeat yourself. Implement a process just once, but execute it many times.
Define functions generally

Higher-order functions(A function that takes a function as an argument value or returns a function as a return vales):

express general methods of computation.
remove repetition from programs
separate concerns among functions
the inner function need to be defined as a real function(f) rather than a value evaluated by the function such as f(x) in a higher-order function. It actually act as a function that its output is some functions.

True/False:

‘and’ will return the first False value it meets or it will return the last True value
‘or’ will return the first True value

Recursion

Skipping questions：

Call expressions don’t allow you to skip evaluating part of the call expressions

every parts of the statement will be executed

Control expressions(and/or) allow you to skip evaluating some sub-expressions

e.g. return if -100 > 0 and sqrt(-100) > 10 will not lead to a error

difference between iteration and recursion

sometimes recursion can simplify the code

Abstraction

1
2
3
4
5


def fact(n):
	if n == 0：
    	return 1
    else:
        return n * fact(n-1)

Is fact implemented correctly?

Verify the base case.
Treat fact as a functional abstraction!(focus on what’s it function)
Assume that fact(n-1) is correct.
Verify that fact(n) is correct, assuming that fact(n-1) correct.

Containers

Strings are Sequences

1
2
3
4
5
6


>>>'here' in 'Where\'s Waldo' 
True
>>>234 in [1, 2, 3, 4, 5]
False
>>>[2, 3, 4] in [1, 2, 3, 4, 6]
False

In list you can only search for one word each time

When working with strings, we usually care about whole words more than letters.

Comprehensions

Both list and dictionary can use comprehension to define them

1
2
3
4


# dictionary
{<key exp>:<value exp> for <name> in <iter exp> if <filter exp>}
# list
[<value exp> for <name> in <iter exp> if <filter exp>]

The parent frame of the comprehensions is the current frame

Data abstraction

Abstraction Barriers

The higher the more abstract. Taking computing fraction as example

This example violates the abstraction barriers. Here’s how

Does not use constructors: instead of using list ‘[1, 2]’, it should use rational
No selectors: instead of using list element to imply numer and denom, it should use numer and denom
No constructor: use add_rational, this will make your code more readable!

All in all, the data abstraction should make a data/func’s detail the same as its name!

An elegant way to obtain the minimum number form cat project

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


def minimum_mewtations(typed, source, limit):
    """A diff function that computes the edit distance from TYPED to SOURCE.
    This function takes in a string TYPED, a string SOURCE, and a number LIMIT.
    Arguments:
        typed: a starting word
        source: a string representing a desired goal word
        limit: a number representing an upper bound on the number of edits
    >>> big_limit = 10
    >>> minimum_mewtations("cats", "scat", big_limit)       # cats -> scats -> scat
    2
    >>> minimum_mewtations("purng", "purring", big_limit)   # purng -> purrng -> purring
    2
    >>> minimum_mewtations("ckiteus", "kittens", big_limit) # ckiteus -> kiteus -> kitteus -> kittens
    3
    """
    typed_words = list(typed)
    source_words = list(source)
    all = 0
    if limit<0: # Base cases should go here, you may add more base cases as needed.
        # BEGIN
        "*** YOUR CODE HERE ***"
        return 0
        # END
    # Recursive cases should go below here
    elif len(typed_words) == 0: # Feel free to remove or add additional cases
        # BEGIN
        "*** YOUR CODE HERE ***"
        return abs(len(typed)-len(source))
    elif len(source_words) == 0:
        return abs(len(source) - len(typed))
        # END
    else:
        add = minimum_mewtations(typed[0:], source[1:], limit-1) + 1 if typed_words[0] != source_words[0] else minimum_mewtations(typed[1:], source[1:], limit)
        remove = minimum_mewtations(typed[1:], source[0:], limit-1) + 1 if typed_words[0] != source_words[0] else minimum_mewtations(typed[1:], source[1:], limit)
        substitute = minimum_mewtations(typed[1:], source[1:], limit-1) + 1 if typed_words[0] != source_words[0] else minimum_mewtations(typed[1:], source[1:], limit)
        return min(add, remove, substitute)
        # END

Syntax

Useful string methods for processing the contents of a file:

.strip():return a string without whitespace (spaces, tabs, etc.)
1 2

>>>' hello '.strip() 'hello'
.split():returns a list of strings that were separated by whitespace
1 2

>>>'hi there'.split() ['hi', 'there']
.replace(a. b): returns a string with all instances of string a replaced by string b
1 2

>>>'2+2'.replace('+', ' + ') '2 + 2'
list: string can be seen as a string, processing it by slicing
1 2

>>>'apples'[:-1] 'apple'

.join(): get the elements in argument separated by the thing before it

1
2
3


>>>s = ['a', 'little', 'bug']
>>>' '.join(s)
'a little bug'

Lab 05 Mutability, Iterators

There are many other list mutation methods:

append(elem): Add elem to the end of the list. Return None.
extend(s): Add all elements of iterable s to the end of the list. Return None.
insert(i, elem): Insert elem at index i. If i is greater than or equal to the length of the list, then elem is inserted at the end. This does not replace any existing elements, but only adds the new element elem. Return None.
remove(elem): Remove the first occurrence of elem in list. Return None. Errors if elem is not in the list.
pop(i): Remove and return the element at index i.

pop(): Remove and return the last element.

1
2
3


>>>s = [1, 2, 3]
>>>print(s.pop(1))
2

The difference of Where iteration and For iteration:

Where iteration can be very useful when the range is variable

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


def insert_items(s, before, after):
    """Insert after into s after each occurrence of before and then return s.

    >>> test_s = [1, 5, 8, 5, 2, 3]
    >>> new_s = insert_items(test_s, 5, 7)
    >>> new_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> test_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> new_s is test_s
    True
    >>> double_s = [1, 2, 1, 2, 3, 3]
    >>> double_s = insert_items(double_s, 3, 4)
    >>> double_s
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_s = [1, 4, 8]
    >>> large_s2 = insert_items(large_s, 4, 4)
    >>> large_s2
    [1, 4, 4, 8]
    >>> large_s3 = insert_items(large_s2, 4, 6)
    >>> large_s3
    [1, 4, 6, 4, 6, 8]
    >>> large_s3 is large_s
    True
    """
    "*** YOUR CODE HERE ***"
    i = 0
    while i < len(s):
        if s[i] == before:
            s.insert(i+1, after)
            i += 1
        i += 1
    return s

# if you ues for iteration, the changing length of list s is quite a big problem

HW 05

the yield, yield from, iter function, and the algorithms here are so hard!

I can feel I’m extremely weak at this part

CS61A笔记

一个计算机基础课的笔记