2020/7/18
期末レポートの提出期限を7/31(金)の24:00とします．
2020/7/6
期末レポートの提出方法を公開しました．レポート提出方法
2020/6/23
期末レポートの詳細を公開しました．
2020/6/22
期末試験を期末レポートに置き換えたことにより，評価のための点数配分を変更しました．詳細は以下のページをご覧ください．
2020/5/27
感染症拡大予防のため，期末試験は期末レポートに置き換える予定です．レポート課題の詳細な内容は6月中〜下旬に公開予定です．
2020/4/3
講義の配信はzoom webinarで行います．また，URLはこの講義ホームページに記載します．ログインにECCSアカウントが必要です．
本講義では情報科学の重要な基礎となっているアルゴリズムとデータ構造に関して学習します．具体的には，
ことを目的としています．この講義を通して
ことができるように授業が設計されています．
本授業は全てオンラインで実施する予定です． 講義はZoom webinarにて配信する予定です．講義の配信動画を視聴するためには，インターネット環境，およびブラウザが必要です．なお，従量課金制による通信費がかからないよう，無料で使えるWifi環境がある場所や定額制のインターネット接続環境で視聴することを強く推奨します．
| 場所 | オンラインで実施予定． |
|---|---|
| 時間 | 水曜日3限（13:00 - 14:45），ただし講義の動画，およびPDFは後からでも見ることが可能． |
| 講義担当者 | 相田 仁，矢谷 浩司 (koji “at-mark” iis-lab.org) |
| TA | 杉山 悠司，鈴木 凌斗 (algorithms “at-mark” iis-lab.org) |
講義配信用Zoom webinarのURLは以下のスプレッドシートに記載します．なお，ECCSアカウントでログインする必要があります．URLは毎回変わりますので，必ずご確認ください．
https://docs.google.com/spreadsheets/d/1UOkDbt2UC1EaECyN29dbuNu27DtL20geRHzxoxewmek/edit?usp=sharing
| 回 | 日程 | 講義内容 |
|---|---|---|
| #0 | 4/8 | プレイントロ，授業で使うシステムの紹介，general Q&A |
| trackの利用方法 | ||
| #1 | 4/15 | イントロダクション，計算量 |
| trackの利用方法 | ||
| #2 | 4/22 | 累積和，データ構造 |
| #3 | 5/7 (木) | 探索（サーチ） |
| #4 | 5/13 | 文字列照合 |
| #5 | 5/20 | 整列（ソート） |
| #6 | 5/27 | 動的計画法1（フィボナッチ数列，最大和問題，ナップサック問題） |
| #7 | 6/3 | 動的計画法2（その他のDP問題） |
| #8 | 6/10 | 「難しい問題」，整数関連 |
| #9 | 6/17 | BFS，DFS |
| #10 | 6/24 | 期末レポート課題説明，レポート提出方法 |
| グラフアルゴリズム1（最短経路問題） | ||
| #11 | 7/1 | グラフアルゴリズム2（最大流問題，最小費用流問題） |
| #12 | 7/8 | グラフアルゴリズム3（二部グラフのマッチング問題，最小全域木），さいごに |
| #13 | 7/15（補講日） | 特別イベント: Crush Your Coding Interview with Facebook |
本講義を受講希望の方は以下のフォームより登録を行ってください．また，単位習得のためにこの講義を受講する方はUTASでの登録を別途行ってください．
https://iis-lab.org/algorithms-entry
本講義を受講する場合，以下の知識，経験，および実験機器があることを想定しています．
本講義の受講にはECCSアカウント（xxxx@g.ecc.u-tokyo.ac.jp）が必須です．セットアップ後使用できるようになるまで少し時間がかかりますので，自分のアカウントの詳細がわからない，という人は以下の動画を確認し，講義開始までに準備をしておいてください．
https://www.youtube.com/watch?v=89_fjWDdzQ4&feature=youtu.be
成績の評価は以下のように行います．
ただし，状況に応じて点数配分を数点程度変更することがあります．また，期末試験はレポート等の形式に変更する可能性があります．なお，出席はとりません．
期末レポートを提出しない場合，原則未受験として扱います．ただし，コードチャレンジに参加しており，期末レポートを提出せずに成績をつけることを希望する場合には，矢谷まで7/15正午までに連絡をしてください．
この講義は毎回2つのパートに分かれています．
この講義では両パートに積極的に参加することが求められています．
矢谷が行う講義は全てZoom webinarを通して配信されます．ECCSアカウントでログインする必要がありますので，予めアカウント情報を確認しておいてください．
配信された講義は，配信終了後もオンラインで視聴できるようにします．詳細はこの講義のページ，およびITC-LMSをチェックしてください．
もし，Zoom webinarを見ることが出来ないネットワーク環境（例えば使用するネットワークの制限でZoom webinarにアクセスできないなど）しか利用できず，この講義を受講したい，という学生さんは，矢谷及びTAさんにメールで連絡をお願いします．
授業中及びその後の授業内容に関する質問は，zoom内のQ&A機能を使って行ってください．
本講義のコードチャレンジではtrackというシステムを使います．trackはオンライン上でプログラミングに関する学習を行ったり，指定された課題に対して自分のコードを提出したりすることが出来ます．またコーディング自体をブラウザ上でできるようになっているため，コーディングに必要な環境構築等を行う必要がありません．
本講義ではPython3を使用します．trackではPython3.6.1がサポートされています（2020年3月現在）．それ以外の言語の使用は認めません．また，track以外のシステムを用いた課題提出も認めません．
コードチャレンジには2種類あります．
基本課題はぜひしっかりと取り組み，解いてください．その上でExtra課題にも取り組んでもらえればと思います．
講義パート終了後すぐ，google formにより登録していただいたメールアドレスに対して，trackからのメールを配信します．そのメールに該当する回の課題を行うページへのリンクが記載されています．track上でのコーディング・デバッグ方法，および課題提出方法はこちらのPDFを参照してください．
メールはnoreply@tracks.runより配信されますので，メールクライアント等においてフィルタリング機能を設定している場合には，このメールアドレスからのメールを受信できるように予め設定をしてください．また，アドブロッカーなどを使用していると，ブラウザ上でうまく表示できなかったり，エラーを起こしたりすることがあります．この場合には，アドブロッカーを一時的に停止させてみてください．
trackにおけるトラブルが発生した場合は，slackにてTAさんに連絡をしてください．
コードチャレンジではいくつかのテストケースが予め設定されています．それらテストケースの通った数を元に，原則[配点]*[テストケース合格率]で点数を計算します．採点に特別な扱いがある場合には，その旨を問題文に記します．
頻繁にテストケースを実行し，デバッグを行ってください．これにより提出間際でのミスを防ぐことができる他，コードが自動保存されるので，万が一提出作業を行えなくても，最終保存されたコードを元に採点が 行われます．
採点は最終提出物に対してのみ行われます．したがって，途中でどれだけミスをしていてもペナルティはありません．
Extra課題に関しては提出されたコードに対して後日類似度チェック等を行い，明らかに類似したコードが あった場合は，その全てに対してペナルティを課します．基本課題に関してはほぼ同じようなコードになるはずですので，このルールを直接は適用しませんが，類似度チェックは行う予定です．
講義で使うシステムではコードをテストケースにかけた時点で，自動でバージョン管理します．コピペ等を行なった場合には，不自然にコード行数が増えたり，テストケースにパスする回数が突然増えたりするので，その辺りもチェックします．不自然な編集があった提出に関してはペナルティを適用することがありますので，十分気をつけてください．
与えられた基本課題においては，入出力や問題文で指示がある場合を除き，実装すべき処理において標準ライブラリや問題で指定されていない外部の関数やライブラリ等を使用しないでください． そのような提出物はテストケースに合格していても，採点されませんで注意してください．Extra課題においては，適宜外部の関数等を使っても良いものとします．
コードチャレンジの課題によってはコードの一部分（コーディング画面の初期コードとは別のコード）があらかじめ与えられている場合があります． その場合，問題文に明記してありますので，指示に従ってください．
コードチャレンジの課題を見ながら，本やWeb上の情報を参考にすることは問題ありません．ただし， 記載されているコードなどをそのまま使うことのないようにしてください．また，友達同士で教え合うのも積極的に行ってください（教えることができる，というのは十分に理解できている証拠でもあります）．ただし，書いたコードを直接見せ合うのではなく，考え方だけを共有するようにしてください．
この講義で重要なのは，「自分で手を動かす」ことを大切にすることです．アルゴリズムやコーディングに自信がなくても，授業で紹介されている内容を理解し，努力すれば一定の評価につながるようになっていますので，後から誤解を招きかねない行為をしないようにお願いいたします．
提出物に対しては後日類似度チェックを行います．以下のような提出物は該当するものすべてに対して採点を取り消します．
悪質な場合にはより大きなペナルティになることがあります．十分気をつけてください．
以下の情報をメールにて，algorithms “at-mark” iis-lab.orgに送ってください．可能な限り事前に，事後でも速やかにお願いします．
認められた場合，課題提出期限をこちらが指定する日時まで延長します．
大きな怪我や病気などの例外を除き，病欠，公欠を希望する授業日から1週間以上を経過した場合は，認めないものとします．
剽窃や不適切な引用，改竄などはAcademic Misconductとして重い処分を受けます．この講義ではコードチャレンジにおける提出物や，期末試験での答案における不正行為により不当に評価を得ようとする行為に対して特に厳重に処罰します．例えば，
などが挙げられます．特に重大なAcademic Misconductが発見された場合，その影響度の大きさに応じて以下の罰則を与えることになります．
レポートやソースコードは誤解の生じないように十分注意して作成・管理してください．
以下の書籍・リンクはこの講義の資料を作る際に参考にさせていただいたり，講義内容に関する大きな刺激を受けたものになります．以下に挙げているもの以外にも参考になる様々な情報がありますので，興味を持ったトピックに関して色々とご自身で調べていただければと思います．
またpythonの基礎の学習には様々なオンラインコースがありますので，それを活用することをおすすめします．
ここでは講義中に出た講義に関係する質問とその返答を取り上げています．