[Teaching home]

ELL781: Software Fundamentals for Computer Technology

If you're doing the course, please join the Piazza forum (the access code will be 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 2022–23
Tu W F 8:00–9:00, LH 606

Evaluation components

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–19 See here SDR
20–22 Mid-course overview: From Problems to Programs AHU Chapter 1 SA
23–24 Algorithm Design: Greedy algorithms—optimal substructure and greedy-choice property AHU Chapter 10; Greedy algorithms and minimum spanning tree notes SA
25–28 Undirected graphs: Minimum spanning trees—Prim's and Kruskal's algorithms AHU Chapters 5, 7; Greedy algorithms and minimum spanning tree notes SA
29–33 Network flows: Flow networks, Maximum flow, Ford-Fulkerson algorithm, Edmonds-Karp algorithm CLRS Chapter 26 SA
34–38 NP-completeness CLRS Chapter 34 SA
39 Approximation algorithms CLRS Chapter 35 SA

[Teaching home]