Exam I: May 26, 2022 (syllabus: material covered through 05/19/22,
corresponding to first three sets of slides, + exercises)
Exam II: June 14, 2022 (syllabus: corresponding to slide sets IV, V, VI,
and additional material covered including Union-Find, + exercises)
Final exam: June 28, 2022 (syllabus: comprehensive - all slide sets through VIII
and all additional material covered, + exercises)
Dr. Elise deDoncker
WMU Parkview campus
Engineering Bldg. 2nd floor, B-240
Phone: 276-3102 (office), 276-3101 (Dept. office)
(but preferably contact me by e-mail: elise [dot] dedoncker [at] wmich [dot] edu)
webex link: https://wmich [dot] webex [dot] com/meet/elise [dot] dedoncker
Tuesday at 13:00
(after class), or by appointment (let me know if/when
you are coming).
TA: Irene Kahvazadeh, irene [dot] kahvazadeh [at] wmich [dot] edu
(best to get the most recent version)
Foundations of Algorithms, R.E. Neapolitan (5th edition, ISBN 9781284049190)
Computer Algorithms/C++, E. Horowitz, S. Sahni and S. Rajasekaran
(2nd edition, ISBN 0-7167-8315-0)
Algorithmics, G. Brassard and P. Bratley
See also References
Course Contents and Goals
The course will introduce the students to the main algorithm paradigms
or classes: divide-and-conquer, the greedy method, dynamic programming,
backtracking, and branch-and-bound techniques.
Tools needed to allow for proper performance analysis of the algorithms
will be covered initially (asymptotic notation, time and space
complexity, solving of recurrence relations - the latter using, e.g.,
expansion or the characteristic equation of the recurrence relation).
Within each of the paradigms,
algorithms will be studied to solve typical problems. These include:
Divide-and-Conquer: quicksort, merge sort, selection, Strassen's
Greedy Method: "fractional" knapsack problem, min. cost spanning
trees, optimal merge patterns (applied to Huffman codes), single source
Dynamic Programming: all pairs shortest paths, 0/1 knapsack,
traveling salesman (TSP);
Backtracking: n-queens problem, Hamiltonian cycles;
Branch-and-bound: job scheduling, TSP.
Furthermore, (if time permits)
an introduction will be given to NP-hard and NP-complete problems,
again illustrated by typical problems.
The goals of the course thus include: to familiarize the students with
the various algorithm paradigms, particularly those commonly used to
tackle "hard" problems; to give the students the necessary
background for algorithm analysis, so that they will be able to compare
theoretical with experimental findings (the latter being exercised in
suitable assignments); and introduce the students to the theory of
High-level languages will be used to implement the programming requirements of assignments and projects.
The students will use mathematical techniques and concepts such as proof techniques
by induction and by contradiction, and solution methods for recurrence relations
to aid in the analysis of algorithms.
The students will understand relationships between theoretical complexity results and
The students will study and apply the algorithm paradigms and complexity properties studied in this course to design and implement 'practical' programming
solutions to non-trivial and sizeable problems.