Course can be found hereclassroom
Done in 2017-05-01

# LESSONS

## How to manage data

### Pop Quiz

31.1

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Inr_DYUqxk8.mp4

print_all_links must keep going until there are no more links to print. Think about looping forever (set while loop condition) until there are no more links (i.e. else:). What do you do when there are no more links (body of else: condition)?

At 1:26, Dave uses a procedure get_page(). The code for this procedure is given later in the course, in Lesson 4. This is the code:

def get_page(url):
try: import urllib
except: return ''


https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/BFYeJzcejxM.mp4

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/xssLR71EuUw.mp4

### Crawling Process

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/l_ulQLpFQJQ.mp4

Quiz: Crawling Process
Pseudo code from the video:

start with tocrawl = [seed]
crawled = []
while there are more pages tocrawl:
pick a page from tocrawl
return crawled


The seed page where crawling begins.

### Finishing Crawl Web

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/nQl4F9uMvGU.mp4

Quiz: Finishing Crawl Web
Hint: at some point, you will have to call get_page on page. It seems counterintuitive, but we use the word page to refer to both the url and the html of a webpage. The get_page procedure takes a url and returns html.

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/sII5zYOFywM.mp4

### Conclusion

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Qm4wJi2Me6Y.mp4

## Problem Set

### Product List

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/RTPL87SBv6o.mp4

### Greatest

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/okAtgJROqgs.mp4

### Lists of Lists

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/xk4fB0yfq58.mp4

### Max Pages

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Mh0Rw9fV9UU.mp4

### Max Depth

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/TRNyIIrB73Q.mp4

## Problem Set(Optional)

### Exploring List Properties

showing list1 and list2:
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, [5, 6]]


Notes on lists

## Responding to Queries

### Introduction

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/gXkELecZYlk.mp4

Welcome to Unit 4!

The notes for Unit 4 are here: PDF and web.

By the end of this unit, we’ll have a working search engine that can crawl and build an index of set of web pages, and respond to keyword queries!

You’ll also learn about designing and using complex data structures that build on the list structure we introduced in the previous unit.

### Lookup

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/bVjECgrnKj4.mp4

### Building the Web Index

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/aRteT5uKqfg.mp4

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/i3V-Aw4y-hg.mp4

### Startup

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/1XElSoLZfKQ.mp4

### The Internet

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/ePw5eGJXuw8.mp4

### Smoke Signals

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/8B6WSjA7DG8.mp4

### Bandwidth

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/P83jTqcQ10A.mp4

### Buckets of Bits

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/IS7TO_lLXFE.mp4

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/jG252FaodkA.mp4

### Making a Network

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/jFElXIkFEhc.mp4

### Protocols

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/0U31-O4oEPc.mp4

### Conclusion

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/1wKlRFhn4zg.mp4

## Lesson 16 Problem Set

### Ben Bitdiddle

Ben Bitdiddle suggests changing the index code by replacing the add_to_index and lookup procedures with the ones shown below the question.

def add_to_index(index, keyword, url):
index.append([keyword, url])

def lookup(index, keyword):
result = []
for entry in index:
if entry[0] == keyword:
result.append(entry[1])
return result


This changes the structure of index, but suppose the only way we use index is by calling add_to_index and lookup. How would this affect the search engine?

**It would produce the wrong results for some lookup queries.

It would produce the same results for all queries, but lookup would sometimes be faster than the original code.

It would produce the same results for all queries, but add_to_index would be faster and lookup would usually be slower than the original code.

It would produce the same results and take the same amount of time for all queries**

Old Code
for entry in index:
if entry[0] == keyword:
entry[1].append(url)
return

    # not found, add new keyword to index
index.append([keyword, [url]])

def lookup(index, keyword):
for entry in index:
if entry[0] == keyword:
return entry[1]
return []


https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/h5KA5t8yo3I.mp4

## How Programs Run

### Introduction

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/XJfrUOoQSOI.mp4
Welcome to Unit 5!

The notes for Unit 5 are here: PDF and web.

The main goal of Unit 5 is to learn about how computer scientists measure cost, which is mostly about understanding how the resources needed to run a program scale with the size of its input. We’ll also learn about implementing and using a hash table, a data structure that will massively improve the performance of our search engine.

It was a privilege to meet with Gabriel Weinberg, the founder of DuckDuckGo, to film this introduction. DuckDuckGo protects the privacy of its users and gets around 3 million searches per day. Gabriel’s blog is full of interesting articles about computing and startups.

### Making Things Fast

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/JIeuI6mknUk.mp4

### Stopwatch

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/ms0iENK29jA.mp4

