E0 251-O Data Structures and Graph Analytics 3:1 (January 2023)

Course Instructor: Dr. Viraj Kumar

Objective: Graph Analytics is important in different domains: Social Networks, Computer Networks, and Computational Biology to name a few. This course deals with the data structures and algorithms underlying Graph Analytics. Important applications will also be considered. Students will be given several programming assignments and a mini project to make them appreciate the contents of the course. Python will be the programming language of implementation for the assignments and the mini project.

Syllabus

Overview of basic data structures such as arrays, linked lists, stacks, and queues. Trees: binary trees and their traversals, binary search trees, balanced trees, and game trees. Priority queues and heaps. Dictionaries and hash tables. Sorting techniques: bubblesort, quicksort, mergesort and decision trees. Algorithm design paradigms: back-tracking, divide and conquer, dynamic programming, and greedy. Graph analytics: depth-first and breadth-first search, connected components and spanning trees, shortest path computation, minimum spanning tree computation, graph matching, network flows, centrality computation, community detection, and connection analysis. Bulk-Synchronous-Parallel model of computation and application to parallel graph algorithms.

Textbooks / References

  1. T H Cormen, C E Leiserson, and R L Rivest, Introduction to Algorithms, The MIT Press, Cambridge, Massachusetts, USA, 1990 and 2009 (3rd ed.).
  2. Unnikrishnan Cheramangalath, Rupesh Nasre, and Y N Srikant, Distributed Graph Analytics: Programming, Languages, and their Compilation, Springer, 2020.
  3. Amy E, Hodler, and Mark Needham, Graph Algorithms: Practical Examples in Apache Spark and Neo4j. O’Reilly, 2019 (free book, downloadable).
  4. Mark A Weiss, Data Structures and Algorithm Analysis in C++, Pearson, 4th ed., 2014.

Prerequisites: A good knowledge of programming in any programming language. Students will be expected to learn Python on their own.

Grading:

  • Programming assignments – 2 (10 marks each)
  • Programming mini project – 1 (20 marks)
  • Mid-term exams – 2 (15 marks each)
  • Final exam – 30 marks