カテゴリー別アーカイブ: 雑記

日々の雑記

静的サイトアセンブラ Middlemanを試してみよう (2)

今回はMiddlemanのテンプレートについてみていきます。

Middlemanでは多くのテンプレート言語を利用でき、HTML製作を簡単にします。
ERb、Haml、Saas、Scss、CoffeeScriptなど、多くのテンプレートエンジンをサポートしています。

＃テンプレートの基礎

標準のテンプレート言語はERbです。ERbは、変数を追加したり、メソッドを呼んだり、ループを使用したり、if文を使用したりする点を除けば、HTMLに似ています。

Middlemanの全てのテンプレートファイルはファイル名にそのテンプレート言語の拡張子がついています。

ERbで書かれたシンプルなインデックスページは、index.htmlというファイル名と拡張子であるerbを足して、index.html.erbという名前になっています。

このファイルは

<h1>Welcome</h1>

1	<h1>Welcome</h1>

のような標準のHTMLを含んでいます。

例えば、Rubyの変数やメソッド、ループなどを使用して

<h1>Welcome</h1>
<ul>
  <% 5.times do |num| %>
    <li>Count <%= num %>
  <% end %>
</ul>

<h1>Welcome</h1>

<ul>

<% 5.times do |num| %>

<li>Count <%= num %>

<% end %>

</ul>

のように記述することができます。

＃レイアウト

レイアウトを使用すると、すべてのテンプレートで共通のHTMLの部分をひとつで管理できます。

Middlemanでは、レイアウトはヘッダとフッタの両方を含み、個別のページコンテンツをラップします。

最も基本的なレイアウトは、いくつかの個別のページコンテンツをもつ場合です。

yieldを使うとテンプレートでどこに個別のページコンテンツを読み込むのかを指定できます。

レイアウトをERbを使って作成すると、以下のように書くことができます。

<html>
<head>
  <title>My Site</title>
</head>
<body>
  <%= yield %>　<!--ここで個別のコンテンツが読み込まれます -->
</body>
</html>

<html>

<head>

</head>

<body>

<%= yield %>

</body>

</html>

個別のページのテンプレートはERbで書くことができました。
レイアウトに書かれている共通部分は不要になるので、例えば以下のようにコンテンツの部分だけを書けばよくなります。個別のページのテンプレートは、例えば

<h1>Hello World</h1>

1	<h1>Hello World</h1>

となります。

この場合、最終的な出力として得られるHTMLは、

<html>
<head>
  <title>My Site</title>
</head>
<body>
  <h1>Hello World</h1>    <!-- yieldの部分で個別のページテンプレートが読み込まれます -->
</body>
</html>

<html>

<head>

</head>

<body>

<h1>Hello World</h1>

</body>

</html>

という形になります。

source/layouts/admin.erb
source/login.html.erb

[メモ] OpenGL Mac OS X コマンドラインコンパイルコマンド

gcc file_name -framework OpenGL -framework GLUT -framework Foundation

[BCI] EEG-based “Serious” Games Design for Medical Applications

Wang et al.

EEGを利用したNeurofeedbackゲームとbrain-computer interfacesに関する論文。
エンターテインメント、e-learningや医療で使用され始めている。
Neurofeedbackを利用したゲームの設計とアルゴリズムとその実装について。

Neurofeedbackとは

ユーザーの頭蓋からEEGを取得し、ディスプレイへの音(など)によって、ユーザーへのリアルタイムフィードバックを表示する技術。

Attention Deficit Hyperactivity Disorder (ADHD)、Autistic Spectrum Disorders (ASD)やアルコールやドラッグなどを含むSubstance Use Disorder (SUD)のような精神疾患では、EEGやERP(Event Related Potential)に健常者とは異なる特徴がみられる。

他の身体部位と同様に、自身のEEGもセルフコントロールできる可能性がある。
通常治療の他に、Neurofeedbackがこれらの疾患に対する治療となる。

多くのNeurofeedbackゲームがADHDの治癒に効果的であることが分かっている。
ADHD患者は
- EEGの大きな歪み
- θ/β波の比に異常
- SCP(Slow Cortical Potential)
という特徴があることが知られている。

Gevensleben et al.(2009)ではfrequency neurofeedback trainingとSCP neurofeedback trainingでADHD患者に対して良い治癒効果が認められたと述べている。

ASDは、興味の限定や同じ行動の繰り返しに加えて、社会的な交流やコミュニケーション異常と関連した精神疾患。
先のGevenslebenらの研究では、ASDの8歳の少女を対象にして、目を開けた状態でresting conditionの時のEEGを解析。
αバンドとθバンドの信号異常。
これに対して、neurofeedbackのスキーマを考案。

