alyssaq

Definitions

NP = Non-deterministic Polynomial time.
It is the set of all decision problems for which the answer 'yes' have verifiable proofs to prove that the answer is indeed 'yes'.
Non-deterministic = different behaviours on different algorithm run. E.g. Merge sort
Polynomial time = algo has an upper-bound run-time by a polynomical expression in the size of its inputs. E.g. O(n log n)

Complexity classes of decision problems (yes-or-no)

P: Solvable in deterministic Turing machine in polynomial time
NP: Solvable in non-deterministic Turing machine in polynomial time

alyssaq

HTTP Fundamentals

HTTP Resources and Messages

What happens when you type a url in the address bar?

HTTP Request: URL

http://www.google.com represents a particular resource on the web.
Resources are anything you want to interact with on the web: images, videos, pages, services.

alyssaq

HTTP Fundamentals 2

HTTP Connections

How does traffic flow through the Internet? What happens in the network layers in a HTTP transaction?

Network Layers

HTTP = application layer protocol (OSI 7) - allows applications to communicate over the network. E.g. Web browser to web server (Apache)
HTTP specifications does not mention how messages move across the network and reach the server. That's where lower layer protocols come to play.

alyssaq

Arrays in javascript are simply objects.

Access - O(1) Beware in IE
Appending (push) - Amortized O(1) (sometimes resizing the hashtable is required;)
Prepending (unshift) - O(n), since it requires reassigning all the indexes
Insertion - Amortized O(1) if the value does not exist. O(n) if you want to shift existing values (Eg, using splice).
Deletion at end (pop) - O(1)
Deletion anywhere else (slice) - O(n) since indices need to be reassigned.
Swapping - O(1)

alyssaq

#Sorting and Searching Sorting is the basic building block of many algorithms. Interesting design of algorithms appear in the context of sorting: divide-and-conquer, data structures, and randomized algorithms.

Common Sorts

Merge sort:

• Advantages: suitable for linked list, suitable for external sort.
• Disadvantages: need extra buffer holding the merged data.

Insertion/Selection sort:

• Advantages: easy to implement.

alyssaq

Data Structures

##Dictionaries A set of n records, each identified by one or more key fields.

Problem: Efficiently locate, insert and delete the record associated with any query key q.

Data structures include hash tables, skip lists and balanced/unbalanced binary search trees.

###Representations

alyssaq

The identity (===) operator behaves identically to the equality (==) operator except no type conversion is done, and the types must be the same to be considered equal.

0 == '0' //true. '0' was type converted to integer
0 === '0' //false. As expected

alyssaq

C++ STL Containers

###Containers Forward Container: forward iterators - increment only in O(1)

• begin(), end()
• All containers

Reversible Container: bidirectional iterators - increment and decrement in O(1)

• rbegin(), rend()

alyssaq

// Use Gists to store code you would like to remember later on
console.log(window); // log the "window" object to the console

alyssaq

#Publish a folder to gh-pages

Scenario: You have a local target folder app that you wish to pubish to gh-pages

Add the target folder to to your .gitignore repository.
Clone the repository to the target folder app, delete the contents and add your files to be published

$ git clone https://github.com/alyssa/polymer app
$ cd app