2014年後期 データ構造とアルゴリズム&プログラミング演習Ⅲ




データ構造とアルゴリズムの授業内容
1
バブルソート, クイックソート
2
マージソート, コームソート
3
リニアサーチ, バイナリサーチ
4
C言語のポインタの復習, 動的配列
5
リスト
6
スタック, キュー
7
再帰呼び出し
8
2分木, 平衡木 (追加資料
9
ハッシュ関数 (参考資料
10
誤差, 複雑な方程式を解く (追加資料
11
文字列検索 (追加資料
12
バックトラック (8クイーン, 15パズル
13
動的計画法
14
ダイクストラ法 (追加資料
    • 欠席6回以上は不合格。
    • 欠席レポート

      • 欠席1回につき、ここにあるPDFファイルの中から任意の1ページを日本語に訳したものを紙に手で書いて提出。

  • プログラミング演習Ⅲの単位の取り方=実演チェック

    • 上記参考書にある以下のコードについて、各回、実演チェックをする。
      • つまり、各コードのどこを変更したかを説明し、それをコンパイルして、動作確認する、という一連の動作を、目の前で実演してもらう。
    • 下の表の左半分の基本課題のコードについては、実演チェックは必須。しかも、次の回までにチェックを受けること。
      • 基本課題のコードは、すべて実演チェックを受ければ88点を与える。
      • 実演チェックを受けなかったコードひとつ毎に、10点を減点する。
    • 下の表の右半分の発展課題のコードについては、実演チェックを受けるかどうかは自由。講義の最終回までにチェックを受ければよい。
      • 発展課題のコードは、ひとつのコードについてチェックを受ける毎に、4点ずつ加点。
    • 教科書にあるすべてのソースコードはここからダウンロードできるが、この講義用に改変したコードもあるので、注意。


基本課題(締切:次回, 点数:満点が88点、ひとつ欠けると-10点)
発展課題(締切:最終回, 点数:ひとつ毎に4点)
1
バブルソート, クイックソート
List 1-1, List 1-2, List 1-3, List 1-4


2
マージソート, コームソート
List 1-5, List 1-6
挿入ソート
List 1-8
3
リニアサーチ, バイナリサーチ, 構造体のサーチ
List 2-1, List 2-3, List 2-5
自己組織化探索
List 2-7
4
動的配列
List 3-3


5
リストのサーチ
List 3-4, List 3-5
リストを用いた自己組織化探索
List 3-7
6
スタック, キュー
List 4-1, List 4-5
スタックによる式の計算
List 4-3
7
フィボナッチ数の計算, アッカーマン関数の計算
右ファイルに書きこんでいるところをチェック(途中で助けを求めない): fib.c, ack.c


8
2分木と「マップ」
List 6-4
逆ポーランド記法
List 12-1
9
ハッシュ関数, ハッシュマップ
List 7-1, List 7-2, List 7-3
テンパズル
List 12-3
10
誤差, 複雑な方程式を解く
List 8-3, List 8-4, List 8-8
ニュートン法
自分で考えて一から書く)
11
文字列検索, BM法
List 9-1, List 9-3
KMP法
List 9-2
12
バックトラック
List 10-1
11パズル
List 10-2
13
動的計画法
List 11-1
(基本課題の続き)
List 11-1
14
ダイクストラ法
List 13-6電停間の距離