### Spin Loop

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/hBw8qWGHrEs.mp4

### Make Big Index

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/zxfXpB6U_0w.mp4

### Index Size Vs. Time

>>> time_execution('lookup(index10000, "udacity")')
(None, 0.000968000000000302)

>>> time_execution('lookup(index10000, "udacity")')
(None, 0.000905999999863066)

>>> time_execution('lookup(index100000, "udacity")')
(None, 0.008590000000002652)

>>> time_execution('lookup(index100000, "udacity")')
(None, 0.008517999999998093)


https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/5DHrCwtBuGU.mp4

### Lookup Time

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/PsCqA6fJ1hk.mp4
This quiz depends on the code for make_big_index(size) from a few segments before:

def make_big_index(size):
index = []
letters = ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a']
while len(index) < size:
word = make_string(letters)
for i in range(len(letters) - 1, 0, -1):
if letters[i] < 'z':
letters[i] = chr(ord(letters[i]) + 1)
break
else:
letters[i] = 'a'
return index


This quiz depends on the code for make_big_index(size) from a few segments before (as well as the code for lookup and add_to_index):
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/WtfufPxl8Mw.mp4

### Making Lookup Faster

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/AArXvYMTCOM.mp4

### Hash Function

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/xzQy09kBswM.mp4
ord()
ord('a')->97
chr()

### Modulus Operator

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/b2J5RyLdNy8.mp4

### Better Hash Functions

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/9vGXclxo8Kc.mp4
My claim about the performance being better with the % buckets inside the loop is (often, and possibly always?) incorrect. Some enterprising students have done experiments showing this, and there is more discussion in the forum.

### Testing Hash Functions

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/TjWwI-MvEhI.mp4

### Empty Hash Table

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/e3gDr_MWqDA.mp4

### Finding Buckets

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/e_ZLxgElqks.mp4

### Lookup

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/cKkaGzt9pwk.mp4

### Update

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/UPiqKaXshfw.mp4

### Dictionaries

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Tne9hgBqCUY.mp4

### Using Dictionaries

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/5wTxBLzR5aM.mp4

### Population

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/H-eGAkgjg_s.mp4

### A Noble Gas

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/qJNsfRfFw-c.mp4

### Modifying the Search Engine

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/ncC1XboU_lo.mp4
Here’s the code in a more readable format:

Here’s the code in a more readable way: (thanks to Christina-49) def get_all_links(page): links = [] while True: url, endpos = get_next_target(page) if url: links.append(url) page = page[endpos:] else: break return links

Here’s the code in a more readable format: (thanks to Christina-49)
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/NBJx7q8XNpE.mp4

### Changing Lookup

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/avNhSME0qxQ.mp4

### Coming Up Next

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/-qYyswP4FqI.mp4

## Problem Set

### Growth

#### Measuring Cost

For which of these procedures does the worst-case running time scale linearly in the number of elements in the input list p? (You may assume that the elements in the list are all small numbers)

#### Sum_list

def sum_list(p):
sum = 0
for e in p:
sum = sum + e
return sum
Has_duplicate_element
def has_duplicate_element(p):
res = []
for i in range(0, len(p)):
for j in range(0, len(p)):
if i != j and p[i] == p[j]:
return True
return False
Mystery
def mystery(p):
i = 0
while True:
if i >= len(p):
break
if p[i] % 2:
i = i + 2
else:
i = i + 1
return i


Peter muddles up odd and even in the last question. The statement p[i] % 2 is True whenp[i] is odd and False when it is even, so the worst case is when all the elements in the list are even.
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/tlFdhxXJzaw.mp4

### Hash String

#### Hash String

Suppose we have a hash table implemented as described in Unit 5 using the hash_string function.

def hash_string(keyword, buckets):
h = 0
for c in keyword:
h = (h + ord(c)) % buckets
return h


Which of the following are true statements?

##### Statement 1

The number of string comparisons done to lookup a keyword that is not a key in the hash table may be less than the number needed to lookup a keyword that is a key in the hash table.

##### Statement 2

We should expect the time to lookup most keywords in the hash table will decrease as we increase the number of buckets.

##### Statement 3

It is always better to have more buckets in a hash table.

##### Statement 4

The time to lookup a keyword in the hash table is always less than the time it would take in a linear time list (as used in Unit 4).

### Is Offered

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Qq8Hd290n5c.mp4

### When Offered

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/hftOGwEW4qY.mp4

### Involved

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/ej9rXa13kr4.mp4

### Refactoring

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/EU9NvdGoAt4.mp4

### Memoization

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/_aPiXzmiems.mp4

## Q&A

### Hash Tables

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/eiktSrhdrxs.mp4

