Ajay

Ajay Gupta
Professor

IEEE-CS TAC Vice-Chair (2022-24)
IEEE-CS TMRC Member (2013 - )
IEEE-CS TAC Vice-Chair (2015-16)
IEEE-CS TCPP Chair (2011-2015)

Director, WiSe Lab

Western Michigan University
Dept. of Computer Science
Mail Stop 5466
4601 Campus Drive
Kalamazoo, MI, 49008-5466


Phone: 269-276-3101 / 3104
Fax: 269-276-3122
E-Mail: ajay dot gupta at wmich dot edu

CS4310-5310 - Design and Analysis of Algorithms                                    

Time & Place: T Th 11:30-12:45pm, CEAS D0208+D0210 / D0109+D0115 Floyd Hall, Hybrid Instruction Delivery (Face-Face and Synchronous),
CRNs: 12840 and 15932, 3 credit hours

This course can satisfy one of the foundation courses required for computer science masters degree for the WMU-CS undergraduate students continuing their graduate studies. Check the details of foundation courses at

https://wmich.edu/cs/academics/graduate/ms-program

Prerequisites:

By Courses: (MATH 1450 or CS1310) and CS3310 or equivalent with a grade of C or better; or permission of the instructor.

By Topic: Advance understanding of high-level language programming - conditional structures; looping structures; arrays; program logic - to solve problems; object oriented programming - be able to create and use objects; software life cycle; validating quality of software produced; introductory sorting and searching algorithms; elementary data structures (linked lists, queues, stacks, hash maps); documenting programs effectively and efficiently; team work.

This is an exciting but challenging course basic, fundamental and foundational to computer science. This course is a continuation of the study of data structures and algorithms, emphasizing methods useful in practice. It provides a theoretical foundation in designing algorithms as well as their efficient implementations. The focus is on the advanced analysis of algorithms and on how the selections of different data structures affect the performance of algorithms. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; backtracking; branch-and-bound; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; and parallel computing.


The course is appropriate for seniors and beginning graduate students.  Like most college courses, this course requires students to take responsibility for their own learning.  The course follows a strict schedule of reading, writing, and quizzes.  Each week reading will cover one or two chapters of the textbook.  The reading, writing, and examination schedule is firm.  Students are required to develop the discipline to follow the schedule.


As is typical of many college courses, this course will require two midterm examinations during the course and a number of quizzes.
Classroom activities, unlike the readings and quizzes, are somewhat less structured.  This allows for tangents in discussions, the use of occasional visiting guests, unforeseen instructor absences, holidays, etc.  The flexibility of the classroom does not tie students or instructor to the textbook readings, but does complement and enhance those readings.  Students are responsible for material in the textbook, whether or not the material is addressed in the classroom.  Students are also responsible for material and skills mentoned, presented or discussed in class.

Required Text

Algorithm Design and Applications by Michael Goodrich and Roberto Tamassia, Oct 2014, Wiley, ISBN - 978-1-118-33591-8.

We will also be using Shaffer's Data Structures and Algorithms book - the link is to an older version, we will provide you an online interactive latest version on Canvas

Notes - Summation and Recurrence Relations.

Optional Texts:

A number of textbooks (in addition to GT's book) on algorithm design appropriate for this course have been published. The course will cover material from these books as well as material from research papers.

The book "Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, ISBN-10: 032157351X, ISBN-13: 978-0321573513" used in previous semesters may suffice for you, if you can copy problems sets needed in homeworks from one of your colleagues who has purchased the required texbook.

The book "Algorithm Design: Foundations, Analysis and Internet Examples by Michael Goodrich and Roberto Tammassia, Wiley, ISBN: 978-0-471-38365-9" may also suffice, if you can copy problems sets needed in homeworks from one of your colleagues who has purchased the required texbook.

Introduction to Algorithms (3rd ed.) by Cormen, Thomas H.Leiserson, Charles E.Rivest, Ronald L.Stein, Clifford (2009) [1990].  MIT Press and McGraw-Hill. ISBN 0-262-03384-4 is a good reference book to have. Read about it in its wiki page

Course Learning Outcomes

  • Reinforce analytic development and problem solving abilities, and develop a deeper foundation in computer science.
  • Show progress with regard to understanding the analysis and performance of algorithms (for further use, e.g., in graduate level courses), including knowledge and use of terminology and how the theory connects with real-world applications, possibly in different and new areas.
  • Apply the concepts covered in the course to written and practical problems, e.g., by combining problem solving with computer programming and the use of software tools as part of assignments.
  • Students who earn a “C” or better in this course should have knowledge of
    • Sequential algorithms pertaining to the greedy, divide-and-conquer, dynamic programming, backtracking and branch-and-bound paradigms;
    • Parallel algorithms pertaining to SIMD, MIMD, shared memory and message passing systems;
    • Introductory databases and data management applications;
    • Analyzing iterative and recursive sequential and parallel algorithms;
    • Efficient data structures such as AVL trees, 2-3 trees, min-max heaps, B-trees.

QuickLinks

Syllabus for Spring 2021

Topics Covered in Spring 2021

Useful Links - from CS3310 etc.