CS 4310-5310 (Summer I 2022)

 
 

Design and Analysis of Algorithms

 

[ Courses ] [ syllabus ] [ class policy ] [ references ] [ projects ] [ assignments ]

   

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)

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
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 0-7167-8315-0)

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: 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 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, (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 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

    [ Courses ] [ syllabus ] [ class policy ] [ references ] [ projects ] [ assignments ]