Other links:
Other links:
Ashoka University’s undergraduate course curriculum is taught across three semesters: Spring, Summer and Monsoon (Fall). Courses are broadly divided into three categories – Foundation Courses (core curriculum), Major & Minor Courses and Co-Curricular Courses.
You may search courses offered at Ashoka here. Please use the drop down menu to choose the specific semester and subject to see the full list of courses under each department. Foundation courses are offered in all semesters and do not have prerequisites. Offerings in other categories differ in each semester. Some higher level major/minor courses may have prerequisites.
To view Summer Semester Courses-2024: Click here
Course Objective: To equip the students with the necessary skills and knowledge to understand, analyze graph algorithms which are extensively studied and applied in a plethora of domains such as networks for transportation, communication and social media as well as design automation for integrated circuits (ICs).
Coverage:
Flows in Networks: Basic concepts, maxflow-mincut theorem, Ford and Fulkerson augmenting path method, integral flow theorem, maximum capacity augmentation, Edmond-Karp method, Dinic’s method and its analysis, Malhotra-Kumar-Maheswari method and its analysis, Preflow-push method (Goldberg Tarjan) and its analysis; Better time bounds for simple networks. Minimum cost flow: Minimum cost augmentation and its analysis.
Matching problems: Basic concepts, bipartite matching – Edmond’s blossom shrinking algorithm and its analysis.
Planarity: Basic facts about planarity, polynomial time algorithm; polynomial time algorithm for planar graphs
Graph isomorphism: Importance of the problem, backtrack algorithm and its complexity
NP-hard optimization problems in graphs: minimum vertex cover, maximum clique, maximum independent set, TSP, chromatic number etc; approximation algorithms and classification of NP-optimization problems with respect to approximability.
