CMPE 300 ANALYSIS OF ALGORITHMS SPRING
2005
Instructor: Assoc. Prof. Fatih Alagöz
Assistant: Ömer Korçak
Text Book: Fundamentals of Sequential and Parallel Algorithms
Kenneth A.Berman,
Jerome L.Paul, PWS Publishing Company, 1997
Reference Books:
·
Introduction
to the Design and Analysis of Algorithms
Anany Levitin, Addison Wesley Pub., 2003
·
Analysis
of Algorithms: An Active Learning Approach
Jeffrey J.McConnell,
Jones and
·
Algorithms
Sequential & Parallel, A Unified Approach
Russ Miller, Laurence Boxer,
Prentice-Hall Inc., 2000
·
Algorithms
and Complexity
Herbert S.Wilf,
Prentice-Hall Inc., 1986
Lecture
Hours and Rooms:
Monday
Tuesday
PS: Thursday 14:00-15:00 ETA
409
Course
Schedule:
Introduction
Algorithm complexity
(Best-case, Worst-case, Average complexity)
Asymptotic analysis (Growth
rate, Aymptotic notation, Comparison of growth rates)
Analysis of example algorithms
Interpolation (?-invariant
under scaling, Scale invariant classes)
Stable, in-place, on-line
algorithms
Adjacent-key comparison-based
algorithms
Recurrence
relations (Forward and Backward substitutions, Change of variable, Generating func.)
Master Theorem
Lower bound theory
Parallel architectures (Shared
memory, Distributed memory)
Parallel algorithms (Analysis,
Goodness measures, Evaluation)
Correctness for parallel
algorithms (0/1 sorting lemma)
Numeric algorithms (Parallel prefix,
Matrix multiplication, Parallel matrix multiplication, Fast fourier transform)
Graph algorithms (Depth-first
search and traversal, Breadth-first search and traversal, Matching)
Probabilistic
algorithms (Monte Carlo algorithms,
Evaluation: (subject to
change)
Midterm: 20 %
Projects: 20 % (10%
project, 10% presentation)
Assignments & Quizes : 20 %
Final: 40 %
Notes:
·
There
will be a research project and a programming project.
·
The midterm
and final examinations will be closed books and notes.
· Attendance for
lectures is mandatory.