[SQLite] Command Line Shell For SQLite

SQLiteライブラリは、シンプルなコマンドラインユーティリティであるsqlite3を含んでいます。これにより、ユーザはSQLiteデータベースに対して、手動でSQLを入力、実行することができます。

ことはじめ

SQLiteデータベースを保持しているファイルの名前を引数にして、sqlite3プログラムを起動する。

$ sqlite3 ex1　// SQLiteデータベース ex1 を作成し、ユーティリティ起動
SQLite version 3.6.11  // バージョン情報
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> create table tbl1(one varchar(10), two smallint);  // テーブルtbl1作成
sqlite> insert into tbl1 values('hello!',10);
sqlite> insert into tbl1 values('goodbye', 20);
sqlite> select * from tbl1;  // tbl1から全タプル表示
hello!|10
goodbye|20
sqlite>

$ sqlite3 ex1　// SQLiteデータベース ex1 を作成し、ユーティリティ起動

SQLite version 3.6.11 // バージョン情報

Enter ".help" for instructions

Enter SQL statements terminated with a ";"

sqlite> create table tbl1(one varchar(10), two smallint); // テーブルtbl1作成

sqlite> insert into tbl1 values('hello!',10);

sqlite> insert into tbl1 values('goodbye', 20);

sqlite> select * from tbl1; // tbl1から全タプル表示

hello!|10

goodbye|20

sqlite>

プログラムを終了する際は、システムのEnd-Of-Fileキャラクタを入力する(通常はControl-D)か、割り込みキャラクタ(通常はControl-C)を入力して停止する。

セミコロンがSQLコマンドの終端となるので、これを入力するまでは複数行にわたって改行して入力することもできる。

sqlite> CREATE TABLE tbl2 (
   ...>   f1 varchar(30) primary key,
   ...>   f2 text,
   ...>   f3 real
   ...> );
sqlite>

sqlite> CREATE TABLE tbl2 (

...> f1 varchar(30) primary key,

...> f2 text,

...> f3 real

...> );

sqlite>

補足: SQLite_MASTERテーブル

データベーススキーマは、SQLiteデータベースの中に”sqlite_master”とよばれる特別なテーブルとして保存されている。
この特別なテーブルに対してSELECTステートメントを実行することでスキーマの情報が得られる。

sqlite> select * from sqlite_master;
    type = table
    name = tbl1
tbl_name = tbl1
rootpage = 3
     sql = create table tbl1(one varchar(10), two smallint)
sqlite>

sqlite> select * from sqlite_master;

type = table

name = tbl1

tbl_name = tbl1

rootpage = 3

sql = create table tbl1(one varchar(10), two smallint)

sqlite>

しかし、このsqlite_masterテーブルについては、DROP TABLE、UPDATE、INSERTやDELETEは使用できない。何かデータベースに変更があるときは、このテーブルは自動的に変更されるため、手動で値を変更することはできない。

sqlite3の特別なコマンド

入力の際に、ドット”.”つきのコマンドを入力すると、sqlite3プログラム自身へのコマンドとして解釈される。これら”ドット・コマンド”は、典型的にはクエリに対する出力フォーマットの形式を変更する際やクエリ文に対してあるプレパッケージを実行する際に使用される。

使用可能なドット・コマンドを確認するには、”.help”コマンドを入力する。

sqlite> .help  // ドット・コマンド .helpを入力 
.backup ?DB? FILE      Backup DB (default "main") to FILE // データベースをファイルにバックアップする
.bail ON|OFF           Stop after hitting an error.  Default OFF  // エラーが起きた際に停止するかどうか
.databases             List names and files of attached databases // 展開中のデータベースの名前とファイルパスをリスト表示
.dump ?TABLE? ...      Dump the database in an SQL text format SQL形式でデータベースをダンプ
.echo ON|OFF           Turn command echo on or off  // echoのオンオフ
.exit                  Exit this program  // sqlite3の終了 
.explain ON|OFF        Turn output mode suitable for EXPLAIN on or off.
.genfkey ?OPTIONS?     Options are:
                         --no-drop: Do not drop old fkey triggers.
                         --ignore-errors: Ignore tables with fkey errors
                         --exec: Execute generated SQL immediately
                       See file tool/genfkey.README in the source 
                       distribution for further information.
