10.22.2008

Read My Lips: Apple Is a Netbook Maker - Bits Blog - NYTimes.com - Sent Using Google Toolbar

Read My Lips: Apple Is a Netbook Maker - Bits Blog - NYTimes.com

Read My Lips: Apple Is a Netbook Maker

By John Markoff

(UPDATED 10/22 1:20 p.m. to clarify a source)

Steven P. Jobs appeared as a surprise "special guest" on Apple's earnings call Tuesday afternoon.

Mr. Jobs, Apple's chief executive, has not taken part in one of the company's conference calls with analysts since 2000, according to the company. His appearance served to underscore a number of points.

First, he sounded healthy, intense and on top of his game. Second, his statements about Apple and the economy suggest that the company may do much better at surviving a deep downturn than the rest of the consumer electronics industry. (No transcript is available yet but Silicon Alley Insider live-blogged the call.)

Mr. Jobs noted in particular the loyalty of Apple customers and suggested that while they might delay purchases, it was unlikely they would leave the computer maker for competitors.

Mr. Jobs also said that Apple has $25 billion in the bank and no debt, and the company plans to use its capital in creative ways to innovate and steal market share. He appeared to dismiss the idea that Apple might use the cash to buy back its stock and give a windfall to shareholders that way.

When a financial analyst said that Apple currently had enough money in the bank to hire all of the engineers in Silicon Valley for a lifetime, Mr. Jobs responded that the suggestion was a good idea.

But the most fun on the conference call came when he parried analysts' questions about new product areas that Apple might or might not enter. A recurring question among Apple watchers for decades has been, "When is Apple going to introduce a low-cost computer?

Mr. Jobs answered that decades-old complaint by stating, "We don't know how to build a sub-$500 computer that is not a piece of junk." He argued instead that the company's mission was to add more value for customers at current price points.

However, he gave a more nuanced answer to the question of whether Apple plans to jump into the "nascent" market for netbooks, essentially restating his comments on the question from last week at the Macbook introduction in Cupertino by saying the company was taking a wait-and-see attitude.

At the same time, he noted that the company already had a powerful entry in the category: the iPhone. (By that standard, Apple is already the dominant netbook manufacturer by orders of magnitude.)

Mr. Jobs also said the company "had some pretty interesting" ideas if the category continues to evolve.

UPDATED: That would seem to confirm findings that a search engine company shared with me on condition that I not reveal its name: The company spotted Web visits from an unannounced Apple product with a display somewhere between an iPhone and a MacBook. Is it the iPhone 3.0 or the NetMac 1.0?

10.21.2008

Longest common substring problem - Wikipedia, the free encyclopedia - Sent Using Google Toolbar

Longest common substring problem - Wikipedia, the free encyclopedia

Longest common substring problem

From Wikipedia, the free encyclopedia

Jump to: navigation, search

The longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings. It should not be confused with the longest common subsequence problem. (For an explanation of the difference between a substring and a subsequence, see substring).

Contents

[hide]

[edit] Example

The longest common substrings of the strings "ABAB", "BABA" and "ABBA" are the strings "AB" and "BA" of length 2. Other common substrings are "A", "B" and the empty string "".

 ABAB   |||   BABA   || ABBA 

[edit] Problem definition

Given two strings, S of length m and T of length n, find the longest strings which are a substrings of both S and T.

A generalisation is the k-common substring problem. Given the set of strings S = {S1,...,SK}, where | Si | = ni and Σni = N. Find for each 2 ≤ kK, the longest strings which occur as substrings of at least k strings.

[edit] Algorithms

You can find the lengths and starting positions of the longest common substrings of S and T in Θ(n + m) with the help of a generalised suffix tree. Finding them by dynamic programming costs Θ(nm). The solutions to the generalised problem take Θ(n1 + ... + nK) and Θ(n1・...・nK) time.

[edit] Suffix tree

Generalised suffix tree for the strings "ABAB", "BABA" and "ABBA", numbered 0, 1 and 2.
Generalised suffix tree for the strings "ABAB", "BABA" and "ABBA", numbered 0, 1 and 2.

