Udacity CS 101: Unit 6

Okay so I finally completed Unit 6, and it was difficult. It seems like the advancement to PageRank was a very big jump. Maybe that’s why people at Google (and other search engine like DuckDuckGo) have to be really really smart. I didn’t understand what was the damping function was for, and even after watching the videos quite a few times I still did not get it. But I guess that is actually more Math and Computer Science, although one can argue that both fields are intertwined quite closely! I sure hope you understand it! Check out Wikipedia’s entry on Page Rank for more information!

This Udacity post references Udacity CS 101 Unit 6.
Advertisements

Udacity CS 101: Recursive

UPDATE: I wrote this post before heading to Chapter 12 of Unit 6, and I just realized that this post contains the answer to the question! So stop readying if you have not attempted!

You might remember seeing this term somewhere in my blog before, and today we are going to visit recursive functions again, under the guidance of Professor Evans. Recall the Fibonacci sequence

1, 1, 2, 3, 5, 8, 13, 21 ...

1, 1, 2, 3, 5, 8, 13, 21 …
Image courtesy of Wolfram MathWorld

1, 1, 2, 3, 5, 8, 13, 21 …

Each number is the sum of its two preceding numbers ( 2 = 1 + 1, 21 = 8 + 13).

In every recursive definition, there are two cases, the base case, and the recursive case. Continue reading

Udacity CS 101: Dictionary

We are introduced to another complex data types in Python: Dictionary. Dictionaries are created using curly braces, and entries in a dictionary are key-value pairs:

Dictionary

Something similar, but not.
Image courtesy of Wikipedia

alphabets = { 'a':1, 'b':2, 'c':3 }

Essentially a dictionary functions like a hash table, given a particular key, a its value is returned. A dictionary is mutable, just like a list. After creating a dictionary, we can append new key-value pairs, and we can modify individual key and values. Continue reading

Udacity CS 101: Hash

A hash function, is a function that maps a big set of data to a smaller set of data. For example, a hash function can map people’s names, to an integer between 1 and 10. Hash is explained in the video using terms like keys and buckets. In this case, the keys are the names, and there are 10 buckets, numbered 0 to 9.

A Hash Function

An example of a hash function.
Image Courtesy of Wikipedia

A good hash function has certain properties. It tries to spread the keys evenly over all the buckets, so the size of each buckets after hashing is roughly the same. And for each key, it will definitely output a hash value that is valid, i.e. less than or equals to the numbers of buckets available. Continue reading

Udacity CS 101: Speed

Very quickly we have moved past Unit 4. The Homework 4 series is quite challenging and might take a while to solve. But solving them just gave me a boost of adrenaline, which explains why I’ve started on Unit 5, 2 weeks ahead of schedule! Join me if you are on a roll too, if not you can always revisit this page and the subsequent articles.

Unit 5 starts with talking about the the cost of running programs. The problem of the cost is called Algorithm Analysis, and there are people with careers devoted to this field. It is actually a fundamental problem of computation. An algorithm is a well-defined procedure that can be executed mechanically, will always finish and produce the correct result.

The cost of an algorithm is not measured by dollars and cents, but rather by speed and storage. Algorithm analysis is about understanding how the inputs will affect the time taken and storage memory required for algorithm to complete. Or to phrase it different, when the inputs increase in size, how does the time and storage requirement scale with relation to size?

We are introduced to a new python library called time:

Measure how much time your program takes
Image courtesy of http://catherinethegame.wikia.com

Continue reading

Udacity CS 101: Basics of the Internet

The Internet is basically a network

A huge network.
Image courtesy of http://blog.brosix.com/

And Professor Evans defined network as a group of entities that can communicate even if not directly connected. So a network has a minimum of two persons/computers, and there has to be a way for these elements to communicate without direct connection. Our Internet is built in this way. When you connect to this website, you do not connect to WordPress directly. Your computer will send this request to view my website to your router, and router to your Internet Service Provider, then to the web host which hosts WordPress. There might be even more intermediate steps in between! And all these happen within seconds.

The time from your request to view this site (the time you press enter after entering the URL), till the WordPress.com receives your request is called the latency. Latency is now measured in milliseconds, which is a thousandth of a second. Eventually we might hit even faster speeds, measuring in micro seconds or nano seconds! Bandwidth is the amount of information that can be transferred in a unit time, usually a second, and it is measured in bits per second or even Mbps, mega-bits (a million bits) per second. So note the difference!

This Udacity post references Udacity CS 101 Unit 4 Chapters 1, 2, 3, 4, 5, 6 and 7.

Udacity CS 101: Making an Index

We’ve mentioned data structures before, and in this case its to do with how we should create our index such that it is quick to search for a particular keyword in the index, and retrieve the location of the keyword (in the form of a URL). Here a new method is introduced to us, split():

find = 'This is a sentence!'

print find.split() # will give us ['This','is','a','sentence!']

This method is useful for splitting up text by ‘space’, but as you can see it’s not very good at recognizing words and punctuation. In the example above, ‘sentence!’ is recognized as a word, so if we base our keyword search on the list returned by this method, we will miss out on the keyword ‘sentence’, because it does not have the exclamation mark! And we definitely know that they mean the word.

Continue reading