To Mock a Mockingbird（5）

To Mock a MockingbirdのChapter 5、6を読んだ。面白かった問題を1つ載せておきます。

（問題）
ある日私は社会学者に会いました。彼は私に次のような研究成果を教えてくれました。

「私はこの島のすべての原住民たちにインタビューをした。
その結果私はおもしろい事実を発見した。
すべての原住民Xに対して、『XとYは、どちらもならず者だ』と主張する原住民Yが少なくとも１人は存在する。」

彼の研究報告は論理的に考えて正しいでしょうか？

（前提）
すべての原住民は、騎士とならず者のいずれかです。
騎士は本当のことしか言いません。ならず者は嘘しか言いません。

To Mock a Mockingbird（4）

「To Mock a Mockingbird」 chapter 4を読んだ。9問中8問自力で正答できた。

chapter 3と比べると簡単だった。 chapter 3が難しすぎた？

"Do you believe that two plus two equals four?"

の問いに、

• accurate truth-teller
• inaccurate truth-teller
• accurate liar
• inaccurate liar

がそれぞれ何と答えるか？という問題がおもしろかった。inaccurateなタイプの人間は、自分が何を信じているかについてもinaccurateなので、ひとひねり必要。

To Mock a Mockingbird（3）

　Chapter 3読んだ。一気にレベルがあがった感じがする。自力で解けたのは半分くらいな気がする。

ちなみに問題2のWhat  About This Oneは解答が間違ってるので注意。
下のサイトに詳しい解説がある。

http://math.stackexchange.com/questions/189537/to-mock-a-mockingbird-two-barbers-logic-puzzle

To Mock a Mockingbird（2）

　Chapter 2復習しました。

嘘つきと正直者の問題でよくある「あなたは主張Pが正しいと言っちゃうかんじの人ですか？」という例のあれは『the Nelson Goodman Principle』という名前がついてるそうです。

　Chapter 2の問題は、いわゆる嘘つきと正直者の問題が中心ですが「Yes/Noで答えられる問題、かつ、3語以内」という制約が付くので、単純にthe Nelson Goodman Principleを適用して終わり。とはなりません。そこがこの本のおもしろいところ。

特に奥さんの名前を忘れたおっちょこちょいの論理学者の問題がおもしろかった（問題の設定、問題自体ともに）。

　

To Mock a Mockingbird（1）

気分転換に『To Mock a Mockingbird』のchapter 1を読み直しました。
やっぱり面白いですね。


　
　本の中で紹介されていた「Sancho Panza paradox」について少し調べてみました。
Sancho Panzaっていうのは、人の名前らしいです。スペイン人の小説家が書いた「Don Quixote」という物語の中の登場人物です。

Sancho Panzaが橋を渡ろうとしたとき、役人が彼を止めます。そしてこう言います。
「もし本当のことを言えばこの橋を通してやろう。嘘を言えばお前は絞首刑だ。」

まあ普通の人なら「1 + 1 = 2です。」とか言って橋を通るのですが、Sancho Panzaはこう言いました。
「僕は絞首刑になるだろうね。」

Sancho Panzaかっこよすぎるぜ！

「プロになるためのWeb技術入門」 ――なぜ、あなたはWebシステムを開発できないのか

　『「プロになるためのWeb技術入門」 ――なぜ、あなたはWebシステムを開発できないのか』を読みました。昨年新入社員研修の講師をしていたときに、マネジャーの方が新人たちに勧めていたのでどんなものかなと思って読んでみました。

　インターネットの歴史、インターネットの発展とともにどのような要求が生まれたか、その要求を満たすためにどのような技術が作られたかということがわかりやすく書かれていました。

　だいたい知ってることが多かったですが、よくまとめられていて、これまで学んだことを効率的に復習することができました。

　扱っているトピックは、

