Sandeep Kumar - ELL 781 Software Fundamental for CTech

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:

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

Select References:

Mark de Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars, Computational Geometry. Springer, 1997.
Vijay V. Vazirani. Approximation Algorithms (VV). Springer Science & Business Media, 2013.
Nancy A. Lynch, Distributed Algorithms. Elsevier, 1996.
Stephen P. Boyd, and Lieven Vandenberghe. Convex Optimization (BV). Cambridge university press, 2004.
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