.header(s) ON|OFF      Turn display of headers on or off  // ヘッダを表示するかどうか
.help                  Show this message  // このメッセージ
.import FILE TABLE     Import data from FILE into TABLE  // FILEからTABLEへデータをインポート
.indices TABLE         Show names of all indices on TABLE
.iotrace FILE          Enable I/O diagnostic logging to FILE
.load FILE ?ENTRY?     Load an extension library
.mode MODE ?TABLE?     Set output mode where MODE is one of:  // 出力形式の変更
                         csv      Comma-separated values
                         column   Left-aligned columns.  (See .width)
                         html     HTML <table> code
                         insert   SQL insert statements for TABLE
                         line     One value per line
                         list     Values delimited by .separator string
                         tabs     Tab-separated values
                         tcl      TCL list elements
.nullvalue STRING      Print STRING in place of NULL values
.output FILENAME       Send output to FILENAME
.output stdout         Send output to the screen
.prompt MAIN CONTINUE  Replace the standard prompts
.quit                  Exit this program  // sqlite3の終了
.read FILENAME         Execute SQL in FILENAME  // FILENAMEに書いてあるSQLの実行
.restore ?DB? FILE     Restore content of DB (default "main") from FILE
.schema ?TABLE?        Show the CREATE statements  // テーブルのCREATEステートメントを表示(スキーマを表示)
.separator STRING      Change separator used by output mode and .import
.show                  Show the current values for various settings
.tables ?PATTERN?      List names of tables matching a LIKE pattern
.timeout MS            Try opening locked tables for MS milliseconds
.timer ON|OFF          Turn the CPU timer measurement on or off
.width NUM NUM ...     Set column widths for "column" mode
sqlite>

sqlite> .help // ドット・コマンド .helpを入力

.backup ?DB? FILE Backup DB (default "main") to FILE // データベースをファイルにバックアップする

.bail ON|OFF Stop after hitting an error. Default OFF // エラーが起きた際に停止するかどうか

.databases List names and files of attached databases // 展開中のデータベースの名前とファイルパスをリスト表示

.dump ?TABLE? ... Dump the database in an SQL text format SQL形式でデータベースをダンプ

.echo ON|OFF Turn command echo on or off // echoのオンオフ

.exit Exit this program // sqlite3の終了

.explain ON|OFF Turn output mode suitable for EXPLAIN on or off.

.genfkey ?OPTIONS? Options are:

--no-drop: Do not drop old fkey triggers.

--ignore-errors: Ignore tables with fkey errors

--exec: Execute generated SQL immediately

See file tool/genfkey.README in the source

distribution for further information.

.header(s) ON|OFF Turn display of headers on or off // ヘッダを表示するかどうか

.help Show this message // このメッセージ

.import FILE TABLE Import data from FILE into TABLE // FILEからTABLEへデータをインポート

.indices TABLE Show names of all indices on TABLE

.iotrace FILE Enable I/O diagnostic logging to FILE

.load FILE ?ENTRY? Load an extension library

.mode MODE ?TABLE? Set output mode where MODE is one of: // 出力形式の変更

csv Comma-separated values

column Left-aligned columns. (See .width)

html HTML <table> code

insert SQL insert statements for TABLE

line One value per line

list Values delimited by .separator string

tabs Tab-separated values

tcl TCL list elements

.nullvalue STRING Print STRING in place of NULL values

.output FILENAME Send output to FILENAME

.output stdout Send output to the screen

.prompt MAIN CONTINUE Replace the standard prompts

.quit Exit this program // sqlite3の終了

.read FILENAME Execute SQL in FILENAME // FILENAMEに書いてあるSQLの実行

.restore ?DB? FILE Restore content of DB (default "main") from FILE

.schema ?TABLE? Show the CREATE statements // テーブルのCREATEステートメントを表示(スキーマを表示)

.separator STRING Change separator used by output mode and .import

.show Show the current values for various settings

.tables ?PATTERN? List names of tables matching a LIKE pattern

.timeout MS Try opening locked tables for MS milliseconds

.timer ON|OFF Turn the CPU timer measurement on or off

.width NUM NUM ... Set column widths for "column" mode

sqlite>

出力フォーマットを変更する

sqlite3プログラムは、8つの異なるフォーマットに対応している。
“csv”、”column”、”html”、”insert”、”line”、”list”、”tabs”、”tcl”
“.mode”コマンドを使うことで、これら出力フォーマットを切り替えることができる。

“list”モード

sqlite> .mode list  // リスト形式での出力に変更
sqlite> select * from tbl1;
hello|10
goodbye|20
sqlite>

sqlite> .mode list // リスト形式での出力に変更

sqlite> select * from tbl1;

hello|10

goodbye|20

sqlite>

“.separator”コマンドを使用すると、リストモードのセパレータを変更することができる。
例えば、カンマとスペースをセパレータにすると、

sqlite> .separator ", "  // セパレータの変更
sqlite> select * from tbl1;
hello, 10
goodbye, 20
sqlite>

sqlite> .separator ", " // セパレータの変更