### Rehashing

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/UMsVMW2S53w.mp4

### Importing Libraries

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/G3ovp33txfc.mp4

### Programming Literacy

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/0oXF2nOTX6I.mp4

## How to Have Infinite Power

### Infinite Power

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/emhiUKHuBXY.mp4
The notes for Unit 6 are here: PDF and web.

This unit introduces what I think is the most fascinating and powerful idea in all of computing - recursive definitions. Understanding them requires some mind-bending gymnastics, but once you do, you will find elegant and powerful new ways to think about nearly all problems you encounter.

The course moves through this pretty quickly, but fortunately many students have contributed great additional resources that explain things very well and with more detail than I do in the course, and give you more practice with recursive programs.

Here are a few that I think are especially good:

Yet Another Attempt to Explain Recursion by Goldsong
Understanding Recursion: The Stack Model by Charles Lin
StG’s Recursion Collection by Sam the Great

### Counter

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Ap3okJ5jIUE.mp4

### Recursive Definitions

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/LinhpqM4cCg.mp4

### Recursive Procedures

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Wa6y0I_uojk.mp4

### Recursive Factorial

Around ~0:06, Dave says that factorial takes a positive whole number as its input, but factorial can also take 0 as an input as well. Instead, then, the input to factorial can be any positive integer or 0.

(Side note: whole numbers are defined differently in different contexts, but they are often defined as all of the non-negative integers. This means the whole numbers are 0, 1, 2, 3, 4…, and if we use this terminology, factorial could take any whole number as its input.)

Note: If you get a The server encountered an error. Please try running again. error, that may mean that your program is not terminating when tested. Make sure your recursion will eventually reach a base case.

### Palindromes

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/LTZXRoLZaJQ.mp4

### Recursive Vs Iterative

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/kirruxKHaqk.mp4

### Bunnies

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/S6wCTLG8BJg.mp4

### Divide and Be Conquered

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/eBu1Z_FBwb4.mp4
Note that this is the standard mathematical definition of the Fibonacci sequence, which is a bit different from the counting rabbits motivation in the original problem. The mathematical sequence starts with 0, which is more elegant mathematically, but wouldn’t make as much sense for rabbits multiplying.

### Counting Calls

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Cai4WuKg4SM.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/bqF8QuYX8YA.mp4
At 1:58 minutes onwards, the formula should be fibo(36 - (n - 1)) = fibo(36 - n + 1) and not fibo(36 - n - 1).

### Faster Fibonacci

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/7k7tMKxH6Dg.mp4

### Ranking Web Pages

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/k32gyEM5H3Y.mp4

### Popularity

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/EP55W6keH7E.mp4

### Good Definitions

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/FX8RlDKEEiU.mp4
A note on the notation: friends(p) is a list of all friends of p.
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/HbLwTw6N-0s.mp4

### Page Rank

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/IKXvSKaI2Ko.mp4

### Altavista

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/T6AeBtfaLco.mp4
AltaVista was finally shut down in July 2013. Here’s an interesting article from the Washington Post: AltaVista is dead. Here’s why it’s so hard to compete with Google. (mostly an interview with Gabriel Weinberg).
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/0ZlFPQ2qQo0.mp4

### Urank

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/H8vrZMAllIY.mp4

### Implementing Urank

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/sR8EJLpWwb4.mp4

### Computing Page Rank

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/_ctzQdS3EfA.mp4

### Formal Calculations

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/YZ3kRWKL0DI.mp4

### Computer Ranks

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/sPaVbELrmh0.mp4

### Finishing Urank

rank(page, time) is defined as: ∑
​​

​d⋅rank(t−1,p)
​​ or:

rank(page, 0) = 1/npages

rank(page, t) = (1-d)/npages

     + sum (d * rank(p, t - 1) / number of outlinks from p)


Thanks to Henry for suggesting to add this.
The URLs have changed around a bit! Here’s a new index page you can start with to test out your search engine: https://www.udacity.com/cs101x/urank/index.html

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/k861qM5OqvU.mp4

### Search Engine

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/7IlDnp39b0U.mp4

## Problem Set

### Rabbits Multiplying

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/pcGGCOPPtmE.mp4

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/q_atgGWy57Y.mp4

## Problem Set 6 Starred

### Family Trees

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/SQ6508of_ZA.mp4

### Only a Little Lucky

The provided solution isn’t complete - it doesn’t actually include the ordered_search code, but only the code for sorting the pages.

Atlas7-115196 provided a more complete solution to this problem! See the forum post: http://forums.udacity.com/questions/100371211/corrected-udacity-solution#cs101

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/lI9O8wUEDFc.mp4

