Time: 11:20 - 12:45, Tuesday and 11:20 - 12:45, Thursday

Room: 203 Dunn Hall

Instructor: Robert Kozma

Asymptotic behavior of programs, basic paradigms in algorithm design: divide-and-conquer, greedy, backtracking, dynamic programming. Analysis of efficiency and optimality of representative algorithms, including graph, pattern matching, numerical, randomized, and approximation algorithms. Approaches to lower bound analysis. Basics of NP completeness, parallelism and connectionism. PREREQUISITE COMP 2150.

Evaluation will be viewed as a continuous two-sided feedback process, which (a) allows students to assess themselves about their progress in learning the material/understanding the issues; and (b) allows the instructor to assess how well he is fostering the communication process with and among students. Students are expected to automatically read relevant chapters in the textbook and the supplementary references as indicated in the syllabus before the corresponding topics are discussed in class. Further reading assignments will also be announced at least two lectures in advance. After completing this course, students are expected to be familiar with the introduced major algorithms and concepts and able to use and evaluate them in problems related to design of algorithms.

15%: Class Participation

25%: Homeworks (5x)

15%: Midterm test (Oct. 31)

45%: Project parts:

5%: Proposal (due Oct.12);

20%: Written part (due Dec. 5);

20%: Presentations (Nov. 28, 30, Dec. 5).

Homeworks: All homeworks are due on the given day (9/12, 9/26, 10/17, 10/31, 11/14) at the start of the class.

August 29 Orientation

August 31 Introduction, overview

September 5 Recursion, Induction

September 7 Sorting 1

September 12 Sorting 2

September 14 Sorting 3

September 19 Searching 1

September 21 Searching 1

September 26 Graphs, optimization

September 28 Graphs and backtracking

October 3 Greedy Algorithm

October 5 Transitive closure

--- Fall Break ---

October 12 Dynamic programming 1

October 17 Dynamic programming 2

October 19 Dynamic programming 3

October 24 String matching

October 26 Polynomials and matrices

October 31 Complexity

November 2 NP completeness 1

November 7 Knapsack problem, traveling salesman problem

November 9 Parallel Algorithms

November 14 Connectionism, algorithmic

November 16 Connectionism and intelligence

November 21 Holiday: Thanksgiving

November 23 Project overview

November 28 Project presentations 1

November 30 Project presentations 2

December 5 Project presentations 3

S. Baase & A. Van Gelden, Computer Algorithms - Introduction to Design & Analyis, Addison-Wesley, 2000, 3^rd Edition

T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Analysis of Algorithms, The MIT Press/McGraw Hill, 1990.

F. Harary, Graph Theory, Addison Wesley, 1972.

R.E. Bellman, S.E. Dreyfus, Applied Dynamic Programming, Princeton University Press, 1962.

G.L. Nemhauser, Introduction to Dynamic Programming, John Wiley & Sons, 1966.

Algorithmica

Journal of Algorithms

Journal of Experimental Algorithms

Journal of the ACM

See instructor about these during the course