Introduction to Graph Algorithms
Offered By: Indian Institute of Science Bangalore via Swayam
Course Description
Overview
Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
ABOUT THE COURSE: A Computer is basically an information processing system and this means it can be used for solving only abstract mathematical problems. That is why, solving a Real World Problem (RWP) by using a computer, begins with a formulation of the RWP as a Mathematical problem in an appropriate mathematical domain. For example, privacy and security problems are formulated as cryptographic problems in Number Theory, Elliptic Curves and Linear Algebra.Mathematical domains such as combinatorics, Geometry, Sets and Relations, Number Theory, Stringology and Graph Theory are among most frequently used domains to arrive at mathematical problems that are equivalent to the real-world problems.In this course we focus on basic graph algorithms. Problems arising in communication networks, social networks and transportation networks are naturally modelled as problems on graphs. Graph algorithms are among the extensively investigated and applied topics in computer science. INTENDED AUDIENCE: UG/PG StudentsPREREQUISITES: Discrete Mathematics, Graph Theory, Basics of Programming and Data StructuresINDUSTRY SUPPORT: Infosys, TCS, MSR
Syllabus
Week 1: Principles of algorithms
Week 2:Introduction to directed and undirected graphs
Week 3:DAGs and incremental algorithms
Week 4:DFS, BFS of directed and undirected graph
Week 5:Application of DFS – cut vertices/bridges of a graph
Week 6:MST
Week 8:APSP
Week 2:Introduction to directed and undirected graphs
Week 3:DAGs and incremental algorithms
Week 4:DFS, BFS of directed and undirected graph
Week 5:Application of DFS – cut vertices/bridges of a graph
Week 6:MST
- Incremental greedy template
- Krushkals algorithms and partition ADT
- PRIMS algorithm and Fibonacci Heaps
Week 8:APSP
Taught by
Prof. C. Pandu Rangan
Tags
Related Courses
Algorithmic Thinking (Part 1)Rice University via Coursera Graph Search, Shortest Paths, and Data Structures
Stanford University via Coursera Algorithms on Graphs
University of California, San Diego via Coursera 算法基础 | Fundamental Algorithms
Peking University via edX Graph Algorithms
University of California, San Diego via edX