本講義では情報科学の重要な基礎となっているアルゴリズムとデータ構造に関して学習します．具体的には，

• アルゴリズムとデータ構造に関する基礎知識を習得する
• Pythonを用いて代表的なアルゴリズム・データ構造を実装する
• 講義内で学習した内容を元に応用的なコーディング課題に取り組む

ことを目的としています．この講義を通して

• 代表的なアルゴリズムの考え方を理解する
• その考え方をコードに落とし込む力を養う
• 競技プログラミング等，様々なコーディング課題に取り組める知識を積み上げる

ことができるように授業が設計されています．

本講義は，学部横断型プログラム「数理・データサイエンス教育プログラム」の対象になっています．
http://www.mi.u-tokyo.ac.jp/mds-oudan/

本授業は原則対面形式で行いまが，メタバース工学部生はオンラインで受講することを許可します． 講義終了後には講義の録画を提供します．

講義の配信動画を視聴したり，プログラミング課題に取り組むためには，インターネット環境，およびブラウザが必要です．なお，従量課金制による通信費がかからないよう，無料で使えるWifi環境がある場所や定額制のインターネット接続環境で受講することを強く推奨します．

本授業はメタバース工学部においても同時開講されます．受講形式，評価基準が本学学生とメタバース工学部生では異なります． どちらの受講生も本ページで提供されている情報をよく確認して受講してください．

講義終了後の録画を見るためのURLは下記ドキュメントに記載してありますので，授業後に確認してください． ECCSアカウントでのログインが必要です．講義終了後の録画配信開始の目安は以下の通りです．

• 第1回と第13回のみ：講義終了後直後
• それ以外の回：同週に行われたコードチャレンジの終了後

https://docs.google.com/document/d/1Ks_mmScuBFOs7_3caW5ZReZIBFpyCB_Qvt5YeVcV7HA/edit?usp=sharing

講義終了後の録画はYoutubeにて共有しますので，リアルタイム配信と同じURLを使用することができます． 第1回の講義の前までに，ご登録いただいたメールアドレスにGoogle docの共有ドキュメントをお送りします．その中で動画配信のURLをお知らせしますので，確認してください．

本講義を受講する場合，以下の知識，経験，および実験機器があることを想定しています．

• 基礎的なPythonに関するプログラミング技術がある．
  • 変数の型，基本的なデータ構造（リスト，辞書），入出力，ループ，条件分岐，関数，再帰などが理解できていて，コードを書くことができるを想定しています．
  • 電子情報工学科，電気電子工学科の授業でいえば，2年生冬学期のプログラミング基礎演習，ソフトウェア1・2あたりを受講し，理解できていればOKです．
  • メタバース工学部生の方は，Python基礎を修了している，もしくは修了者と同程度かそれ以上のpythonに関する知識，経験があることを想定しています．
  • 基礎部分を補いたい方は，Pythonプログラミング入門もとても良いかと思います．
• trackでコーディングを行えるPC環境がある．OSに関しては問わない．ブラウザはChromeおよびFirefoxを推奨する．
  • https://eeic-algorithms.train.tracks.run/auth/login にアクセスし，右下にある「受験環境を確認する」を押し，すべての項目で問題なしになることを事前に確認してください．
• slackを使うことができる．講義内でアナウンスはこのホームページの他，slackでも行います．
• メタバース工学部生の方は，Googleアカウントが必要です．あらかじめ作成してください．

本講義を受講希望の方は以下のフォームより登録を行ってください．ECCSアカウントでログインしておく必要があります．また，単位習得のためにこの講義を受講する方はUTASでの登録を別途行ってください．

https://forms.gle/eYiZRVPfxM1qxA5A9

本講義を受講希望の方はメールにて事前に通知しているフォームより登録を行ってください．Googleアカウントでログインしておく必要があります．

本学学生とメタバース工学部生で成績評価方法が大きく異なります．自分に当てはまる方の評価方法をよく理解した上で受講してください．

病欠，公欠等の理由により期限内に課題が提出ができない場合，講義担当者へメールにて連絡をして，対応を相談してください．事前の相談がない場合は救済措置が難しくなる可能性があることをご承知おきください．

成績の評価は以下のように行います．

• コードチャレンジ基本課題（全24課題）：34点
• 以下の2つの課題より選択：33点
  • コードチャレンジExtra課題（全11課題）
  • レポート課題（全1課題）
  • 両方提出した場合には点数の高い方を成績に利用
