Welcome to Rajesh's Algorithm Portfolio! While completing Algorithms Specialization from Stanford I had to solve few problems. Here is the list-
Course 1 - Divide and Conquer, Sorting and Searching, and Randomized Algorithms - info
- Multiplication method using Karatsuba Divide and Conquer algorithm. view code
- Karatsuba Pseudocode - https://en.wikipedia.org/wiki/Karatsuba_algorithm#Pseudocode
- Karatsuba formula = ((ac)10^n) + (((a+b)(c+d) - (ac) - (bd)) * 10^(n/2)) + (bd)
- X = 10^(10/2) * a + b and Y = 10^(10/2) * c + d where a, b, c, d are n/2 digit numbers
- XY = (10^n)ac + 10^(n/2) * (ad+bd) + bd
- (a + b) * (c + d) = ac + ad + bc + bd
- (a+b)(c+d) - (ac) - (bd) = ad + b*d
- XY = ((ac)10^n) + (((a+b)(c+d) - (ac) - (bd)) * 10^(n/2)) + (b*d)
- Assumptions -
-
- Both numbers are non-negative. This can easily be fixed by counting number of
- negative numbers in multiplication whether it is odd or even.
- Running time complexity - O(n^(log_2(3))) = O(n^1.59)
- Given an array A, compute the number of inversions = number of pairs {i, j} such a that A[i] > A[j] and i < j. view code
- You are given a unimodal array of n distinct elements, meaning that its entries are in increasing order up until its maximum element, after which its elements are in decreasing order. Give an algorithm to compute the maximum element that runs in O(log n) time. view code
- You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative, or zero. You want to decide whether or not there is an index i such that A[i] = i. Design the fastest algorithm that you can for solving this problem. view code
- You are given as input an unsorted array of n distinct numbers, where n is a power of 2. Give an algorithm that identifies the second-largest number in the array, and that uses at most n + log_2 n - 2 comparisons. view code
- Count the number of comparisons during quick sort. If m is the length of an array then m-1 comparisons will happen as pivot is compared with rest of the elements. view code
- Average case running time complexity - O(n log(n))
- Worst case running time complexity - O(n^2)
- Running time complexity depends on how good the pivot is selected.
- I found 'median of three' pivot selection produced the near merge sort results.
- Given a graph, find minimum number of cuts. view code
- A QuickSort variant to get nth biggest number in an array. view code
- Array elements are unsorted and order could be of max array length
- Running time complexity - O(n) (Its contrary to what code looks like O(n^2))
Course 2 - Graph Search, Shortest Paths, and Data Structures - info
- Given a graph, find all Strongly Connected Components. view code
- A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.
- Given a directed acyclic graph, find topologic sort order of nodes. view code
- Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
- Given a weighted graph, find shortest distance path using Dijkstra algorithm from source to other nodes. view code
- The goal of this problem is to implement the "Median Maintenance" algorithm. view code
- The text file contains a list of the integers from 1 to 10000 in unsorted order; you should treat this as a stream of numbers, arriving one by one. Compute the sum of these 10000 medians, modulo 10000 (i.e., only the last 4 digits).
- Given list of numbers, count distinct target sum t values in a given range [low, high] for distinct pairs of numbers in a given set. view code
- This is also called as Two Sum problem.