|
Instructor
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
Office hours
T 13:30 - 14:30,
or by appointment (let me know if/when you are coming).
TA: TBD
Grader
Michael Loh, michaeljiahui.loh@wmich.edu
Texts
(best to get the most recent version)
Required:
Foundations of Algorithms, R.E. Neapolitan (5th edition, ISBN 9781284049190)
Computer Algorithms, E. Horowitz, S. Sahni and S. Rajasekaran
(2nd edition, ISBN 0-7167-8316-9)
Course Contents and Goals
The course will introduce the students to the main algorithm paradigms
or classes: divide-and-conquer, greedy methods, 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
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: n-queens problem, Hamiltonian cycles;
Branch-and-bound: job scheduling, TSP.
Furthermore,
an introduction will be given to NP-hard and NP-complete problems,
again illustrated by typical problems.
In addition, some data structure topics may be covered, including
B-trees and 2-3 search trees (if this was not offered in the CS 3310
prerequisite), and sets and disjoint set union (for an efficient
implementation of Kruskal's algorithm).
The goals of the course thus include: to familiarize the students with
the various algorithm paradigms, including methods 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
High-level 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 non-trivial and sizeable problems.
Useful link
|