• クライアントとサーバー
• URLとURI
• GETとPOST
• CGIとサーブレット
• HTTPプロトコルについて
• Cookieとセッション
• 三層構成（Webサーバー、アプリケーションサーバー、DBサーバー）
• MVCモデルを実現するフレームワーク（Struts 1を例に）
• O/Rマッピング（iBATISを例に）
• セキュリティ（SQLインジェクション、XSS、セッションハイジャック、CSRFなど）

と多岐に渡り、最低限知っておくべきことはほぼ網羅されているのかなと思います。

そしてこの本の一番いいところは、「今の業界ではこうするのが常識だ！」、「この技術を使いなさい！」と押し付けるのではなく、

• なぜその技術を使用する必要があるのか？
• その技術が生まれる前はどのような問題があったのか？
• その技術のおかげでどのようなメリットがえられるのか？

をきちんと説明してくれるところです。この価格で、扱ってるテーマも広いのに、ここまで丁寧に説明してくれる本はなかなかないのではと思います。エンジニア一年生に勧めるべき最高の本です。

デザインパターン（12） Decorator

ようやく半分まで来ました！Decoratorパターンです。
このパターンはすごいです。今まで見てきたパターンの中で一番すごいと思います。

まとめ

• 基本的な機能を提供するオブジェクトと装飾的な機能を提供するオブジェクトを同一視するためのパターン。
• 動的に機能を追加できる。
• 任意の組み合わせで機能を追加できる。
• Decoratorは透過的インターフェースを使用。

疑問点

結城さんの本では、java.ioパッケージのライブラリでDecoratorパターンが使われていることが紹介されています。他にはどういう場面で使われるのか調べてみました[1]。

よく使われるのはwindowシステムのwindow。単純なwindowにスクロールバーをつけたり、枠線をつけたりといった場合にDecoratorを使うと便利。これをクラス階層でやろうとすると、装飾機能のべき乗個のクラスが必要になる(Window, ScrollingWindow, WindowWithBorder, ScrollingWindowWithBorder, ....)ので、Decorator必須です。

あとは、アクセス制御にも使えるようです。「この条件の場合は、このメソッドは呼び出せない。あの条件の場合は、あのメソッドは呼び出せない。」というような要件が必要な場合、もともとのオブジェクトでアクセス制御をごちゃごちゃと書くのではなく、オブジェクトを制御用のDecoratorで包むようにしてあげると綺麗な設計になります。

ソースコード

「実行時にキーボード入力された値に従って動的に機能を追加する。」という例を実装してみました。

import java.util.Scanner;

interface Cake {
    public void display();
}

class PlainCake implements Cake {
    @Override
    public void display() {
        System.out.println("普通のケーキ");
    }
}

abstract class Decorator implements Cake {
    protected Cake cake;
    
    public Decorator(Cake cake) {
        this.cake = cake;
    }
}

class ChocolateDecorator extends Decorator {
    public ChocolateDecorator(Cake cake) {
        super(cake);
    }

    @Override
    public void display() {
        System.out.println("チョコレートつき");
        cake.display();
    }
}

class StrawberryDecorator extends Decorator {
    public StrawberryDecorator(Cake cake) {
        super(cake);
    }

    @Override
    public void display() {
        System.out.println("苺つき");
        cake.display();    
    }    
}

class CreamDecorator extends Decorator {
    public CreamDecorator(Cake cake) {
        super(cake);
    }

    @Override
    public void display() {
        System.out.println("クリームつき");
        cake.display();            
    }
}

public class Main {
    public static void main(String[] args) {    
        Cake cake = new PlainCake();
        Scanner in = new Scanner(System.in);
        
        System.out.println("チョコレートいる？ (Y/N)");
        if ("Y".equals(in.next()))
            cake = new ChocolateDecorator(cake);
        
        System.out.println("苺いる？ (Y/N)");
        if ("Y".equals(in.next()))
            cake = new StrawberryDecorator(cake);

        System.out.println("クリームいる？ (Y/N)");        
        if ("Y".equals(in.next()))
            cake = new CreamDecorator(cake);
        
        in.close();

        System.out.println("ケーキ完成！");
        cake.display();
    }
}