You can find the longest common substrings of a set of strings by building a generalised suffix tree for the strings, and then finding the deepest internal nodes which has leaf nodes from all the strings in the subtree below it. In the figure on the right you see the suffix tree for the strings "ABAB", "BABA" and "ABBA", padded with unique string terminators, to become "ABAB$0", "BABA$1" and "ABBA$2". The nodes representing "A", "B", "AB" and "BA" all have descendant leaves from all of the strings, numbered 0, 1 and 2.

Building the suffix tree takes Θ(n) time (if the size of the alphabet is constant). If you traverse the tree bottom up, and maintain a bit vector telling which strings are seen below each node, you can solve the k-common substring problem in Θ(NK) time. If you prepare your suffix tree for constant time lowest common ancestor retrieval, you can solve it in Θ(N) time.[1]

[edit] Dynamic programming

You first find the longest common suffix for all pairs of prefixes of the strings. The longest common suffix is

\mathit{LCSuff}(S_{1..p}, T_{1..q}) =  \begin{cases}        \mathit{LCSuff}(S_{1..p-1}, T_{1..q-1}) + 1  & \mathrm{if } \; S[p] = T[q] \\        0                                            & \mathrm{otherwise} \end{cases}

For the example strings "ABAB" and "BABA":

A B A B
0 0 0 0 0
B 0 0 1 0 1
A 0 1 0 2 0
B 0 0 2 0 3
A 0 1 0 3 0


The maximal of these longest common suffixes of possible prefixes must be the longest common substrings of S and T. These are shown on diagonals, in red, in the table.

\mathit{LCSubstr}(S, T) = \max_{1 \leq i \leq m, 1 \leq j \leq n} \mathit{LCSuff}(S_{1..i}, T_{1..j}) \;

This can be extended to more than two strings by adding more dimensions to the table.

[edit] Pseudocode

The following pseudocode finds the set of longest common substrings between two strings with dynamic programming:

function LCSubstr(S[1..m], T[1..n])     L := array(0..m, 0..n)     z := 0     ret := {}     for i := 1..m         for j := 1..n             if S[i] = T[j]                 if i = 1 or j = 1                     L[i,j] := 1                 else                     L[i,j] := L[i-1,j-1] + 1                 if L[i,j] > z                     z := L[i,j]                     ret := {}                 if L[i,j] = z                     ret := ret ∪ {S[i-z+1..i]}     return ret 

This algorithm runs in O(mn) time. The variable z is used to hold the length of the longest common substring found so far. The set ret is used to hold the set of strings which are of length z

The following tricks can be used to reduce the memory usage of an implementation:

  • Keep only the last and current row of the DP table to save memory (O(min(m,n)) instead of O(mn))
  • Store only non-zero values in the rows. You can do this by using hash tables instead of arrays. This is useful for large alphabets.