• 期末試験（70〜80分程度を予定，対面で実施予定）：33点

ただし，期末試験を受験しなかった場合，この講義の成績は「未受験」という扱いになります．もし，期末試験を受験しないが成績をつけてほしい場合には，個別に期末試験前日までに連絡をしてください．（もちろん成績は総得点によりますので，連絡をしたら必ず単位が来る，ということではありません．）

修了基準は以下のとおりです．

• コードチャレンジ基本課題（全24課題，34点満点）の提出．ただし，
  • 総得点が17点以上．
  • 0点の提出（未着手のままの提出，着手したが0点の提出）が5回以下．

Extra課題は提出しなくても成績に対するペナルティはありませんが，提出された場合は0.5を乗じた上で総得点に加算することとします．例えば，基本課題で15点，Extra課題で10点を取った場合，15 + 0.5 * 10 = 20として，点数に関する修了基準を満たすことになります（提出回数に関しては別途考慮されます）．

講義は原則，対面にて行います．ただし，新型コロナウイルス感染症の拡大状況や社会情勢に応じて，形式の変更があり得ることをご承知おきください．

各回の講義は録画し，講義終了後に共有します．本学学生とメタバース工学部生で録画にアクセスできるようになるまでの時間が違いますので，講義スケジュールをご確認ください．

メタバース工学部生はリアルタイムでのオンライン配信を見て受講することも許可します．

授業中及びその後の授業内容に関する質問は，slackで行ってください．

コマンドを利用することで匿名でメッセージを送ることができます．名前を出したくない場合は，その機能を使ってください．

また，講義担当者からは授業の理解度を図るために，授業中にslackで呼びかけを行いますので，リアクションしてもらえると嬉しいです．

成績のうち約1/3は，Extra課題を毎週提出するか，以下に示すレポート課題を期限までに提出することで与えられます．レポート課題を提出した上で，Extra課題を提出している方は，より点数の高い方を成績評価に利用します．

レポート課題の具体的な内容は以下のPDFを参照してください．

https://yatani.jp/teaching/lib/exe/fetch.php?media=2023algorithms:report.pdf

レポート課題の提出にはTurnitinを利用します． Turnitinへの招待は6月末頃〜7月頭に行う予定です．

メタバース工学部生はレポート課題の提出は必要ありません．

本講義のコードチャレンジではtrackというシステムを使います．trackはオンライン上でプログラミングに関する学習を行ったり，指定された課題に対して自分のコードを提出したりすることが出来ます．またコーディング自体をブラウザ上でできるようになっているため，コーディングに必要な環境構築等を行う必要がありません．

本講義ではPython3を使用します．それ以外の言語の使用は認めません．また，track以外のシステムを用いた課題提出も認めません．

コードチャレンジには2種類あります．

• 基本課題: 講義内で紹介された擬似コードの実装や変更を行うもの．授業の内容をしっかり追えばできるようになっており，受講者のほぼ全員に出来てほしい課題．
• Extra課題：授業の内容を踏まえた発展的な課題．競技プログラミングとかにも出てくる内容を含んだ，頑張ればできる腕試し的課題．

基本課題はぜひしっかりと取り組み，解いてください．その上でExtra課題にも取り組んでもらえればと思います．Extra課題はレポート課題との選択肢気になっており，どちらか一方を提出していただければ問題ありません．Extra課題を提出した上でレポート課題を提出した場合は，より点数の高い方を成績評価に利用します．

なお，メタバース工学部生に対してもExtra課題に取り組むことはオプションとなっていますが，本学学生の場合と違う扱いとなり，提出した場合は加点対象となります（成績評価のところを参照のこと）．

本講義で利用するtrackのURLはこちらです． https://eeic-algorithms.train.tracks.run/auth/login

上記ページにアクセスし，右下にある「受験環境を確認する」を押し，すべての項目で問題なしになることを事前に確認してください．

アカウント名，初期パスワードは以下のように設定されています．

• 本学学生
  • アカウント名：ECCSアカウントのメールアドレス
  • 初期パスワード：入力していただいた学生証番号（人によっては駒場の学生証番号を入れてくださっていますのでご注意ください）
• メタバース工学部生
  • アカウント名：ご登録時に使用したGoogleアカウントのメールアドレス
  • 初期パスワード：（別途個別にメールにて連絡いたします．）

初回のログインの時点でパスワードの変更が要求されますので，より適切なパスワードに変更をしてください．