参考URL

[1] http://en.wikipedia.org/wiki/Decorator_pattern

デザインパターン（11） Composite

結城さんの本でCompositeパターンを勉強しました。

まとめ

• 単体のオブジェクトとその集合を同一視するためのパターン。
• 木構造のような再帰的なデータ構造に適用できる。

疑問点

いわゆる葉になるようなデータと、そうでないデータを統一的に扱えるようにするというのが利点だというのは分かったけど、わざわざ共通のインターフェースを用意する必要があるのか。葉かそうじゃないかの判定は子を管理しているコンテナがnullか否かでできそうだし、それやればクラス一つでいいからクライアントからは統一的に扱えるような・・・。
Wikipediaを見てみよう[1]。。

When dealing with Tree-structured data, programmers often have to discriminate between a leaf-node and a branch.

そうそう。Compositeパターン使わなくても葉かどうかは見分けられる。

This makes code more complex, and therefore, error prone. The solution is an interface that allows treating complex and primitive objects uniformly. In object-oriented programming, a composite is an object designed as a composition of one-or-more similar objects, all exhibiting similar functionality. This is known as a "has-a" relationship between objects.The key concept is that you can manipulate a single instance of the object just as you would manipulate a group of them.

うーむ、確かに。もし葉の場合はごにょごにょごにょ、そうでない場合はごにょごにょごにょみたいなコードを書くよりは、Composite使った方が綺麗にまとまるし、バグも減るってことか。

参考URL

[1] http://en.wikipedia.org/wiki/Composite_pattern

デザインパターン（10） Strategy

--上海の夜--

Strategyパターンを勉強しました。継承ではなく、委譲を用いることでクラス間の結びつきを弱くするのがポイント。

まとめ

• 使用するアルゴリズムの切り替えを簡単にするためのパターン。
• 実行中にアルゴリズムを切り替えることも可能。

疑問点

多態性を使えば、委譲じゃなく継承でもいけるけど、どうなんだろう。使いどころを調べてみると、

For instance, a class that performs validation on incoming data may use a strategy pattern to select a validation algorithm based on the type of data, the source of the data, user choice, and/or other discriminating factors. These factors are not known for each case until run-time, and may require radically different validation to be performed. The validation strategies, encapsulated separately from the validating object, may be used by other validating objects in different areas of the system (or even different systems) without code duplication.[1]

とあった。んー、うまく理解できてなかったところが分かった気がする。Strategyのユーザは、いろいろなStrategyを自由に選ぶようにしたい。プラス、個々のアルゴリズムは他にもいろいろなところで使われることがある。ってことか。

Formally speaking, the strategy pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. Strategy lets the algorithm vary independently from clients that use it.[1]

ってあるから、クライアントの部品性とアルゴリズムの部品性を高めるために、それぞれえを独立したものにしたいってことか。確かにこれなら委譲じゃないとダメか。

参考URL

[1]http://en.wikipedia.org/wiki/Strategy_pattern

デザインパターン（9） Bridge

結城さんの本でデザパタの勉強しました。Bridgeパターンは、今まで出てきた中で一番好きなパターンです。（ちょっと大袈裟ですが）感動すらしました。

クラスを継承する場合は、それが機能追加のための継承なのか？それとも新しい実装をするための継承なのか？を意識しなければならない。ということを学びました。

まとめ

• 機能のクラス階層と実装のクラス階層を分ける。
• 委譲により、機能のクラス階層と実装のクラス階層を結びつける。（クラス図を書くと、この委譲の部分がbridgeに見える。）
• 機能を機能のクラス階層に追加した場合は、すべての実装クラスで使用可能となる。
• クライアントは、機能のクラスのAPIを使ってクラスを利用する。

疑問点

特になし。とても分かりやすかった。

デザインパターン（8） Abstract Factory

まとめ

