LESSONS
How to manage data
Measure Udacity
|
|
Find Element
|
|
Union
|
|
Pop Quiz
31.1
Get All Links
Print All Links
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Inr_DYUqxk8.mp4
Quiz: Print All Links
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 return urllib.urlopen(url).read() except: return ''
Include this code above your get_next_target() procedure in your answer.
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/BFYeJzcejxM.mp4
Links
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/xssLR71EuUw.mp4
Starting Get All Links
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/m3oEwba-yxU.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/f4L30M_25AI.mp4
Updating Links
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/8krkKyimMUA.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/4-5169UHZTM.mp4
Finishing Get All Links
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/E3_IlnR_j44.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/LUnnw_TBxPI.mp4
Finishing the Web Crawler
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/BWKxjRDadkI.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 add that page to crawled add all the link targets on this page to tocrawl return crawled
The seed page where crawling begins.
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/_DESjvmuSsA.mp4
Crawl Web
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/bI3rP7tAGdA.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/XRkqyIvx39w.mp4
Crawl Web Loop
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/h4pJFmz7l1g.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/jRm4rYw1w6c.mp4
Crawl If
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/lZhKW6QTmX0.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/sopj7b5XEfk.mp4
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
Lists
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/fzaaNzGDcCg.mp4
Mutating Lists
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/kFEMVfPAP-A.mp4
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
Sudoku
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/60wESSZRSp0.mp4
Problem Set(Optional)
Exploring List Properties
|
|
showing list1 and list2:
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, [5, 6]]
Symmetric Square
|
|
Mean of a List
|
|
Problem Set(Optional 2)
Antisymmetric Square
|
|
Recognize Identity Matrix
|
|
Numbers in Lists
|
|
Frequency Analysis
|
|
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.
Data Structures
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/pv5-RgG1pdk.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/nNEXCEH0dEw.mp4
Add to Index
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/B2J-bDQ4M1o.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/SGkb6vqS7zA.mp4
Lookup
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/hzDJhLS4yCo.mp4
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
Add Page to Index
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/_5rpzWzFnJM.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/i3V-Aw4y-hg.mp4
Finishing the Web Crawler
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/dQjsf-4cWo0.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/cPKnNmFTS80.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
Networks
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/dy4KsLNw1lU.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/_8Xgtd4j7j8.mp4
Smoke Signals
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/8B6WSjA7DG8.mp4
Latency
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/6_1akTCAnt4.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/5NoF37dKsAI.mp4
Bandwidth
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/P83jTqcQ10A.mp4
Bits
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/6HCFOyZI9tA.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/4OxrAgA30T8.mp4
Buckets of Bits
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/IS7TO_lLXFE.mp4
What Is Your Bandwidth?
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/jG252FaodkA.mp4
Traceroute
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/kU30juVBCBg.mp4
Traveling Data
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/bQqvRI8NSFo.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/8csDnLICd4w.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
Data Structures
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/6rE8vvdYn2c.mp4
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
def add_to_index(index, keyword, url):
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
Networking
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/rl7zOmndGLY.mp4
Better Splitting
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/alpdXaaSfGI.mp4
Improving the Index
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/GD98Z_3cANU.mp4
Counting Clicks
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/XAb3iFZfOl0.mp4
Time Spent at Routers
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/jqNiHcMsS_Y.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/TWEE2f1w55U.mp4
Problem Set(Optional)
Word Count
Latency
Converting Seconds
Download Calculator
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
Measuring Speed
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/5vnXm71KECU.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
Predicting Run Time
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/HBwT29hWXrs.mp4
Make Big Index
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/zxfXpB6U_0w.mp4
Index Size Vs. Time
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/yYm5t1wLarM.mp4
Sample timings:
>>> 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)
add_to_index(index, word, 'fake')
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
Worst Case
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/TBylO5VopA4.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/26jeGBtszyk.mp4
Fast Enough
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/lSakl4WtFiE.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/rbYT97miQMY.mp4
Making Lookup Faster
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/AArXvYMTCOM.mp4
Hash Table
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/KxGQbWGPeak.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/fdddZ5zcHyI.mp4
Hash Function
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/xzQy09kBswM.mp4ord()
ord('a')
->97chr()
Modulus Operator
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/b2J5RyLdNy8.mp4
Modulus Quiz
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/l8cjHI9UbW4.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/nmV96-OcGi4.mp4
Equivalent Expressions
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/yoUU_QDJv4o.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/TRuWp6uRBKI.mp4
Bad Hash
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/gGSY4yAusdk.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/qn99D3acUnA.mp4
Better Hash Functions
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/SKbp6T6C-0Q.mp4
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
Keywords and Buckets
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/2cL69wIOpVk.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/0k-hAMfA5uY.mp4
Implementing Hash Tables
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/sRfcPW1Rj_4.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/3AN9tyu_w-I.mp4
Empty Hash Table
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/a_NjE-wJQGc.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/e3gDr_MWqDA.mp4
The Hard Way
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/cpAkNOOdzLw.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/GY8OtZj6LZA.mp4
Finding Buckets
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/0ZOo7GAm2qU.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/e_ZLxgElqks.mp4
Adding Keywords
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/VFulPFO-OS0.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/ge6HmR7EuDI.mp4
Lookup
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/vJJ0wakAu7s.mp4
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
For further information on Hash Tables in Python, please refer to this article here
Population
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/em3CWlSaEKY.mp4
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/OdToP6LQRoc.mp4
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
Problem Set(Optional)
Shift a Letter
Shift n Letter
Rotate
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
Long Words
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/-PhZlJuDf_o.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/XzJO5xc3QIk.mp4
Counter
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Ap3okJ5jIUE.mp4
Counter Quiz
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/6s-aT1rO3JQ.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/YnPLnU9D3mQ.mp4
Expanding Our Grammar
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/qYsl757ShjA.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/nU2DBYNw1jM.mp4
Recursive Definitions
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/LinhpqM4cCg.mp4
Ancestors
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/_AQRlt9UA4o.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Ip3vojOsIkI.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.
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/gWoWZHonPdE.mp4
Palindromes
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/zWnI5eACaLM.mp4
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/E6oGm_Z2aQk.mp4
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/oJAHMzgSTyA.mp4
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
Circular Definitions
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Rxp6JuoNqL0.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/YUwZCZVtLaU.mp4
Relaxation
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/e7-gweWZ0io.mp4
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/kpXVV8aiZFU.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/B5lAVjLd76Q.mp4
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
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/GovJzUltdL8.mp4
rank(page, time) is defined as: ∑
p∈inlinks
outlinks
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) over all pages p that link to this page
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
Recursive Grammars
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/Ej9obZ0QECY.mp4
Rabbits Multiplying
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/pcGGCOPPtmE.mp4
Spreading Udaciousness
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/q_atgGWy57Y.mp4
Deep Count
|
|
Feeling Lucky
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/6qVB4lZmzMc.mp4
Problem Set 6 Starred
Family Trees
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/SQ6508of_ZA.mp4
Khayyam Triangle
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/i8X3KHanfXE.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
Challenges in Search
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
Open Source
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/TUBAD93kCfA.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
Pick One
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/K2s3b4XTaN0.mp4
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
Remove Tags
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/5LrTUeawyfI.mp4
Date Converter
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/YgW5c4mH19g.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
Find and Replace
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/-xUQEeXjC8g.mp4
Longest Repetition
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/LWSvPPfH9Cw.mp4
Deep Reverse
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/aYLkoPSiiG0.mp4
Challenging Practice Problems
Stirling and Bell
|
|
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/TJ4M9ZyAZ3I.mp4
Combating Link Spam
|
|
There was a typo in the last test example.
# a->a, a->b, b->a, a->c, c->d, c->a links are reciprocal
should read
# a->a, a->b, b->a, a->c, c->d, d->a links are reciprocal
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/hP-UDkuUL0o.mp4
Elementary Cellular Automaton
https://s3.cn-north-1.amazonaws.com.cn/u-vid-hd/M_pkidxeGMY.mp4
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
Code Editor
A Place to Try Things Out
|
|
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!
Gamer’s Network
|
|