アドブロッカーなどを使用していると，ブラウザ上でうまく表示できなかったり，エラーを起こしたりすることがあります．この場合には，アドブロッカーを一時的に停止させてみてください．

trackにおけるトラブルが発生した場合は，slackにてヘルプリクエストを出してください．

コードチャレンジではいくつかのテストケースが予め設定されています．それらテストケースの通った数を元に，原則[配点]*[テストケース合格率]で点数を計算します．採点に特別な扱いがある場合には，その旨を問題文に記します．

頻繁にテストケースを実行し，デバッグを行ってください．これにより提出間際でのミスを防ぐことができる他，コードが自動保存されるので，万が一提出作業を行えなくても，最終保存されたコードを元に採点が行われます．

採点は最終提出物に対してのみ行われます．したがって，途中でどれだけミスをしていてもペナルティはありません．また，提出までにかかった時間の長短は採点に考慮されません．

Extra課題に関しては提出されたコードに対して後日類似度チェック等を行い，明らかに類似したコードがあった場合は，その全てに対してペナルティを課します．基本課題に関してはほぼ同じようなコードになるはずですので，このルールを直接は適用しませんが，類似度チェックは行います．また，指示に従った提出物になっているかのチェックも行います．

講義で使うシステムではコードをテストケースにかけた時点で，自動でバージョン管理します．コピペ等を行なった場合には，不自然にコード行数が増えたり，テストケースにパスする回数が突然増えたりするので，その辺りも必要に応じてチェックします．不自然な編集があった提出に関してはペナルティを適用することがありますので，十分気をつけてください．

与えられた基本課題においては，入出力や問題文で指示がある場合を除き，実装すべき処理において標準ライブラリや問題で指定されていない外部の関数やライブラリ等を使用しないでください． そのような提出物はテストケースに合格していても，採点されませんで注意してください．Extra課題においては，適宜外部の関数等を使っても良いものとします．

コードチャレンジの課題によってはコードの一部分（コーディング画面の初期コードとは別のコード）があらかじめ与えられている場合があります． その場合，問題文に明記してありますので，指示に従ってください．

コードチャレンジの課題を見ながら，本やWeb上の情報を参考にすることは問題ありません．ただし，記載されているコードなどをそのまま使うことのないようにしてください．また，友達同士で教え合うのも積極的に行ってください（教えることができる，というのは十分に理解できている証拠でもあります）．ただし，書いたコードを直接見せ合うのではなく，考え方だけを共有するようにしてください．

この講義で重要なのは，「自分で手を動かす」ことを大切にすることです．アルゴリズムやコーディングに自信がなくても，授業で紹介されている内容を理解し，努力すれば一定の評価につながるようになっていますので，後から誤解を招きかねない行為をしないようにお願いいたします．

提出物に対しては後日類似度チェックを行います．以下のような提出物は該当するものすべてに対して採点を取り消します．

• 提出物間でほぼ同一のコード
• Webや参考書に記載されているものとほぼ同一であることが判明したコード
• track上での課題取り組み時間（終了時刻 - 開始時刻）が極端に短い
• 与えられたテストケースに通るようにだけ設計されたコード
• その他，明らかに不正行為の証拠があるもの

悪質な場合にはより大きなペナルティになることがあります．十分気をつけてください．

コードチャレンジの締め切り後もtrack上で自分のコードにアクセスすることができますので，適宜自習に活用してください．ただし，提出期限後の変更や得点の変化は採点には反映されません．

また，Extra課題に関しては，解答例と簡単な解説をその次の講義回にて共有します．基本課題は授業のスライドにある情報で実装できるようになっていますので，授業のスライドをよく確認してください．

手元，もしくはtrack上でより細かくどのテストケースでうまく行っていないかを確認するためには以下のようなコマンドを使用すると良いです．

python3 main.py < ./test/in/basic/[入力するファイル名] | (cat ./test/out/basic/[想定出力結果のファイル名] | diff /dev/fd/3 -) 3<&0

期末試験は原則対面です．期末試験の実施方法に関しては，ここで詳細を連絡をします．

メタバース工学部生は期末試験の受験は必要ありません．

過去の期末試験は，こちらに置いてあります．自習の参考にしてください．ただし，試験時間，大問・小問の数，解答形式，出題範囲，問題の難易度などは年度により変更がある可能性があります．授業中のアナウンスを十分よく確認してください．

https://drive.google.com/drive/folders/1Coxpw6JYwA09npRfTwq-Aa_XwlRTviq8?usp=sharing

