10 Papers Every Programmer Should Read

Interesting.

- 10 Papers Every Programmer Should Read (At Least Twice)
- 10 Papers Every Software Architect Should Read (At Least Twice)

Disk scheduling algorithms

Several common disk scheduling algorithms:

First Come First Served (FCFS)
Shortest Seek Time First (SSTF)
SCAN (Elevator algorithm)
Circular SCAN (C-SCAN)
LOOK
Circular LOOK (C-LOOK)

References:
[1] Disk scheduling
[2] Wiki: elevator algorithm
[3] Example of calculation

Lecture by Vladimir Vapnik

Lecture on Empirical Inference by Vladimir Vapnik.

Coin tossing

Coin tossing is a game form ancient time. Yet there are interesting issues related and research going on.

One example is to simulate an unbiased coin with a biased one. von Neumann gave a simple method: HT is counted as Head, TH is counted as Tail, HH and TT are discarded. This can have extension to be more efficient in the sense of needed less number of tosses per decision though, e.g., HHTT can be counted as Head, TTHH can be counted as Tail as well [2].

Search "biased coin toss" would give some interesting research papers on relevant issues. Some examples are:

[1] Optimal random number generation from a biased coin (2005)
[2] Tossing a Biased Coin
[3] Tree algorithm for unbiased coin tossing with a biased coin (1984)
[4] "Topic 5: random generation" from CSE 103: PROBABILITY AND STATISTICS -- Readings

OLE with Perl

Perl can do many things beyond normal expectation. One example is with OLE objects. If you have MS Office installed on your computer, you can try the following code. It creates a word document and saves as C:\test.doc. You will see the Word document automatically opening up, adding lines and closing down. This demonstrates the capability of Perl to manipulate MS Office files. Application is such as automatic business report generation.

#!\usr\bin\perl -w
# http://www.adp-gmbh.ch/perl/word.html
# http://www.xav.com/perl/faq/Windows/ActivePerl-Winfaq12.html
# http://www.ngbdigital.com/perl_ole_word.html

use warnings;
use strict;

use Win32::OLE;

my $word = CreateObject Win32::OLE 'Word.Application' or die $!;
$word->{'Visible'} = 1;

my $filename = "C:\\test.doc";
my $document = $word->Documents->Add;

my $selection = $word->Selection;

$selection -> TypeText("Hello HomeTom");
$selection -> TypeParagraph;
$selection -> TypeText("How are you doing today?");
$selection -> TypeParagraph;

$selection -> TypeText("Great. How about you?");
$selection -> {'Style'} = "Heading 1";

$selection -> TypeParagraph;

my $heading_1 = $document->Styles("Heading 1");
my $heading_1_font = $heading_1 -> Font;

$heading_1_font -> {Name} = "Bookmann";
$heading_1_font -> {Size} = 20;
$heading_1_font -> {Bold} = 1;

# Save As
$word->ActiveDocument->SaveAs({FileName => $filename});

$selection -> Typeparagraph;
$selection -> TypeText("Now save and exit after 3 seconds");

sleep 3;

$word->Documents->Close;
$word->Quit;

1;

Min edge coverage problem

Problem: Given a directed graph, find a minimal set of vertices which touch all edges
within a graph.

This is a NP-complete problem. No polynomial time solution exists.

One solution is to get powerset of all vertices, then for each vertice subset, check if it covers all edges in the graph. Return the subset with the smallest size.

min_size = Infi;
set_index = -1;
Generate all possible vertex set S;
for all set si in S
  if union of edges covered by each vertex in set si == E
    if (si.size() < min_size)
      min_size=si.size();
      set_index = i;
return i;

This solution is from Careercup Top 150 Questions.

Architecture of high-throughput, scalable web application

The points here are taken from this link (In Chinese).

A. Some notes from the book Building Scalable Web Sites (ISBN 0596102356, 2006, 352 pages).

1. Scale up a web application
   - vertically scale up: increase setting of single machine (memory, CPU).
   - horizontally scale up: add more machines
2. Redundancy
   - Back up: hot back up (online backup), cold back up (offline backup).
3. Load balancing
   - session/session-less load balancing
   - hardware/software load balancing
4. Cache

B. Article by Ni Haitao.

1. Use static html: convert dynamic content to static html.
2. Separate image/graphics server from application server.
3. Use database cluster instead of single database.
4. Use Cache. E.g.
   Apache - mod_proxy, squid; 
   Linux - memcached; 
   PHP - Pear cache, eaccelerator, Apc, XCache.
5. Use mirror site.
6. Load balancing.
   - hardware 4-layer exchange
   - software 4-layer exchange
   - 7-layer exchange