第一回課題：データ構造とアルゴリズム（２００９）

課題の提出

• 提出期限
  2009/05/14 (Thu), 18:00 JST 【予定】
• 提出方法
  Web CTから提出
• 条件
  「必修」課題は全て提出してください。
  「発展」課題の提出は任意です。
  （「発展」課題を出さなくともＡ評価になる可能性はありますが、確実に目指すのなら「発展」課題をするほうがよいでしょう）
  

課題１

• ★必修：課題１ａ★

  深さ優先探索を行うプログラムを、再帰呼び出しを用いずにＣ言語で書いて実行せよ。
  処理対象のグラフＧ３は隣接行列で下記のように与える。
  探索中に複数の選択肢がある場合は、常に番号の若いノードを選択すること（授業のプログラムと同一）。
  

  Graph G3

  #define N 8 int edge[N][N] = { /* 0 1 2 3 4 5 6 7 */ {0,1,0,0,1,0,0,0}, /* 0 */ {1,0,0,0,0,0,1,0}, /* 1 */ {0,0,0,1,0,0,1,0}, /* 2 */ {0,0,1,0,0,0,0,1}, /* 3 */ {1,0,0,0,0,1,0,0}, /* 4 */ {0,0,0,0,1,0,1,0}, /* 5 */ {0,1,1,0,0,1,0,1}, /* 6 */ {0,0,0,1,0,0,1,0} /* 7 */ };

  • 提出物〔1a-1〕：Ｃソースファイル（コメント必須）
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    プログラムで工夫した行について、必ず何かしらの説明をコメントの形でプログラム中に書き込むこと。
    コメントがないようなプログラムは提出とはみなさないので注意すること。
    

    【注意】
    誰かに教えてもらった場合：	その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。）
    誰かに教えてあげた場合：	その学生（氏名・学籍番号）をプログラム先頭に記すこと。
    お互いに相談した場合：	教えてもらった・教えてあげたの例に準拠して提出してください。

  • 提出物〔1a-2〕：プログラムのグラフG3に対して、出発点をノード０としたときの出力結果を保存したテキストファイル
    

  • 提出物〔1a-3〕：プログラムのグラフG3に対して、出発点をノード１としたときの出力結果を保存したテキストファイル
    

• ★必修：課題１ｂ★

  授業で示した深さ優先探索プログラムにおいて、頂点数８の連結無向グラフのうち、空間計算量を最小にするようなグラフの例と出発ノードを示せ。
  また、その時の空間計算量を示せ。

  • 提出物〔1b-1〕：テキストファイル
    プレーンテキスト（拡張子 .txt）で十分であるが、必要があればword等で書いてpdfで提出してもよい。
    

• ★必修：課題１ｃ★

  授業で示した深さ優先探索プログラムにおいて、頂点数Ｎ、辺の数Ｅに対して時間計算量はＯ（Ｎ×Ｎ）である。
  どのような改良を施せば、この時間計算量を削減することができるか、プログラムの改良の方針を示せ。
  また、そのときの時間計算量をＮ，Ｅをもちいて示せ。
  （ヒント：連結無向グラフで考えられる辺の数の最大値はＮを用いてどう表せるか？）
  

  • 提出物〔1c-1〕：テキストファイル
    プレーンテキスト（拡張子 .txt）で十分であるが、必要があればword等で書いてpdfで提出してもよい。
    

• ◆発展：課題１ｐ◆

  課題１ｃの改良法に基づき、実際にプログラムを作成し、実行せよ。
  

  • 提出物〔1p-1〕：Ｃソースファイル（コメント必須）
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    講義で説明した元のプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
    

  • 提出物〔1p-2〕：頂点０、頂点１を起点とするＧ３の処理結果を保存したテキストファイル
    実際の実行時間についても言及すること（記述のみでも計測結果を示してもよい）。