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 UnionFind, + exercises) Final exam: June 28, 2022 (syllabus: comprehensive  all slide sets through VIII and all additional material covered, + exercises)
Instructor
Dr. Elise deDoncker
WMU Parkview campus
Engineering Bldg. 2nd floor, B240
Phone: 2763102 (office), 2763101 (Dept. office)
(but preferably contact me by email: elise [dot] dedoncker [at] wmich [dot] edu)
webex link: https://wmich [dot] webex [dot] com/meet/elise [dot] dedoncker
Office hours
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
Texts
(best to get the most recent version)
Required:
Foundations of Algorithms, R.E. Neapolitan (5th edition, ISBN 9781284049190)
Computer Algorithms/C++, E. Horowitz, S. Sahni and S. Rajasekaran
(2nd edition, ISBN 0716783150)
Recommended:
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: divideandconquer, the greedy method, dynamic programming,
backtracking, and branchandbound 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:
DivideandConquer: quicksort, merge sort, selection, Strassen's
matrix multiplication;
Greedy Method: "fractional" knapsack problem, min. cost spanning
trees, optimal merge patterns (applied to Huffman codes), single source
shortest paths;
Dynamic Programming: all pairs shortest paths, 0/1 knapsack,
traveling salesman (TSP);
Backtracking: nqueens problem, Hamiltonian cycles;
Branchandbound: job scheduling, TSP.
Furthermore, (if time permits)
an introduction will be given to NPhard and NPcomplete 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
algorithm complexity.
Computer Usage
Highlevel languages will be used to implement the programming requirements of assignments and projects.
Learning outcomes
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
practical performance.
The students will study and apply the algorithm paradigms and complexity properties studied in this course to design and implement 'practical' programming
solutions to nontrivial and sizeable problems.
Useful link