• オブジェクト生成のためのデザインパターン。
• クライアントはabstract factoryを通してオブジェクトの生成を行う。
• クライアントは生成されたオブジェクトの具体的な実装は知らない。
• abstract factoryを継承したconcrete factoryをシステム変数やプロパティファイル、実行引数などで指定することにより、使用される具体的な工場を変えることができる。
• 具体的な工場の種類によって生成されるオブジェクト（concrete object）の具体的な実装は異なる。
• 新しい種類のconcrete factory / concrete objectをクライアントへの影響なく追加できる。

疑問点

Factory Method Patternとの違いがよく分かっていないような気がする。

参考[2]によると、「Factory methodは単なるメソッド。Factory methodを実装しているクラスの本来の役割はオブジェクトの生成ではない。これに対して、Abstract Factoryはオブジェクト生成のためのクラス。異なる工場では異なる製品が作成される。」とある。

Factory MethodってAbstract Factoryと同じようなことをするイメージを持っていたけど、もっと単純なものという認識でいいのだろうか。。単純にそのクラスで使いたいオブジェクトを生成するときにnewせずにcreateInstanceみたいなメソッドを使うぞ！と決めたらそれがFactory Methodになるんだろうか・・。

 お、いい説明を見つけた。Factory methodのエッセンスは、
「Define an interface for creating an object, but let the classes that implement the interface decide which class to instantiate. The Factory method lets a class defer instantiation to subclasses.」 (参考[3])

ふむふむ。なんか分かってきた。逆にAbstract Factoryのエッセンスは、
「Provide an interface for creating families of related or dependent objects without specifying their concrete classes.」 （参考[1]）

やべっ。超分かりやすい。なんか分かったような気がする。

Factory methodの場合は、使いたいオブジェクトを生成するためのメソッドがスーパークラスで定義されているので、それを実装して具体的にどのクラスを使うか決めてください。オブジェクトを作りたいときは、newじゃなくてそのメソッド（Factory method）を使ってください。

Abstract Factoryの場合は、オブジェクトの使用者クラスは、newしてそのオブジェクトを生成するのではなく、コンストラクタで受け取った（またはグローバルにアクセスできる部分に存在する）factoryさんにオブジェクトの生成を委譲してください。ただしfactoryさんの具体的な実装については使用者は知る必要はありません。実行環境ごとにfactoryさんの具体的な実装は異なっており、生成されるオブジェクトの具体的な実装も異なりますが、使用者はこれを意識する必要はありません。

と、こういうことかな。間違っていたらご指摘いただけると嬉しいです。

参考URL

[1] http://en.wikipedia.org/wiki/Abstract_factory_pattern
[2] http://stackoverflow.com/questions/5739611/differences-between-abstract-factory-pattern-and-factory-method
[3] http://en.wikipedia.org/wiki/Factory_method_pattern

デザインパターン（7） Builder

まえおき

以下の書籍でBuilderパターンについて勉強した。

まとめ

• 構造を持ったインスタンスを組み上げるときに利用する。
• Builder、ConcreteBuilder、Director、Clientによって構成される。

疑問点

• Builderパターンはオブジェクト生成のためのデザインパターン。Factory Methodパターンと何が違うのか？

Factory Methodパターンは異なる種類のオブジェクトを生成するときのパターンで、Builderパターンはオブジェクトの生成手順をきれいにまとめるためのパターンなので、目的がまったく違う。以下のような記述が参考サイト[1]にあった。

The rule of thumb I noticed after some time was the following: Consider a restaurant. The creation of "Todays Meal" is a factory pattern, because you tell the kitchen "get me todays meal" and the kitchen/factory decides what object to generate. based on hidden critereas.

The builder appears if you ordered a custom pizza. In this case, the waiter tells the chef/builder "I need a pizza, add cheese, cheese, onions and bacon to it!". Thus, the builder exposes what attributes the generated object should have, but hides how to set them.

• パッと見、Template Methodパターンと同じに見えるんだけど、何が違うのか？

