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

CS5310 - Algorithms                                     

Time & Place: T Th 04:00pm-05:40pm, C0227 CEAS,
Call Numbers: 15555 and 11429, 3 credit hours

This is one of the foundation courses required for computer science masters degree starting Fall 2014. Check the details of foundation courses at

https://www.cs.wmich.edu/wp-content/themes/wmu/docs/Three_Foundational_Courses_For_New_MS-CS_Program_Effective_Fall2014.pdf

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 advanced undergraduate and beginning graduate 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 presented or discussed in class.

Required Text

Algorithm Design: Foundations, Analysis and Internet Examples by Michael Goodrich and Roberto Tammassia, Wiley, ISBN: 978-0-471-38365-9

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 last semester may suffice for you, if you can copy problems sets needed in homeworks from one of your colleagues who has purchased the required texbook.

Course Learning Outcomes

  • Reinforce analytic development and problem solving abilities, and develop a 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 2014, in pdf

Topics Covered in Spring 2014