sqlite> select * from tbl1;

hello, 10

goodbye, 20

sqlite>

“line”モード
各列はデータベースの行を表しており、それぞれの行は”属性名 = データ”で表される。
連続したレコードは空行で区切られる。

sqlite> .mode line  // "line"モードでの出力に変更
sqlite> select * from tbl1;
one = hello
two = 10
　　　　　　　　　　　 // 空行による区切り
one = goodbye
two = 20
sqlite>

sqlite> .mode line // "line"モードでの出力に変更

sqlite> select * from tbl1;

one = hello

two = 10

　　　　　　　　　　　 // 空行による区切り

one = goodbye

two = 20

sqlite>

“column”モード
各レコードは対応する属性ごとに列で分けられ、各行で表示される。

sqlite> .mode column
sqlite> select * from tbl1;
one         two       
----------  ----------
hello       10        
goodbye     20        
sqlite>

sqlite> .mode column

sqlite> select * from tbl1;

one two

---------- ----------

hello 10

goodbye 20

sqlite>

デフォルトでは、各列は少なくとも10文字”———-”分の幅で表示される。
列の幅が広すぎる場合、”.width”コマンドで列の幅を変更できる。

sqlite> .width 12 6  // 第一列の幅を12文字、第二列の幅を6文字に変更
sqlite> select * from tbl1;
one           two   
------------  ------  // 12  6　文字に変更された
hello         10    
goodbye       20    
sqlite>

sqlite> .width 12 6 // 第一列の幅を12文字、第二列の幅を6文字に変更

sqlite> select * from tbl1;

one two

------------ ------ // 12 6　文字に変更された

hello 10

goodbye 20

sqlite>

最初の2行は列の属性が出力されていた。この表示は”.header”コマンドで設定することができる。

sqlite> .header off  // 属性情報の出力をoff
sqlite> select * from tbl1;
hello         10     // データのみを出力できた
goodbye       20    
sqlite>

sqlite> .header off // 属性情報の出力をoff

sqlite> select * from tbl1;

hello 10 // データのみを出力できた

goodbye 20

sqlite>

“insert”モードは、得られた出力を他のデータベースへの入力として使用できる。

sqlite> .mode insert new_table  // 出力を新しいテーブルnew_tableへ挿入するモードへ変更
sqlite> select * from tbl1;  　　// tbl1の全タプルを表示
// 出力をnew_tableへ挿入するためのコマンド発行)
INSERT INTO 'new_table' VALUES('hello',10);
INSERT INTO 'new_table' VALUES('goodbye',20);
sqlite>

sqlite> .mode insert new_table // 出力を新しいテーブルnew_tableへ挿入するモードへ変更

sqlite> select * from tbl1; 　　// tbl1の全タプルを表示

// 出力をnew_tableへ挿入するためのコマンド発行)

INSERT INTO 'new_table' VALUES('hello',10);

INSERT INTO 'new_table' VALUES('goodbye',20);

sqlite>

“html”モードは、XHTMLテーブルとして結果を表示する。ただし、開始タグ

と終了タグ

は出力されない。要素ととのみ。CGI作成時に便利？

結果をファイルへ出力する

デフォルトでは、sqlite3のクエリの結果は標準出力へ送られる。”.output”コマンドを使用すると、これを変更できる。引数にファイル名を与えればよい。再び標準出力に戻すには、”.output stdout”とすればよい。

sqlite> .mode list                // リストモードで表示
sqlite> .separator |              // セパレータをパイプ(|)に変更
sqlite> .output test_file_1.txt   // 出力先を標準出力からファイルへ変更
sqlite> select * from tbl1;       // SQLクエリを発行
sqlite> .exit                     // 終了
$ cat test_file_1.txt  // 出力結果があるファイルの中身を確認
hello|10
goodbye|20
$                      // OK

sqlite> .mode list // リストモードで表示

sqlite> .separator | // セパレータをパイプ(|)に変更

sqlite> .output test_file_1.txt // 出力先を標準出力からファイルへ変更

sqlite> select * from tbl1; // SQLクエリを発行

sqlite> .exit // 終了

$ cat test_file_1.txt // 出力結果があるファイルの中身を確認

hello|10

goodbye|20

$ // OK

良い進捗報告に必要なもの

進行状況 (前回から今回までに行った作業、計画と現状について)
進行を妨げる妨害要因
遅れを取り戻すための方法、必要な援助

東証一部上場会社 1699社コードリスト (2013.02.24現在)

