Sem 6 : Competetive Programming Batch C3
L: 2 T: 0 P: 1 Credits: 3
This Repo tracks the progress of course cse331 and contains the solution to the problems discussed during the lectures.
Coding Pearls was the third course in competetive programming batch and aimed towards creating a better understanding of advanced data structures.
Through this course students should be able to:
- CO1: Relate the theoretical as well as practical knowledge to form an amalgamation of working code.
- CO2: Employ a working combination of solutions to ubiquitous problems which are time and space efficient.
- CO3: Identify and comprehend the inner workings behind the design of an optimal solution.
- CO4: Illustrate the usage of algorithms and data structures in the design of an optimal solution towards a problem.
- CO5: Recall the knowledge obtained from various algorithmic paradigms to formulate optimal solutions to real-world problems.
- CO6: Examine and utilise knowledge to build and design reliable code which is capable of passing various test cases.
Heaps (Priority Queues): Max Heap, Min Heap, Heap Sort, K’th Largest element in array, Sort an almost sorted array, Connect n ropes with minimum cost, Array representation of binary heap
Disjoint Set Union: Union-Find algorithm, Union by Rank and Path Compression
Binary Trees: Types of Binary Tree, Insertion in a tree, Deletion in a tree, Tree traversals, Inorder, Preorder, Postorder, Inorder traversal without recursion, Print Postorder traversal from given Inorder and Preorder traversals, Level Order Tree Traversal
Problems based on Binary Trees: Diameter of a tree, Populate Inorder Successor for all nodes, Find n-th node of inorder traversal, Level Order traversal in spiral form, Boundary traversal of binary tree, Finding Lowest Common Ancestors, Sum of nodes in a binary tree having only the left child nodes
Graph Algorithms: Graph and its representations, Breadth First Traversal for a Graph, Depth First Traversal for a Graph, Eulerian path and circuit, Eulerian path for an undirected graph, Eulerian circuit for an undirected graph, Hamiltonian path in an undirected graph
Problems and Algorithms based on Graphs: Distance of nearest cell having 1, Dijkstra’s shortest path algorithm, Bellman Ford algorithm, Minimum Spanning Tree algorithms namely Prim’s algorithm, Kruskal algorithm, Graph colouring problem, Check if graph is bipartite, Detect cycle in graph, Check if cycle exists between two nodes, Strongly Connected Components, Shortest path from 1 to n, Minimum product spanning tree
Practicals:
- Program to implement Min Heap
- Program to implement Max Heap
- Program to print K'th largest element in array
- Program to connect n ropes with minimum cost
- Program to sort an almost sorted array
- Program to insert an element in binary tree
- Program to delete an element from a tree
- Program to implement tree traversals such as inorder, preorder and postorder
- Program to populate inorder successor of all nodes
- Program to implement boundary traversal of all nodes
- Program to find lowest common ancestor
- Program to print level order traversal in spiral form
- Program to implement BFS of a graph
- Program to implement DFS of a graph
- Program to implement Dijkstra's shortest path algorithm
- Program to implement Bellman Ford algorithm
- Program for graph colouring problem
- Program to check if graph is bipartite
- Program to detect cycle in graph
- CRACKING THE CODING INTERVIEW by GAYLE LAAKMANN MCDOWELL, CAREERCUP
- DATA STRUCTURES AND ALGORITHMS: CONCEPTS, TECHNIQUES AND APPLICATIONS by G. A. V. PAI, MCGRAW HILL EDUCATION
Session: 2023-24
I would like to express my sincere gratitude to Raj Karan Singh for their exceptional teaching and guidance throughout this course. Their dedication and expertise have been invaluable in helping me to understand and complete this project.