ELL781: Software Fundamentals for Computer Technology

Instructors: Sumantra Dutta Roy (SDR) and Sandeep Kumar (SK)

3 credits (3-0-0)Pre-requisites: COL 106Semester I: 2020-2021Classes: Tue-Wed-Fri 8:00 am -9:00 am online (MS Teams)

The course is to be jointly taught by Prof. Sumantra Dutta Roy and Sandeep Kumar. This page houses the part to be covered by the second instructor, Sandeep. The course will focus on aspects of applied algorithmic design principles useful for electrical and computer science engineers.

Evaluation: Scribing (5%), Assignments (15%), Course Project (15%), and End Exam (15%).

Textbooks:

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (CLRS). MIT Press, 3rd Edition, 2009.

Select References:

  1. Mark de Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars, Computational Geometry. Springer, 1997.

  2. Vijay V. Vazirani. Approximation Algorithms (VV). Springer Science & Business Media, 2013.

  3. Nancy A. Lynch, Distributed Algorithms. Elsevier, 1996.

  4. Stephen P. Boyd, and Lieven Vandenberghe. Convex Optimization (BV). Cambridge university press, 2004.

  5. Michael R. Garey and David S. Johnson. Computers and Intractability (GJ). Vol. 174. San Francisco: freeman, 1979.

Tentative Lecture Plan:

  • Lecture 1: Logistics required for the second part of the course and graph preliminaries

  • Lecture 2: Graph traversal algorithm; BFS

  • Lecture 3: Graph traversal algorithm; DFS

  • Lecture 4: DFS applications

  • Lecture 5: Greedy algorithms; optimal substructure and greedy choice property

  • Lecture 6: Minimum Spanning Tree; Prim's and Kruskal algorithm

  • Lecture 7: Shortest path algorithm; analysis of Bellman-Ford algorithm

  • Lecture 8: Network flows; Flow networks, Maximum flow

  • Lecture 9: Ford-Fulkerson algorithm and Edmonds-Karp algorithm

  • Lecture 10: Linear programming 1

  • Lecture 11: Linear Programming 2

  • Lecture 12: Algorithm design as optimization problem

  • Lecture 13: Computational geometry; line segment, convex hull and projection algorithms

  • Lecture 14: Computational geometry: Voronoi diagram

  • Lecture 15: Distributed algorithms

  • Lecture 16: Approximation algorithms I

  • Lecture 17: Approximation algorithms II

  • Lecture 18: Complexity Theory