## Q&A

### Pythonic

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/2g6qtjwKkA0.mp4
Correction - Peter Norvig teaches class CS212.

### Python Versions

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/owH7bqKiR-g.mp4

### Using Recursion

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/VWyHjEh0tfA.mp4

### Recursion in Other Languages

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/siNYLJ1YaAc.mp4

### Pagerank

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/rN-5K_q4JDc.mp4

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/ulkWpQl6izE.mp4

### International Characters

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/9QbeX7LOl0g.mp4

## Past, Present, and Future of Computer

### Past, Present, and Future

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/4TChbk9pnxQ.mp4

### Themes

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/-6OLwm10pqs.mp4

### Overview

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/-atl1N1mvu0.mp4

### Computer Science

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/YBJk5Z5bAEA.mp4

### Computer Science

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/DIbtX0GqIA8.mp4

### Past of Computing

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/vvIj_PWFoyY.mp4

### Computer History Museum

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/ClTnWszPp3Q.mp4

### Babbage Engine

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/5nYcND7WjCY.mp4

### First Hard Drive

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/oSCCFDZLRgY.mp4

### Search Before Computers

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/F2DTZoa-zPo.mp4

### Search on the Web

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/mgR9sInLwfc.mp4

### Present of Computing

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/9fxDFZGwUiA.mp4

### Slac and Big Data

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/4_0sCB_csRI.mp4

### Mozilla

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/_IfqKBbEqck.mp4

### Getting Involved

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/56KQGpGOwLM.mp4

### Having an Impact

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/lL36LxpsXBI.mp4

### Benetech

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/FqQFwXOJTeU.mp4

### Future of Computing

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/EsTiQxNDQfo.mp4

### Text Analysis

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/679-n8LWaVo.mp4

### Energy Aware Computing

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/wLyAANVyJQM.mp4

### Computer Security

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/H87Yxc4p-C8.mp4

### Theory of Computation

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/W7nD3AMJDAI.mp4

### Quantum Computing

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/XafsCK3yk4U.mp4

### Stay Udacious

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/oDxqlHY6V1w.mp4

## Cumulative Practice Problems

### Triangular Numbers

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/tQplGM4DtTA.mp4

### Linear Time

For the procedures below, check the procedures whose running time scales linearly with the length of the input in the worst case. You may assume the elements in input_list are fairly small numbers.

def proc1(input_list):
maximum = None
for element in input_list :
if not maximum or maximum < element:
maximum = element
return maximum

def proc2(input_list):
sum = 0
while len(input_list) > 0:
sum = sum + input_list[0]   # Assume input_list[0] is constant time
input_list = input_list[1:]  # Assume input_list[1:] is constant time
return sum

def proc3(input_list):
for i in range(0, len(input_list)):
for j in range(0, len(input_list)):
if input_list[i] == input_list[j] and i != j:
return False
return True


https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/nnNQTjmc3DY.mp4

or

### Termination

For each of the procedures defined below, check the box if the procedure always terminates for all inputs that are natural numbers (1,2,3…).

def proc1(n):
while True:
n = n - 1
if n == 0:
break
return 3

def proc2(n):
if n == 0:
return n
return 1 + proc2(n - 2)

def proc3(n):
if n <= 3:
return 1
return proc3(n - 1) + proc3(n - 2) + proc3(n - 3)


https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/RBc-2ZVuH9E.mp4

## Challenging Practice Problems

### Stirling and Bell

There was a typo in the last test example.

# a->a, a->b, b->a, a->c, c->d, c->a links are reciprocal


# a->a, a->b, b->a, a->c, c->d, d->a links are reciprocal


### Elementary Cellular Automaton

Sorry about this. There is a mistake in the video in generation 3 for pattern 30, which makes all the following lines incorrect as well. The corrected output is:

...x....  (input)
..xxx...  ( generations = 1)
.xx..x..  ( generations = 2)
xx.xxxx.  ( generations = 3)
x..x....  ( generations = 4)
xxxxx..x  ( generations = 5)
.....xxx  ( generations = 6)


Additional information: Elementary Cellular Automaton at Wolfram’s Mathworld

https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Jc1vOOWfQaA.mp4

## Project Prep

### Project Description

#### Final Project Description

Congratulations on making it to the final project! Your job is to take simple text strings like “Alex likes Carla, Ryan, and Priya” and turn them into a social network. To do this, you must complete a number of required procedures, as described on the next screen. You must also create a “make-your-own” procedure.

Most of this project will take place inside the browser and most of it will be auto-graded. Feel free to share your final code with your peers in the Discussion Forum for additional feedback.

If you have any questions, ask on the Discussion Forum!