これは明確な違いが自分ではよく分からなかった。Builderパターンの方が抽象度や独立性が高いような気がする。Template Methodパターンだと親-子クラスという関係があるし、同じ部品を別の処理フローでテンプレート化したいときに処理フローの数だけ親-子のペアを毎回書かないといけないような気がする。それに比べて、Builderパターンの方はdirector-builder間の関係が移譲なのでそれぞれの独立性が高いのかなと思う。参考サイト[2]になんとなくしっくりくるような説明があった。

Template method is really just a way to define some methods that each subclass must define.

The builder pattern is used to construct a more complex object.

Lets say that we want to construct different Saab (car brand) models. Each model has different engines,lights etc.

If we were to use the template method pattern we had to create one class for each single combination of cars or use some nasty inheritance hierarchies. A lot of those methods would also contain duplicate code.

With the build pattern we can instead take different parts and compose those together to a complete car. Hence we can reuse a engine for every model if needed and we can also customize each part of the car.

その他

• 書籍の練習問題がおもしろかった。久しぶりにswingでGUIを書いた。今度簡単なゲームか何か書いてみようかな。

参考サイト

1. When would you use the Builder Pattern? [closed]
2. Differences between builder pattern vs template method

デザインパターン（6） Prototype

まえおき

Prototypeパターンの勉強をしました。書籍だけで大まかなイメージは掴めましたが、「複雑な過程を経てインスタンス生成されるものを簡単に作れる」という例があると、より分かりやすいと思います。

まとめ

• プロトタイプと呼ばれるオブジェクトをコピーすることで、複雑な過程を経てインスタンス化されるオブジェクトの生成を簡単にすることができる。
• コピーされたオブジェクトは、プロトタイプとは独立しているので、必要に応じてフィールドの内容を変更することができる。（参考サイト[2,3]）

疑問点

• 書籍には「複雑な過程を経てインスタンス生成されるものを簡単に作れる」という例が無くて具体的なイメージが湧かなかった。参考サイト[1]を見て複雑な過程（もしくは時間のかかる処理）を経て作られるインスタンスのイメージが掴めた。

その他

• cloneメソッドとCloneableインターフェースに関して学んだ。cloneメソッドはshallow copyなので対象オブジェクトに参照型のフィールドが存在する場合は本当にshallow copyでよいのか注意する。

参考サイト

1. TECHSCORE
2. THE CODE PROJECT
3. javapapers

デザインパターン（5） Singleton

まえおき

Singletonです。説明が分かりやすく、かつ、例題もどのような場面で使うのかをしっかり抑えている内容だったため簡単に理解できました。

まとめ

• そのクラスのインスタンスがシステム上で１個しか存在しないことを保証する。
• コンピュータそのものを表現したクラス、システム設定を表現したクラス、ウインドウシステムを表現したクラスなどが使用対象となる。

疑問点

• 特になし

その他

• コンストラクタをprivateにするというのは大事なポイント。意図を理解していない開発者に対象オブジェクトを普通にnewされると困ったことになってしまうので。
• static フィールドが初期化されるタイミングも重要。
• マルチスレッドに関する問題がおもしろかった。synchronizedについて勉強しなおした。

デザインパターン（4） Factory Method

まえおき

今日はFactory Methodパターンについて。去年読んだときは理解できなくて、いろいろなサイトを見て回った。今日改めて読んでみてもメリットがよくわからなかった。この本で強調されているポイントがちょっと違うのではないかという疑問を持った。分かりやすいサイトを見つけたのでそこを読んで理解度を補強した。

まとめ

• インスタンスの生成のための枠組みと実際の生成を切り離すためのパターン
• FactoryクラスでTemplate Methodパターンが使われている
• 使用者クラスから生成するクラスの依存性を排除する

疑問点