['1301', '1332', '1334', '1352', '1377', '1379', '1414', '1417', '1514', '1515', '1518', '1605', '1606', '1661', '1662', '1712', '1719', '1720', '1721', '1722', '1762', '1766', '1780', '1801', '1802', '1803', '1805', '1808', '1810', '1812', '1813', '1814', '1815', '1816', '1819', '1820', '1821', '1822', '1824', '1826', '1827', '1833', '1834', '1835', '1847', '1852', '1860', '1861', '1865', '1866', '1867', '1868', '1870', '1871', '1878', '1879', '1881', '1882', '1883', '1884', '1885', '1888', '1890', '1893', '1896', '1898', '1899', '1911', '1914', '1916', '1919', '1921', '1924', '1925', '1926', '1928', '1929', '1930', '1934', '1937', '1939', '1941', '1942', '1944', '1945', '1946', '1949', '1950', '1951', '1952', '1954', '1956', '1959', '1961', '1963', '1964', '1967', '1968', '1969', '1972', '1973', '1975', '1978', '1979', '1980', '1982', '1983', '2001', '2002', '2003', '2004', '2009', '2052', '2053', '2056', '2107', '2108', '2109', '2120', '2127', '2128', '2131', '2151', '2168', '2170', '2174', '2175', '2181', '2193', '2196', '2198', '2201', '2204', '2206', '2207', '2211', '2212', '2215', '2217', '2220', '2229', '2264', '2267', '2269', '2270', '2281', '2282', '2284', '2286', '2288', '2290', '2292', '2301', '2305', '2309', '2317', '2322', '2327', '2331', '2353', '2359', '2371', '2372', '2378', '2395', '2398', '2413', '2418', '2432', '2433', '2440', '2450', '2453', '2462', '2466', '2491', '2501', '2502', '2503', '2531', '2533', '2540', '2572', '2579', '2580', '2590', '2593', '2594', '2597', '2599', '2602', '2607', '2613', '2651', '2659', '2660', '2662', '2664', '2670', '2674', '2676', '2678', '2681', '2685', '2687', '2692', '2695', '2698', '2715', '2726', '2729', '2730', '2733', '2734', '2737', '2749', '2753', '2760', '2764', '2768', '2772', '2784', '2791', '2792', '2801', '2802', '2809', '2810', '2811', '2812', '2815', '2871', '2874', '2875', '2897', '2899', '2908', '2910', '2914', '2915', '2918', '2922', '3001', '3002', '3003', '3004', '3022', '3023', '3028', '3034', '3036', '3048', '3050', '3064', '3076', '3086', '3087', '3088', '3091', '3092', '3097', '3098', '3099', '3101', '3103', '3104', '3105', '3106', '3107', '3109', '3110', '3116', '3141', '3148', '3151', '3153', '3156', '3159', '3167', '3201', '3202', '3204', '3205', '3225', '3228', '3231', '3258', '3302', '3313', '3315', '3321', '3333', '3341', '3349', '3360', '3366', '3371', '3382', '3391', '3395', '3396', '3397', '3398', '3401', '3402', '3405', '3407', '3408', '3421', '3431', '3433', '3434', '3436', '3443', '3501', '3512', '3513', '3514', '3521', '3524', '3526', '3529', '3551', '3553', '3569', '3577', '3580', '3591', '3593', '3606', '3607', '3608', '3620', '3626', '3627', '3630', '3632', '3635', '3636', '3639', '3640', '3656', '3657', '3659', '3660', '3662', '3708', '3715', '3724', '3730', '3738', '3762', '3769', '3770', '3774', '3817', '3834', '3861', '3864', '3865', '3877', '3878', '3880', '3893', '3941', '3946', '3950', '4003', '4004', '4005', '4007', '4008', '4021', '4022', '4023', '4027', '4028', '4031', '4041', '4042', '4043', '4044', '4045', '4046', '4047', '4061', '4062', '4063', '4064', '4078', '4088', '4091', '4092', '4095', '4097', '4098', '4099', '4100', '4109', '4112', '4114', '4116', '4118', '4151', '4182', '4183', '4185', '4186', '4187', '4188', '4201', '4202', '4203', '4204', '4205', '4206', '4208', '4212', '4215', '4216', '4217', '4218', '4220', '4221', '4228', '4229', '4231', '4238', '4271', '4272', '4282', '4283', '4295', '4301', '4307', '4310', '4312', '4319', '4321', '4324', '4326', '4331', '4337', '4340', '4343', '4344', '4346', '4350', '4362', '4401', '4403', '4404', '4410', '4452', '4461', '4471', '4502', '4503', '4506', '4507', '4508', '4512', '4514', '4516', '4519', '4521', '4523', '4527', '4528', '4530', '4531', '4534', '4536', '4538', '4539', '4540', '4541', '4543', '4544', '4547', '4548', '4549', '4550', '4551', '4553', '4554', '4555', '4559', '4568', '4569', '4574', '4577', '4578', '4581', '4611', '4612', '4613', '4614', '4617', '4619', '4620', '4626', '4631', '4633', '4634', '4641', '4651', '4653', '4658', '4661', '4665', '4666', '4668', '4671', '4674', '4676', '4678', '4679', '4680', '4681', '4684', '4687', '4689', '4694', '4696', '4704', '4708', '4711', '4714', '4716', '4718', '4719', '4722', '4724', '4725', '4726', '4728', '4732', '4733', '4739', '4743', '4745', '4746', '4762', '4767', '4768', '4775', '4776', '4779', '4799', '4801', '4812', '4820', '4825', '4826', '4839', '4848', '4901', '4902', '4911', '4912', '4914', '4917', '4919', '4921', '4922', '4924', '4927', '4928', '4951', '4956', '4958', '4963', '4967', '4968', '4971', '4973', '4975', '4977', '4985', '4989', '4992', '4994', '4996', '4997', '5002', '5007', '5009', '5011', '5012', '5013', '5015', '5017', '5018', '5019', '5020', '5101', '5105', '5108', '5110', '5121', '5122', '5142', '5185', '5186', '5187', '5191', '5192', '5195', '5196', '5201', '5202', '5204', '5208', '5210', '5214', '5218', '5232', '5233', '5234', '5261', '5262', '5269', '5288', '5301', '5302', '5310', '5331', '5332', '5333', '5334', '5337', '5344', '5351', '5352', '5363', '5367', '5384', '5391', '5393', '5401', '5406', '5408', '5410', '5411', '5413', '5423', '5440', '5444', '5445', '5449', '5451', '5453', '5457', '5463', '5464', '5471', '5476', '5480', '5481', '5482', '5486', '5491', '5541', '5563', '5602', '5612', '5631', '5632', '5658', '5659', '5702', '5703', '5706', '5707', '5711', '5713', '5714', '5715', '5726', '5727', '5738', '5741', '5801', '5802', '5803', '5805', '5807', '5809', '5812', '5815', '5819', '5821', '5851', '5857', '5901', '5902', '5909', '5911', '5912', '5915', '5923', '5929', '5930', '5932', '5936', '5938', '5942', '5943', '5946', '5947', '5949', '5951', '5957', '5958', '5959', '5974', '5975', '5976', '5981', '5988', '5991', '5992', '5998', '6005', '6013', '6054', '6101', '6103', '6104', '6113', '6118', '6135', '6136', '6138', '6140', '6141', '6146', '6151', '6201', '6203', '6205', '6208', '6210', '6217', '6218', '6222', '6247', '6250', '6262', '6268', '6269', '6272', '6273', '6274', '6277', '6278', '6282', '6287', '6291', '6293', '6298', '6301', '6302', '6305', '6306', '6309', '6310', '6315', '6316', '6317', '6319', '6326', '6328', '6330', '6331', '6332', '6333', '6335', '6339', '6340', '6345', '6349', '6351', '6355', '6358', '6361', '6362', '6363', '6366', '6367', '6368', '6369', '6370', '6371', '6373', '6375', '6376', '6378', '6379', '6381', '6383', '6390', '6393', '6395', '6406', '6407', '6409', '6412', '6413', '6417', '6418', '6419', '6420', '6428', '6430', '6436', '6440', '6444', '6445', '6448', '6454', '6455', '6457', '6459', '6460', '6461', '6462', '6463', '6465', '6470', '6471', '6472', '6473', '6474', '6479', '6480', '6481', '6482', '6485', '6486', '6489', '6490', '6498', '6501', '6502', '6503', '6504', '6505', '6506', '6507', '6508', '6513', '6517', '6581', '6584', '6586', '6588', '6590', '6592', '6594', '6617', '6620', '6622', '6630', '6632', '6640', '6641', '6644', '6645', '6651', '6652', '6674', '6675', '6676', '6678', '6701', '6702', '6703', '6704', '6706', '6707', '6715', '6718', '6723', '6724', '6727', '6728', '6730', '6731', '6737', '6741', '6742', '6744', '6745', '6751', '6752', '6753', '6754', '6755', '6756', '6758', '6762', '6763', '6767', '6768', '6770', '6771', '6773', '6779', '6788', '6789', '6791', '6794', '6796', '6798', '6800', '6801', '6803', '6804', '6806', '6807', '6809', '6815', '6816', '6817', '6820', '6823', '6839', '6841', '6844', '6845', '6849', '6850', '6853', '6855', '6856', '6857', '6858', '6859', '6860', '6861', '6866', '6869', '6875', '6877', '6883', '6885', '6900', '6901', '6902', '6905', '6910', '6911', '6914', '6915', '6923', '6924', '6925', '6926', '6927', '6929', '6935', '6937', '6938', '6941', '6947', '6951', '6952', '6954', '6958', '6961', '6963', '6965', '6966', '6967', '6971', '6973', '6976', '6981', '6985', '6986', '6988', '6989', '6995', '6996', '6997', '6999', '7003', '7004', '7007', '7011', '7012', '7013', '7102', '7105', '7122', '7148', '7150', '7161', '7164', '7201', '7202', '7203', '7205', '7211', '7212', '7220', '7222', '7224', '7226', '7230', '7231', '7236', '7238', '7239', '7240', '7241', '7242', '7243', '7244', '7245', '7246', '7248', '7250', '7251', '7256', '7259', '7260', '7261', '7262', '7266', '7267', '7269', '7270', '7272', '7274', '7276', '7277', '7278', '7280', '7282', '7283', '7294', '7296', '7305', '7309', '7312', '7313', '7414', '7416', '7420', '7421', '7427', '7433', '7438', '7442', '7445', '7447', '7448', '7451', '7453', '7455', '7456', '7459', '7463', '7466', '7476', '7480', '7481', '7482', '7483', '7494', '7504', '7506', '7508', '7512', '7513', '7514', '7516', '7517', '7518', '7520', '7522', '7524', '7532', '7537', '7541', '7545', '7550', '7552', '7554', '7558', '7561', '7581', '7591', '7594', '7595', '7599', '7600', '7601', '7606', '7607', '7608', '7609', '7611', '7613', '7615', '7616', '7619', '7628', '7630', '7631', '7637', '7640', '7649', '7701', '7702', '7709', '7714', '7715', '7717', '7718', '7721', '7723', '7728', '7729', '7730', '7731', '7732', '7733', '7734', '7735', '7739', '7740', '7741', '7744', '7745', '7751', '7752', '7756', '7762', '7769', '7775', '7817', '7819', '7821', '7822', '7825', '7832', '7838', '7840', '7844', '7846', '7860', '7862', '7864', '7867', '7868', '7873', '7874', '7885', '7893', '7897', '7898', '7905', '7908', '7911', '7912', '7913', '7914', '7915', '7916', '7917', '7921', '7925', '7936', '7937', '7942', '7943', '7944', '7947', '7949', '7951', '7952', '7955', '7956', '7958', '7961', '7962', '7966', '7968', '7970', '7971', '7972', '7974', '7976', '7979', '7981', '7984', '7987', '7988', '7990', '7994', '7995', '7999', '8001', '8002', '8005', '8007', '8008', '8011', '8012', '8013', '8014', '8015', '8016', '8018', '8020', '8022', '8025', '8028', '8029', '8031', '8032', '8035', '8036', '8037', '8038', '8043', '8050', '8051', '8052', '8053', '8056', '8057', '8058', '8059', '8060', '8061', '8065', '8068', '8070', '8074', '8075', '8078', '8081', '8084', '8086', '8087', '8088', '8089', '8090', '8091', '8093', '8095', '8096', '8097', '8098', '8101', '8103', '8111', '8113', '8114', '8127', '8129', '8130', '8131', '8132', '8133', '8136', '8137', '8140', '8141', '8142', '8150', '8151', '8153', '8154', '8155', '8158', '8159', '8160', '8165', '8166', '8168', '8170', '8173', '8174', '8175', '8178', '8179', '8181', '8182', '8184', '8185', '8194', '8196', '8200', '8201', '8203', '8207', '8214', '8217', '8218', '8219', '8227', '8229', '8233', '8237', '8242', '8245', '8248', '8251', '8252', '8253', '8255', '8260', '8263', '8266', '8267', '8270', '8273', '8274', '8276', '8278', '8279', '8281', '8282', '8283', '8289', '8291', '8303', '8304', '8306', '8308', '8309', '8316', '8324', '8325', '8327', '8331', '8332', '8333', '8334', '8336', '8337', '8338', '8339', '8341', '8342', '8343', '8344', '8345', '8346', '8349', '8350', '8354', '8355', '8356', '8358', '8359', '8360', '8361', '8362', '8363', '8364', '8366', '8367', '8368', '8369', '8374', '8377', '8379', '8381', '8382', '8383', '8385', '8386', '8387', '8388', '8390', '8392', '8393', '8394', '8395', '8396', '8397', '8399', '8409', '8410', '8411', '8415', '8418', '8423', '8424', '8425', '8439', '8473', '8511', '8512', '8515', '8518', '8519', '8521', '8522', '8524', '8527', '8529', '8530', '8536', '8537', '8541', '8542', '8543', '8544', '8545', '8550', '8551', '8558', '8562', '8563', '8566', '8570', '8572', '8584', '8585', '8586', '8591', '8593', '8595', '8600', '8601', '8604', '8609', '8613', '8614', '8616', '8617', '8622', '8624', '8628', '8630', '8692', '8697', '8698', '8703', '8706', '8707', '8713', '8714', '8725', '8729', '8742', '8750', '8766', '8771', '8772', '8793', '8795', '8801', '8802', '8803', '8804', '8806', '8815', '8818', '8830', '8833', '8835', '8840', '8841', '8842', '8848', '8860', '8864', '8869', '8870', '8871', '8875', '8876', '8877', '8879', '8880', '8881', '8895', '8897', '8904', '8905', '8907', '8915', '8918', '8923', '8933', '8934', '8944', '8999', '9001', '9003', '9005', '9006', '9007', '9008', '9009', '9010', '9014', '9020', '9021', '9022', '9031', '9037', '9039', '9041', '9042', '9044', '9045', '9047', '9048', '9058', '9062', '9064', '9065', '9066', '9067', '9068', '9069', '9070', '9072', '9074', '9075', '9076', '9081', '9086', '9101', '9104', '9107', '9110', '9113', '9115', '9119', '9130', '9132', '9201', '9202', '9232', '9301', '9302', '9303', '9304', '9305', '9306', '9310', '9312', '9324', '9351', '9358', '9364', '9366', '9368', '9369', '9370', '9375', '9380', '9381', '9401', '9404', '9409', '9412', '9413', '9422', '9430', '9432', '9433', '9435', '9437', '9449', '9470', '9474', '9475', '9477', '9479', '9501', '9502', '9503', '9504', '9505', '9506', '9507', '9508', '9509', '9511', '9513', '9531', '9532', '9533', '9534', '9536', '9543', '9600', '9601', '9602', '9603', '9605', '9607', '9613', '9616', '9619', '9621', '9622', '9627', '9628', '9632', '9633', '9671', '9672', '9675', '9678', '9681', '9682', '9684', '9692', '9697', '9704', '9706', '9715', '9716', '9717', '9719', '9722', '9726', '9728', '9729', '9731', '9735', '9739', '9740', '9742', '9743', '9744', '9746', '9747', '9749', '9755', '9757', '9759', '9760', '9763', '9766', '9783', '9787', '9788', '9790', '9792', '9793', '9795', '9810', '9828', '9830', '9831', '9832', '9842', '9843', '9850', '9854', '9861', '9869', '9880', '9882', '9883', '9887', '9889', '9896', '9900', '9902', '9928', '9930', '9932', '9934', '9938', '9945', '9946', '9948', '9956', '9957', '9962', '9963', '9972', '9974', '9979', '9982', '9983', '9984', '9987', '9989', '9990', '9991', '9993', '9994', '9997']