[edit] References

  1. ^ Gusfield, Dan [1997] (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8. 

[edit] External links

10.20.2008


FEATURED TOPIC

Bank Runs

George G. Kaufman
A run on a bank occurs when a large number of depositors, fearing that their bank will be unable to repay their deposits in full and on time, simultaneously try to withdraw their funds immediately. This may create a problem because banks keep only a small fraction of deposits on hand in cash; they lend out the majority of deposits to borrowers or use the funds to purchase other interest-bearing assets such as government securities. When a run comes, a bank must quickly increase its cash to meet depositors' demands. It does so primarily by selling assets, often hastily and at fire-sale prices. As banks hold little capital and are highly leveraged, losses on these sales can drive a bank into insolvency. MORE
ALSO OF INTEREST

International Trade

by Arnold Kling [Nobel Prize winner Paul Krugman's contributions explained.]

Stock Market

by Jeremy J. Siegel

Savings and Loan Crisis

by Bert Ely

Federal Reserve System

by Richard H. Timberlake

Deposit Insurance

by George G. Kaufman
The Phillips curve represents the relationship between the rate of inflation and the unemployment rate. Although he had precursors, A. W. H. Phillips's study of wage inflation and unemployment in the United Kingdom from 1861 to 1957 is a milestone in the development of macroeconomics. Phillips found a consistent inverse relationship: when unemployment was high, wages increased slowly; when unemployment was low, wages rose rapidly.

Phillips conjectured that the lower the unemployment rate, the tighter the labor market and, therefore, the faster firms must raise wages to attract scarce labor. At higher rates of unemployment, the pressure abated. Phillips's "curve" represented the average relationship between unemployment and wage behavior over the business cycle. It showed the rate of wage inflation that would result if a particular level of unemployment persisted for some time.

Economists soon estimated Phillips curves for most developed economies. Most related general price inflation, rather than wage inflation, to unemployment. Of course, the prices a company charges are closely connected to the wages it pays. Figure 1 shows a typical Phillips curve fitted to data for the United States from 1961 to 1969. The close fit between the estimated curve and the data encouraged many economists, following the lead of Paul Samuelson and Robert Solow, to treat the Phillips curve as a sort of menu of policy options. For example, with an unemployment rate of 6 percent, the government might stimulate the economy to lower unemployment to 5 percent. Figure 1 indicates that the cost, in terms of higher inflation, would be a little more than half a percentage point. But if the government initially faced lower rates of unemployment, the costs would be considerably higher: a reduction in unemployment from 5 to 4 percent would imply more than twice as big an increase in the rate of inflation—about one and a quarter percentage points.

At the height of the Phillips curve's popularity as a guide to policy, Edmund Phelps and Milton Friedman independently challenged its theoretical underpinnings. They argued that well-informed, rational employers and workers would pay attention only to real wages—the inflation-adjusted purchasing power of money wages. In their view, real wages would adjust to make the supply of labor equal to the demandfor labor, and the unemployment rate would then stand at a level uniquely associated with that real wage—the "natural rate" of unemployment.


Figure 1 The Phillips Curve, 1961–1969

Source: Bureau of Labor Statistics.
Note: Inflation based on the Consumer Price Index.

Both Friedman and Phelps argued that the government could not permanently trade higher inflation for lower unemployment. Imagine that unemployment is at the natural rate. The real wage is constant: workers who expect a given rate of price inflation insist that their wages increase at the same rate to prevent the erosion of their purchasing power. Now, imagine that the government uses expansionarymonetary or fiscal policy in an attempt to lower unemployment below its natural rate. The resulting increase in demand encourages firms to raise their prices faster than workers had anticipated. With higher revenues, firms are willing to employ more workers at the old wage rates and even to raise those rates somewhat. For a short time, workers suffer from what economists call money illusion: they see that their money wages have risen and willingly supply more labor. Thus, the unemployment rate falls. They do not realize right away that their purchasing power has fallen because prices have risen more rapidly than they expected. But, over time, as workers come to anticipate higher rates of price inflation, they supply less labor and insist on increases in wages that keep up with inflation. The real wage is restored to its old level, and the unemployment rate returns to the natural rate. But the price inflation and wage inflation brought on by expansionary policies continue at the new, higher rates.

Friedman's and Phelps's analyses provide a distinction between the "short-run" and "long-run" Phillips curves. So long as the average rate of inflation remains fairly constant, as it did in the 1960s, inflation and unemployment will be inversely related. But if the average rate of inflation changes, as it will when policymakers persistently try to push unemployment below the natural rate, after a period of adjustment, unemployment will return to the natural rate. That is, once workers' expectations of price inflation have had time to adjust, the natural rate of unemployment is compatible with any rate of inflation. The long-run Phillips curve could be shown on Figure 1 as a vertical line above the natural rate. The original curve would then apply only to brief, transitional periods and would shift with any persistent change in the average rate of inflation. These long-run and short-run relations can be combined in a single "expectations-augmented" Phillips curve. The more quickly workers' expectations of price inflation adapt to changes in the actual rate of inflation, the more quickly unemployment will return to the natural rate, and the less successful the government will be in reducing unemployment through monetary and fiscal policies.

The 1970s provided striking confirmation of Friedman's and Phelps's fundamental point. Contrary to the original Phillips curve, when the average inflation rate rose from about 2.5 percent in the 1960s to about 7 percent in the 1970s, the unemployment rate not only did not fall, it actually rose from about 4 percent to above 6 percent.

Most economists now accept a central tenet of both Friedman's and Phelps's analyses: there is some rate of unemployment that, if maintained, would be compatible with a stable rate of inflation. Many, however, call this the "nonaccelerating inflation rate of unemployment" (NAIRU) because, unlike the term "natural rate," NAIRU does not suggest that an unemployment rate is socially optimal, unchanging, or impervious to policy.

A policymaker might wish to place a value on NAIRU. To obtain a simple estimate, Figure 2 plots changes in the rate of inflation (i.e., the acceleration of prices) against the unemployment rate from 1976 to 2002. The expectations-augmented Phillips curve is the straight line that best fits the points on the graph (the regression line). It summarizes the rough inverse relationship. According to the regression line, NAIRU (i.e., the rate of unemployment for which the change in the rate of inflation is zero) is about 6 percent. The slope of the Phillips curve indicates the speed of price adjustment. Imagine that the economy is at NAIRU with an inflation rate of 3 percent and that the government would like to reduce the inflation rate to zero. Figure 2 suggests that contractionary monetary and fiscal policies that drove the average rate of unemployment up to about 7 percent (i.e., one point above NAIRU) would be associated with a reduction in inflation of about one percentage point per year. Thus, if the government's policies caused the unemployment rate to stay at about 7 percent, the 3 percent inflation rate would, on average, be reduced one point each year—falling to zero in about three years.

Using similar, but more refined, methods, the Congressional Budget Office estimated (Figure 3) that NAIRU was about 5.3 percent in 1950, that it rose steadily until peaking in 1978 at about 6.3 percent, and that it then fell steadily to about 5.2 by the end of the century. Clearly, NAIRU is not constant. It varies with changes in so-called real factors affecting the supply of and demand for labor such as demographics, technology, union power, the structure oftaxation, and relative prices (e.g., oil prices). NAIRU should not vary with monetary and fiscal policies, which affect aggregate demand without altering these real factors.


Figure 2 The Expectations-Augmented Phillips Curve, 1976–2002

Source: Bureau of Labor Statistics.
Note: Inflation based on the Consumer Price Index.

The expectations-augmented Phillips curve is a fundamental element of almost every macroeconomic forecasting model now used by government and business. It is accepted by most otherwise diverse schools of macroeconomic thought. Early new classical theories assumed that prices adjusted freely and that expectations were formed rationally—that is, without systematic error. These assumptions imply that the Phillips curve in Figure 2 should be very steep and that deviations from NAIRU should be short-lived (see new classical macroeconomics and rational expectations). While sticking to the rational-expectations hypothesis, even new classical economists now concede that wages and prices are somewhat sticky. Wage and price inertia, resulting in real wages and other relative prices away from their market-clearing levels, explain the large fluctuations in unemployment around NAIRU and slow speed of convergence back to NAIRU.


Figure 3 Nonaccelerating Inflation Rate of Unemployment

Source: Congressional Budget Office.

Some "new Keynesian" and some free-market economists hold that, at best, there is only a weak tendency for an economy to return to NAIRU. They argue that there is no natural rate of unemployment to which the actual rate tends to return. Instead, when actual unemployment rises and remains high for some time, NAIRU also rises. The dependence of NAIRU on actual unemployment is known as the hysteresis hypothesis. One explanation for hysteresis in a heavily unionized economy is that unions directly represent the interests only of those who are currently employed. Unionization, by keeping wages high, undermines the ability of those outside the union to compete for employment. After prolonged layoffs, employed union workers may seek the benefits of higher wages for themselves rather than moderating their wage demands to promote the rehiring of unemployed workers. According to the hysteresis hypothesis, once unemployment becomes high—as it did in Europe in the recessions of the 1970s—it is relatively impervious to monetary and fiscal stimuli, even in the short run. The unemployment rate in France in 1968 was 1.8 percent, and in West Germany, 1.5 percent. In contrast, since 1983, both French and West German unemployment rates have fluctuated between 7 and 11 percent. In 2003, the French rate stood at 8.8 percent and the German rate at 8.4 percent. The hysteresis hypothesis appears to be more relevant to Europe, where unionization is higher and where labor laws create numerous barriers to hiring and firing, than it is to the United States, with its considerably more flexible labor markets. The unemployment rate in the United States was 3.4 percent in 1968. U.S. unemployment peaked in the early 1980s at 10.8 percent and fell back substantially, so that by 2000 it again stood below 4 percent.

Modern macroeconomic models often employ another version of the Phillips curve in which the output gap replaces the unemployment rate as the measure of aggregate demand relative to aggregate supply. The output gap is the difference between the actual level of GDP and the potential (or sustainable) level of aggregate output expressed as a percentage of potential. This formulation explains why, at the end of the 1990s boom when unemployment rates were well below estimates of NAIRU, prices did not accelerate. The reasoning is as follows. Potential output depends not only on labor inputs, but also on plant and equipment and other capital inputs. At the end of the boom, after nearly a decade of rapid investment, firms found themselves with too much capital. The excess capacity raised potential output, widening the output gap and reducing the pressure on prices.

Many articles in the conservative business press criticize the Phillips curve because they believe it both implies that growth causes inflation and repudiates the theory that excess growth of money is inflation's true cause. But it does no such thing. One can believe in the Phillips curve and still understand that increased growth, all other things equal, will reduce inflation. The misplaced criticism of the Phillips curve is ironic since Milton Friedman, one of the coinventors of its expectations-augmented version, is also the foremost defender of the view that "inflation is always, and everywhere, a monetary phenomenon."

The Phillips curve was hailed in the 1960s as providing an account of the inflation process hitherto missing from the conventional macroeconomic model. After four decades, the Phillips curve, as transformed by the natural-rate hypothesis into its expectations-augmented version, remains the key to relating unemployment (of capital as well as labor) to inflation in mainstream macroeconomic analysis.

W hen economists refer to the "opportunity cost" of a resource, they mean the value of the next-highest-valued alternative use of that resource. If, for example, you spend time and money going to a movie, you cannot spend that time at home reading a book, and you cannot spend the money on something else. If your next-best alternative to seeing the movie is reading the book, then the opportunity cost of seeing the movie is the money spent plus the pleasure you forgo by not reading the book.

The word "opportunity" in "opportunity cost" is actually redundant. The cost of using something is already the value of the highest-valued alternative use. But as contract lawyers and airplane pilots know, redundancy can be a virtue. In this case, its virtue is to remind us that the cost of using a resource arises from the value of what it could be used for instead.

This simple concept has powerful implications. It implies, for example, that even when governments subsidize collegeeducation, most students still pay more than half of the cost. Take a student who annually pays $4,000 in tuition at a state college. Assume that the government subsidy to the college amounts to $8,000 per student. It looks as if the cost is $12,000 and the student pays less than half. But looks can be deceiving. The true cost is $12,000 plus the income the student forgoes by attending school rather than working. If the student could have earned $20,000 per year, then the true cost of the year's schooling is $12,000 plus $20,000, for a total of $32,000. Of this $32,000 total, the student pays $24,000 ($4,000 in tuition plus $20,000 in forgone earnings). In other words, even with a hefty state subsidy, the student pays 75 percent of the whole cost. This explains why college students at state universities, even though they may grouse when the state government raises tuitions by, say, 10 percent, do not desert college in droves. A 10 percent increase in a $4,000 tuition is only $400, which is less than a 2 percent increase in the student's overall cost (see human capital).

What about the cost of room and board while attending school? This is not a true cost of attending school at all because whether or not the student attends school, the student still has expenses for room and board.