[Teaching home]

ELL781: Software Fundamentals for Computer Technology

If you're doing the course, please join the Piazza forum (the access code has been announced in class and e-mailed to you).

Instructors: Sumantra Dutta Roy (SDR) and Sumeet Agarwal (SA)
3 credits (3-0-0)
Pre-requisites: COL106
I Semester 2021–22
Tu W F 8:00–9:00, Microsoft Teams

Evaluation components

Audit criteria

30% for audit pass as per Institute rules.

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms (AHU). Addison-Wesley, 1983.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (CLRS). MIT Press, 3rd Edition, 2009.

Planned outline

Class(es) Topics References Instructor
1–18 See here SDR
19–21 Mid-course overview: From Problems to Programs AHU Chapter 1 SA
22–23 Algorithm Design: Greedy algorithms—optimal substructure and greedy-choice property AHU Chapter 10; Greedy algorithms and minimum spanning tree notes SA
23–27 Undirected graphs: Minimum spanning trees—Prim's and Kruskal's algorithms AHU Chapters 5, 7; Greedy algorithms and minimum spanning tree notes SA
28–32 Network flows: Flow networks, Maximum flow, Ford-Fulkerson algorithm, Edmonds-Karp algorithm CLRS Chapter 26 SA
33–35 NP-completeness CLRS Chapter 34 SA
36 Approximation algorithms CLRS Chapter 35 SA

[Teaching home]