[Algorithms] Algorithms and Data Structure

What is algorithm?

Algorithm: well-defined computational procedure. it has input and output such as some values. it is composed of a sequence of computational steps.

Correctness: for every input instance, the algorithm halts with the correct output.

Correct algorithm solves the given computational problem.

What is data structure?

Data Structure: a way to store and organize data in order to facilitate access and modifications.

No single data structure works well for all purposes.

Various techniques of algorithm design and analysis

Order notation
Minimum spanning trees (MST)
Maximum flow in a network
Divide-and-conquer
Dynamic Programming (DP)
Amortized analysis

etc.

Hard problems

NP-complete: the subset of computational problems.
1) no efficient algorithm for this type of problem has ever been found, and nobody has ever proven that an efficient algorithm for one cannot exist. (In other words, no one knows whether or not efficient algorithm exist for NP-complete problem.)
2) this problem has remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. (!)
3) several NP-complete problems are similar to problems for which we know efficient algorithms.

E.g. Traveling-salesman problem
To deliver goods to several address, we want to know the shortest overall distance traveled by car. => This is NP-complete (no efficient algorithm exists! However under some assumptions, we can use approximate algorithms.)

Efficiency

Different algorithms devised to solve the same problem often differ dramatically in their efficiency. (=> Discuss Order notation)
Difference of efficiency can be much more significant than differences than differences due to hardware and software.

E.g. Time complexity
Two algorithms for sorting. if n items given as input, computational time of each algorithm are
1) Insertion sort: $c_1 n^2$
2) Merge sort: $c_2 n{\rm log}n$
where $c_1, c_2$ are constant.
Although insertion sort usually runs faster than merge sort for small input size, the input size $c$ becomes large enough, merge sort’s advantage of ${\rm log}n$ vs. $n$ .