Algorithm Theory

(アルゴリズム論)

Lecture time and location:

Friday, 240pm-4:10pm, Lecture Room 7 of Mechaniacl Engineering Department

Instructors		Hiroaki Kobayashi	Taira Nakajima
Contact Info.	Office	4th Floor, Information Synergy Center Main Building	Room 301, Mechanical Enginnering Building 2
	Phone	022-217-3415	022-217-4100
	Fax	022-217-6096	022-217-7015
	E-mail	koba@isc.tohoku.ac.jp	nakag@fractral.is.tohoku.ac.jp

Syllabus:

• Basic Data Structures (by Nakajima)
• Statistical Representation of Data (by Nakajima)
• Data Modeling (by Nakajima)
• Monte Carlo Simulations (by Nakajima)
• Random Number and its Application to Encryption (by Nakajima)
• Genetic Algorithms (by Nakajima)
• Neural Networks (by Nakajima)

• Algorithm Analysis (by Kobayashi)
• Search Algorithms (by Kobayashi)
• Sorting Algorithms (by Kobayashi)
• Graph Algorithms (by Kobayashi)
• Strategies for Algorithm Design (by Kobayashi)
• Network Problems (by Kobayashi)
• Design of Parallel Algorithms (by Kobayashi)
  

Grading Policy

Evaluated based on the home assignments presented below!

Reference Texts

• Algorithm Design: Foundations, Analysis, and Internet Examples
  Michael T. Goodrich and Roberto Tamassia
  John Wiley & Sons, Inc.
  ISBN: 0-471-38365-1

• NUMERICAL RECIPES in C(日本語版）
  W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery
  丹慶 勝市，奥村 晴彦，佐藤 俊郎，小林 誠 (訳）
  技術評論社
  ISBN: 4-87408-560-1

Announcement:

レポート課題　（レポートで評価を行い、筆答試験は行いません）

１）講義で取り上げられた様々なアルゴリズムのうち，自分が興味を持ったアルゴリズムに関する論文を探して(英文,8ページ以上)読み，その内容をA4紙4ページ程度にまとめて提出すること．レポートの言語は英語，または日本語とする．

２）1月24日配布資料のスライド12に示されるadjacency list structureを適当なプログラム言語を用いて定義せよ。次に、社会においてグラフ表現可能なもの（インターネット、電話、、高速道路、鉄道路線など）をグラフを用いて表現し、任意の2点間の経路を求めるアルゴリズムをプログラムせよ。ただし、複数の経路が存在する場合に、すべての経路を探索できるようにすること。レポートとして、アルゴリズム、プログラムリスト、実行データ、実行結果、考察、たとえば、アルゴリズム＆プログラム設計において工夫した点（アルゴリズムの動作の可視化、アルゴリズムの高速化、効率化など。評価の加点要素となります）、その結果への影響等、をまとめること。

提出場所: 機械系2号館301 中島講師室
提出期限: 2/17(月) 17:00 (厳守)
連絡先: nakag@fractal.is.tohoku.ac.jp

Q&A Bulletin Board

Handouts in PDF

If you do not have acrobat reader、 please click here.

• 0. Lecture's overview(10/4/02, by Kobayashi)
• 1. Elementary Data Structures (10/04/02, by Nakajima)
• 2. Elementary Data Structures 2 (10/11/02, by Nakajima)
• 3.Data Modeling (10/18/02, by Nakajima)
  • Reading: Numerical recipes in C(ISBN4-87408-560-1), Chapter 7
• 4.Numerical recipes in C(ISBN4-87408-560-1), Chapter 7
  • Reading: Numerical recipes in C, Chapter 13
• 11/1 No Class
• Monte Carlo Simulations (11/8/02, by Nakajima)
  • Reading: An Introduction to the Kalman Filter
• RSA cryptography (11/15/02, by Nakajima)
• 7. Machine learning (10/22/02, by Nakajima)
  • Reading: Self-Organizing maps(ISBN3-540-62017-6), Chapter 1, 3
• Machine learning 2(10/29/02, by Nakajima)
  • Reading: Reinforcement Learning(ISBN4-627-82661-3), Chapter 1,6
• 12/6 No Class
• 9. Analysis of Computer Algorithms (12/13/02, by Kobayashi)
• 10. Search Trees (12/20/02, by Kobayashi)
• 11. Sorting (1/10/03, by Kobayashi)
• 12. Sorting (1/17/03, by Kobayashi)
• 13. Graphs (1/24/03, by Kobayashi)
• 14. Graph Algorithms (1/31/03, by Kobayashi)