Algorithm-and-Data-Structures-MIT-Course

This repository contains my implementation of the algorithms discussed in 6.006 and 6.046J CS courses of MIT open course ware. I used Python 3.7 to code these algorithms.

S.No.	File name	Description
1	peakfinding_1D.py	Illustrates how to create classes in Python
2	peakfinding_2D.py	Illustartes how to create bar, scatter and line plots.
3	Document_Distance	This folder contains 8 variants of an algorithm to compute distance between two documents containg some text. The algorithms are increasingly efficinet implementations
4	insertion_and_merge_sort.py	An implementation of Insertion {O(n^2)} and Merge sort {O(n lg n)}.
5	heap_sort.ipynb	An implementation of Heap Sort algorithm {O(n lg n)}, Build-max-heap is {O(lg n)} and for loop within heap_sort is {O(n)}.
6	Counting_and_Radix_Sort.ipynb	An implementation of the Counting Sort and Radix sort algorithms ~ {O(n)}.
7	Karp-Rabin.ipynb	An implementation of the Karp-Rabin algorithm for string matching in Python.
8	Karatsuba_Multiplication.ipynb	An implementation of the Karatsuba algorithm for faster multiplication ~O(n^1.585).
9	Newton-Raphson-Method.ipynb	An implementation of the Newton-Raphson algorithm for finding roots of a polynomial equation.
10	Breadth_First_Traversal.ipynb	An implementation of breadth first search (or traversal) in a given graph 'G' from a given source vetex 's'.
11	Depth_First_Search.ipynb	An implementation of depth first search (or traversal) in a given graph 'G'.
12	Dijkstra_shortest_path.ipynb	An implementation of Dijkstra's single source shortest path algorithm in a given graph 'G'.
13	Bellman-Ford_Algorithm.ipynb	An implementation of Bellman-Ford single source shortest path algorithm in a given graph 'G'. This algorithm detects negative cycles in a given graph.

Practice Problems

S.No.	File name	Description
1	Fibonacci_Memoization.ipynb	A recursive implementation Fibonacci series generator, its limitation and solution through memoization.
2	RandomWalk_MonteCarlo.ipynb	What is the largest random walk for which no transport (<=4) will be required to return home?