DFA & NFA

In the course "Formal Language", we learned about "DFA and NFA", and here's my study notes.

Reference

1. http://stackoverflow.com/questions/3978438/dfa-vs-nfa-engines-what-is-the-difference-in-their-capabilities-and-limitations
2. DFA http://en.wikipedia.org/wiki/Deterministic_finite_automaton
3. NFA http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton

Definitions

Finite Automaton

A finite automaton is a processor that has states and reads input, each input character potentially setting it into another state.

 In my opinion, we can see this as a finite state machine.

Deterministic Finite Automaton (1943)

A finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string. 'Deterministic' refers to the uniqueness of the computation.

In one state at a time.

Nondeterministic Finite Automaton (1959)

A finite state machine that (1)does not require input symbols for state transitions and (2)is capable of transitioning to zero or two or more states for a given start state and input symbol.

In more than one state at a time.

Difference between DFA and NFA

• all transitions are uniquely determined
• an input symbol is required for all state transitions
• DFAs are easier to understand, but NFAs are generally smaller. 

Upload File using jQuery-File-Upload

Original Code

https://github.com/blueimp/jQuery-File-Upload

My Work

http://heron.nctucs.net/upload/

This is cool jQuery library which allows the user to upload their files with cool interface. It also support "drag & drop", so it's much faster for people to select files. However, security may be a big issue in this case.

Problems I Met & How I Solved Them

Error, unable to upload the file

Solving this problem by giving right permission to the folder which the website is going to save files (in the example code, it's ./server/php/files). Make sure that "www-data" is able to "write" the folder.

The thumbnails are not showing up

I directly type in the URL of the thumbnails, and the browser showed a message asked me to read the error log file. In the log file, it says:

Invalid command 'Header', perhaps misspelled or defined by a module not included in the server configuration, referer: http://heron.nctucs.net/upload/index.html

So, here my solution from this website:

ln -sf /etc/apache2/mods-available/headers.load /etc/apache2/mods-enabled/headers.load

Internet.org

Original Document

https://fbcdn-dragon-a.akamaihd.net/hphotos-ak-ash3/851578_534669043269870_1216439060_n.pdf

Facts (sentences from the paper)

• In its early days, Facebook ran on a single server that cost $85 a month and had to handle traffic for every Harvard student who used the service.
• Facebook.com was first coded in PHP, which was perfect for the quick iterations that have since defined our style of product rollouts and release engineering.
• Facebook has grown to 5,299 employees and 1.15 billion users as of June 2013.
• Every day, there are more than 4.75 billion content items shared on Facebook, more than 4.5 billion "Likes," and more than 10 billion messages sent. More than 250 billion photos have been uploaded to Facebook, and more than 350 million photos are uploaded every day on average.
• To build more efficient apps, Facebook is working to solve:
• Diversity of devices and operating system
• Geographic diversity
• 1.15 billion people
• 70 different languages
• Network connectivity
• Testing to ensure consistent network connectivity (Air Traffic Control to simulate different network conditions right inside Facebook' offices)
• Consuming less data
• first solution, offer different resolution photos, https://www.facebook.com/note.php?note_id=76191543919
• reliable and scalable image cache had to be developed on Android to avoid redownload

Things

• Hip Hop for PHP
• https://www.facebook.com/note.php?note_id=280583813919
• allows 50 percent more traffic to be processed on the same machines than original PHP
• http://github.com/facebook/hiphop-php
• Hip Hop interpreter (HPHP)
• Hip Hop Virtual Machine
• https://www.facebook.com/note.php?note_id=10150415177928920
• a 500 percent increase in throughput for Facebook compared with Zend PHP 5.2
• Open Compute Project
• http://www.opencompute.org/
• Corona
• More efficient scheduling framework that separates cluster resource management from job coordination.
• https://www.facebook.com/notes/facebook-engineering/under-the-hood-scheduling-mapreduce-jobs-more-efficiently-with-corona/10151142560538920
• Avatarnode
• Optimizing HDFS is crucial to keeping our systems efficient and reliable.
• WebP
• intended to replace both PNGs and JPEGs, providing substantial reduction in image size at an equivalent image quality
• https://developers.google.com/speed/webp/
• "vanity free"
• eliminates anything from the designs that isn't necessary to the function of that device

What I learned

Facebook.com was first complemented using PHP, what we all think it's easy and fast for developing. Then, they started to work very deep into PHP when more people using Facebook. This is new to me, what I thought is that this kind of websites doesn't go really deep into the technology but learning human psychology/business/etc insteads.