CS 4310 (Spring 2024)

  
 

Design and Analysis of Algorithms

  

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

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

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