期末試験座席表はこちらのとおりです．もし，受験予定で，自分の学籍番号がない場合は，至急矢谷まで連絡をしてください．

https://drive.google.com/file/d/1Jsnom5fQ3LBl42rQR_UFSUumVrdkIELr/view?usp=sharing

以下の情報をメールにて，algorithms “at-mark” iis-lab.orgに送ってください．可能な限り事前に，事後でも速やかにお願いします．

• 病欠，公欠を希望する授業日
• 病欠，公欠の理由
• 理由が正当なものであることを裏付けるもの（診断書，処方箋，出席する学会のプログラム等のスキャンデータ，感染症に関係するホットラインへの相談記録）

認められた場合，課題提出期限をこちらが指定する日時まで延長します．

大きな怪我や病気などの例外を除き，病欠，公欠を希望する授業日から1週間以上を経過した場合は，認めないものとします．

剽窃や不適切な引用，改竄などはAcademic Misconductとして重い処分を受けます．この講義ではコードチャレンジにおける提出物や，期末試験での答案における不正行為により不当に評価を得ようとする行為に対して特に厳重に処罰します．例えば，

• インターネット上にあるライブラリやサンプルのソースコードを引用することなく用いた，
• 他人が書いたソースコードを無断かつ引用なしに転用した，
• ほかの学生が書いた回答を盗み見て利用した．
• ChatGPT等の自然言語処理サービスを利用して，コードの全部もしくは一部を生成し，利用した．

などが挙げられます．特に重大なAcademic Misconductが発見された場合，その影響度の大きさに応じて以下の罰則を与えることになります．

• 不正が見つかった課題を不採点(0点扱い，既採点の場合は採点取り消し)，
• 今までに提出されたすべての課題を不採点，
• 今までに提出されたすべての課題を不採点，かつ以降の課題提出を認めない．

レポートやソースコードは誤解の生じないように十分注意して作成・管理してください．

以下の書籍・リンクはこの講義の資料を作る際に参考にさせていただいたり，講義内容に関する大きな刺激を受けたものになります．以下に挙げているもの以外にも参考になる様々な情報がありますので，興味を持ったトピックに関して色々とご自身で調べていただければと思います．

• プログラミングコンテストチャレンジブック 第2版．秋葉拓哉，岩田陽一，北川宜稔．
• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造．渡部有隆，Ozy，秋葉拓哉．
• 新・明解Pythonで学ぶアルゴリズムとデータ構造．柴田望洋．
• 問題解決力を鍛える!アルゴリズムとデータ構造．大槻兼資，秋葉拓哉．
• 累積和を何も考えずに書けるようにする！
  • https://qiita.com/drken/items/56a6b68edef8fc605821
• 二分探索をはじめからていねいに
  • https://hcpc-hokudai.github.io/archive/algorithm_binary_search_001.pdf
• 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
  • https://qiita.com/drken/items/97e37dd6143e33a64c8c
• ソートを極める！ 〜 なぜソートを学ぶのか 〜
  • https://qiita.com/drken/items/44c60118ab3703f7727f
• 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～.
  • https://qiita.com/drken/items/a5e6fe22863b7992efdb
• プログラミングコンテストでの動的計画法
  • https://www.slideshare.net/iwiwi/ss-3578511
• Candies [Educational DP Contest / DP まとめコンテスト M]
  • https://www.hamayanhamayan.com/entry/2019/01/10/235150
• Union-Find木の解説と例題
  • https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396
• 競技プロ的なアルゴリズムのスライドのまとめ
  • https://yukicoder.me/wiki/slide
• Atcoder tags
  • https://atcoder-tags.herokuapp.com/explain
• ICPC Challenge　実践的プログラミング (全学自由研究ゼミナール)
  • http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/

またpythonの基礎の学習には様々なオンラインコースがありますので，それを活用することをおすすめします．

• https://www.python.ambitious-engineer.com/introduction-index#i-4
• https://www.python-izm.com/introduction/
• https://docs.python.org/3/
• https://www.learnpython.org/

ここでは講義中に出た講義に関係する質問とその返答を取り上げています．

• 数学2Dの演習の授業も同じ曜限に開講されていて、どちらも履修したいのですがそれは可能でしょうか？
  • 残念ながら認められません．EEICでは情報よりの興味をお持ちであれば「数学2G＋アルゴリズム」を取れるように授業が設計されていますので，ぜひご検討ください．