• メリットが「CreatorクラスがConcreteProductに依存しないこと」と書かれているけど、「ConcreteProductの使用者クラスがConcreteProductに依存しないこと」の方がうれしい部分だと思うけど。。
• 使用するクラスを直接newするのは悪だと言うのは知っていて、それをしないために単純なインスタンス生成メソッドを使うことと、Factory Methodを使うことの違いがよく分からなかった。参考サイトを見て解決した。

その他

• Factory Methodパターンでインスタンス生成して欲しいことを明示するために、コンストラクタをpublicにしないというテクニックはおもしろいと思った。

参考サイト

• 事例で学ぶデザインパターン 第４回 Factory Method パターン

Factory Methodパターンを使わないと、以下の3つのデメリットがあることを示し、

1. クライアントクラスと具象クラスの結合度が高い
2. 同等の生成処理の実装が各クライアントクラスに散在している
3. 生成処理の中に変動しやすい if 文が存在している

単純なファクトリクラスを利用することで、1.2.を解決できることを示し、さらに3.を解決するためにファクトリクラスを抽象化し、Factory Methodパターンへと導くという説明が素晴らしかった。

デザインパターン（3） Template Method

まえおき

今日はTemplate Methodパターンについて。フレームワークと関連の深いパターン。

まとめ

• 大まかな処理の流れをテンプレート可する。
• 処理の大きな流れをスーパークラス側で定義し、各処理の詳細な処理はサブクラス側で定義する。

疑問点

• メリットの説明が分かりづらかった。自分なりに考えてみたがメリットは大きく２つあると思う。処理の大まかな流れをテンプレート可することで、ソースコード量が減り、機能変更（各詳細処理を呼び出す順番や呼び出す処理の追加）にも強くなるというのが一つ。もう一つは決まった処理を決まった場所に書かせることで保守性が上がるということ。

その他

• これは完全にフレームワーク内部で使われているパターンだなと思った。処理の流れはフレームワーク側で定義するから、利用者は○○にこういう処理を、△△にはああいう処理を書いてくれ。という感じ。

• 「Liskov substitution principle」、「Hollywood principle」といった関連キーワードを学習した。こういう横文字のテクニカルタームをさらっと言えると、何となく出来るヤツに見えるので積極的に覚えていきたい。

デザインパターン（2） Adaptor

まえおき

今日はAdaptorパターンについて。Wrapperパターンとも呼ばれるらしい。このパターンはごくごくあたり前のことを言っているだけのような気がするんだけど。保守のプログラミングをやる場合は無意識のうちに使っていることが多いと思う。

まとめ

• 既存機能と必要機能の「ずれ」を埋める。
• 実績のあるクラスを効率的に利用することでテスト工数を減らすことができる。

疑問点

• 継承を利用した方法と、移譲を利用した方法の使い分けがよく分からない。この本ではAdapteeが一つのクラスの場合しか説明されていないが、Adapteeが複数個あった場合は移譲を利用した方法しか使えない。Adapteeが一つのクラスなら継承、複数個のクラスなら移譲という使い分けでいいのだろうか？

その他

• 「無意識のうちに使っている」と冒頭で書いたけど、よく考えるとAdapteeをAdapterでラッピングしてClientが使うという実装しかしたことがない。これでもテスト工数を減らすという目的は果たせるけれど、設計上よろしくない。Clientが知るべきは使いたい機能だけなのでそれをTargetとして明示的に示してあげる必要がある。そうすることで開発者の意図が伝わりやすいソースコードができる。というか、ここまでやって初めてAdaptorパターンと呼べるのかな・・。

関連情報

• Adapterパターンを使い利用コンポーネントを切り替える　インターフェースの差異を吸収することで、ソースの改修を少なくすることができるということをうまく説明しています。また、クラスの生成をメソッド化するとさらに改修量が減るという説明もとても分かりやすいです。

デザインパターン（１） Iterator

まえおき

社内のプログラミング講師になったから、デザインパターンくらいは知っとかないとまずい。ということでもう一度復習することにした。去年の夏読んでいた『Java言語で学ぶデザインパターン入門』という本を最初から読み直していこうと思う。まずは、Iteratorパターンから。

