Syllabus

Fundamental Computer Concepts of Informatics

I500 - Fall 2008 (Section # 13877)

Class Meets

Time: Tuesday and Thursday 11:15am-12:30pm

Place: I2 122

Lab Section Meets

Time: Friday 2:30pm-3:20pm

Place: GR 102A

Instructor

Predrag Radivojac

Office: Informatics 219

Email:.predrag@indiana.edu.

Web: http://www.informatics.indiana.edu/predrag

Associate Instructor

Amrita Mohan

Office: Informatics 207

Email:.ammohan@indiana.edu.

Office Hours

(theory) Tuesday/Thursday 1pm-2pm or by appointment

(lab) Wednesday 11am-12:30pm or by appointment

Course Objective

The course objective is to study principles underlying efficient algorithms and their analysis. A significant portion of the course will be devoted to programming in Matlab. No prior programming experience is expected.

Prerequisites

Graduate student standing or permission of the instructor.

Textbooks

Required

Introduction to Algorithms, 2^nd ed. - by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press, 2001 (available online at IUCAT!!!).

Recommended

Machines, Languages, and Computation - by Peter J. Denning, Jack B. Dennis, and Joseph E. Qualitz, Prentice-Hall, 1978.

Supplementary material will be provided in class.

Topics

▪  mathematical foundations of algorithms

▫  growth of functions

▫  summations

▫  recurrences

▫  counting and probability

▪  data structures

▫  elementary data structures

▫  hash tables

▫  binary search trees

▪  sorting and order statistics

▫  heapsort

▫  quicksort

▫  medians and order statistics

▪  strings and languages

▫  hierarchy of formal languages

▫  formal grammars

▫  probabilistic grammars

▪  advanced design techniques

▫  dynamic programming

▫  greedy algorithms

▪  graph algorithms

▫  elementary graph algorithms

▫  minimum spanning trees

▫  shortest path problems

▪  special topics

▫  matrix operations

▫  string matching algorithms

▫  computational geometry

▫  NP-completeness

Grading

Midterm exam: 20%

Final exam: 20%

Homework assignments: 50%

Class participation: 10%

Late Policy and Academic Honesty

The homework assignments are due in class, on the specified due date. No late assignments will be accepted unless there are legitimate circumstances. All assignments are individual, except when collaboration is explicitly allowed. All the sources used for problem solution must be acknowledged, e.g. web sites, books, research papers, personal communication with people, etc. Academic honesty is taken seriously; for detailed information see Indiana University Code of Student Rights, Responsibilities, and Conduct.

Last updated: 08/24/2008