• 他学部，もしくは他学科の学生ですが単位取得のために講義を受講することは可能ですか？
• 大学院生ですが単位取得のために講義を受講することは可能ですか？
  • 所属する研究科，専攻に卒業要件としての単位取得が可能かどうかを確認した上で，UTASでの登録をしてください．

• スライドとは違うアルゴリズムで提出してしまったのですが減点等はありますか？
  • スライドや問題文の指定と違うアルゴリズムで提出した場合は，テストケースに通っていても採点されないことがありますので，問題文の指示をよくお読みください．
• 聞き逃したかもしれないのですが、採点結果はITC-LMSなどで見れますか？
  • 採点は[配点]*[テストケース合格率]が原則ですので，それで自分の点数がわかります．ただし，問題中で明確に指定されている要件を満たしていない場合，採点が取り消される，あるいは減点となります．
• 採点のフィードバックはありますか
  • 私達からの個別のフィードバックはこの講義のサイズでは難しいので，テストケースに通ったかどうかが一応のフィードバックになるようにしてます．
• 課題を終えるまでにかかった時間は評価に入りますか？
  • 考慮しません．
• 翌週に模範解答的なものは公開されますか
  • はい．Extra課題に関しては公開予定です．
• 課題についてWEB上のコードを参照して、そっくりじゃなくても似ているコードはいけませんか？
  • 自分自身で咀嚼した上で書いたコードだと判断してよいと第三者が見て言えるレベルにしてもらえればと思います．
• dequeやheapqなどは使用しない方が良いということでしょうか？
  • 基本課題ではその類のものは原則使用できません（ただし，別途指示がある場合を除く）．またExtra課題であっても，既存のライブラリの効率性に依存する提出（もしそのライブラリを使わないコードに書き換えた場合，テストケースに通らないことが容易に予想される提出物）は減点の対象となります．

• ネットワーク接続（コンテンツサーバー）の異常で受験できません
  • adblock解除で接続できた報告がありましたので，試してみてください．それでもエラーが出る場合はこちらに連絡をください．
• テスト実行で一度保存すればブラウザを一度閉じてもコードが保存されるということでしょうか
  • はい．そうです．不安ならローカルにコピーしておいてください．
• SyntaxError: Non-ASCII character ‘\xe3’ in file main.py on line 4, but no encoding declared というエラーが出る
  • どこかに日本語が入っているためだと考えられます． # coding: UTF-8を入れるといけるはずです．
• 「解答を完了」したあと、「試験を提出する」を押さないと、採点されなかったりますか？前回は「試験を提出する」を押し忘れたようなきがするのですが
  • 期限が来ると自動で提出はされますが，押してもらうほうが確実です．
• デフォルトで書いてあるコードは、特に気にしなくていいものですか？それとも理解しないといけない内容が書かれていますか？
  • 気にしなくてよいです．このコードを利用せずに提出しても問題ありません．
• sys.stdin やdefを使わずに、inputなどだけを用いて提出したのですが(テストケースには正解)、それでもよかったでしょうか
  • 問題ありません．デフォルトのテンプレートを消した上で，提出してもらって問題ありません．
• Ctrl+sでテスト実行されました
  • こちらも便利ですね！
• 後から復習できるようにtrack上の問題文をローカルに保存する方法はありますか？
  • とりあえずwebページをPDFとかに保存してもらえればと思います．（何かしらの方法で公開できないか検討中）
• コードを初めからやり直したいときにリセットする方法はありますか？
  • 右上の歯車のところにテスト環境を初期化というボタンがあります．

• Command terminated by Signal 9というエラーが出ます．
  • 多くの場合，メモリ制限に引っかかっているものと考えられます．どこか効率的でないメモリの使い方をしていないか，確認してみてください．
• Command terminated by Signal 11というエラーが出ます．
  • もし再帰を使っている場合は，以下のようにして再帰回数の上限とスタック領域を拡大してみてください．

import sys

import resource

resource.setrlimit(resource.RLIMIT_STACK, (-1, -1)) # スタック領域を拡大

sys.setrecursionlimit(1000000) # 再帰回数の上限を拡大

• テストケースが多すぎてどのような誤りがあるか確認できません．
  • 以下のコマンドをプロンプト（trackの右下のコンソールの一番下のところ）に入れると，想定出力と出力が違っている行が出力されます．

python3 main.py < ./test/in/basic/[入力するファイル名] | (cat ./test/out/basic/[想定出力結果のファイル名] | diff /dev/fd/3 -) 3<&0