まとめ

• 集合体の要素を一つ一つ指し示し、全体をスキャンするときに使う。
• 集合体のスキャン機能を集合体の実装から独立させることができる。

疑問点

• Aggregate インターフェースにIteratorインターフェースで定義されている抽象メソッドを定義すれば同じような保守性（使用者側で変更が発生しない）は担保できるのでは？と思ったが、一つの集合体を異なる方法で数え上げたいときは別にIteratorとしてスキャン役を持っておいた方が便利か。Mapのスキャンとかだと、keyをスキャンしたい場合も、valueをスキャンしたい場合があるしね。コンポーネントの独立性という意味でAggregateとIteratorを別々に用意することには大きな利便性があると思う。と中盤くらいで考えていたら、最後の方の節の「複数のイテレータ」で似たような話が言及されていた。

その他

この本で強調されている「具体的なクラスを定義する前に、インターフェースを定義する。」というのはすごく大切だと思う。機能と実装を切り離すことで、クラスの使用者がクラスの実装を意識せずに済むというのは非常に大事。

Introduction to Algorithms chap.2

"off in the whiteness" by angela7dreams

Chapter.2 is entitled "Getting Started."

2.1 Insertion sort

I originally had a few knowledge about sort algorithms, like bubble sort, quick sort, merge sort. But this is the first time for me to learn (or write it by myself) insertion sort. Its worst-case running time is n², but its best-case running time is n. So it's faster than other O(n²) algorithms in a particular situation, and also faster than quick sort and merge sort for sufficiently small input data. Don't know insertion sort? It's the same procedure when you sort a hand of cards.

Another important concept in this section is loop invariants, which is used to assert the termination and the correctness of algorithms. There are three types of invariants for you to consider when you evaluate an algorithm:

1. Initialization
2. Maintenance
3. Termination

2.2 Analyzing algorithms

Analyzing algorithms means analyzing the resources required and its computational time. In the book, random-access machine(RAM) is used for analysis of algorithms, where arithmetic, data movement and control take a constant amount of time. As an example, running time of insertion sort is measured, and you analyze the worse-case and the average-case running time of it.

2.3 Designing algorithms

Insertion sort is based on incremental approach. In this section, another approach called divide-and-conquer is introduced. As an example, merge sort is explained. I just implemented merge sort for a Facebook Hacker Cup problem, but the implementation in the book is better than mine. In the function MERGE() sentinels are used, and this yields a concise procedure. (Sentinel is not so much an algorithm-related thing as an implementation skill, though. I just wrote it since I was just moved by its good point.) As in "insertion sort" part, some analysis is done for merge sort.

Exercises and Problems

I'll just introduce an interesting problem.

Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. Give a Θ(n lg n) algorithm to determine the number of inversions in A[]. (Hint: Modify merge sort.)

Introduction to Algorithms chap.1

I started reading a famous book entitled "Introduction to Algorithms," which is known as a textbook used in MIT. If I read one chapter a week, I would be able to finished the book in a year. Still It would take quite a long time though. Anyway I think I'm going to write memos when I'm done with a chapter.

This is about the first chapter "The Role of Algorithms in Computing." This chapter explains what the use of learning algorithms. I found an interesting question in this chapter.

"Suppose computers were infinitely fast and computer memory was free. Would you have any reason to study algorithms?"

The answer is, of course, yes! (Truth be told, I was not able to find a witty answer by myself..)

You still want to know:

1. Your algorithm terminates?

2. If so, with a correct answer?

It also mentions quite a few areas in which algorithms really help.

• hardware design
• graphical user interface
• networking
• computer language (compiler, interpreter, or assembler)

Some people say, "In this age when the computer has developed this far in a sense of hardware, what the use of learning fast algorithm?" But as the book says, "With the ever-increasing capacities of computers, we use them to solve larger problems than ever before."

I would conclude that this first chapter is really encouraging for those who want to start learning algorithms. You should try it out.