DAA-lab

This repo contains assignments and programs for Design and Analysis of Algorithms Lab

* week-1 : searching algorithms

1. linear search - O(n)
2. iterative binary search - O(log n)
3. iterative binary search - O(log n)
4. jump search - O(sqrt(n))
5. exponential search - O(log n)

* week-2 :

1. duplicates - to find no. of occurences of a given element in array - O(log n)
2. indices_sum - to find three indices i, j, k such that arr[i] + arr[j] = arr[k] - O(n^3)
3. difference - to count the number of pairs of integers such that their difference is equal to a given key - O(n^2)

* week-3 : sorting algorithms

1. insertion sort - O(n^2)
2. selection sort - O(n^2)
3. merge sort - O(n*log n)

* week-4 : sorting algorithms

1. merge sort - O(n*log n)
2. randomised quick sort - O(n*log n)
3. partial quick sort - O(n)

* week-5 :

1. count character with max. occurence in an array - O(n)
2. pair_sum - to find whether two elements exist such that their sum is equal to the given key element- O(n*log n)
3. common_element - to find list of elements which are common to two sorted integer arrays of size m and n - O(m+n)

* week-6 : bfs / dfs

1. dfs - to find if there is a path between 2 nodes
2. bipartite - to check if the graph is bipartite or not

* week-7 : shortest path problems in graph

1. dijkstra - to find shortest paths of all nodes from a source node
2. bellman ford - to find shortest paths of all nodes from a source node

* week-8 : minimum spanning trees

1. prim's - to find minimum spanning weight
2. kruskal's - to find minimum spanning weight
3. maxWeight - to find maximum spanning weight (using kruskal's)

* week-9 :

1. floyd_warshall - to find all pair shortest path
2. fractional_knapsack - to find list of selected items with given weight and maximum value
3. merge_files - to merge all files into single file with minimum computation

* week-10 :

1. max_activities - to find max no. of non-conflicting activities , given starting and finishing time
2. max_tasks - to find max no. of tasks that can be performed , given time and deadlines
3. majority_element - to find whether majority element exists or not . Also find median .

* week-11 :

1. multiply_matrices - to find min no. of operations to multiply list of matrices
2. coin - to find no. of ways to add coins to make a sum (unbounded knapsack) .
3. equal_sum_subset - to partition a set of elements into 2 subsets of equal sum .