DAA-Lab-5thSem

All the programs done in Design and Analysis of Algorithms Lab in my 5th Semester.

Lab 1 | 20-07-2024

1. largest.cpp Write a program to find the largest element in a given array.
2. evenodd.cpp Convert an array such that all the even elements are grouped together followed by the odd elements.
3. presum.cpp Find the prefix sum of an array.
4. secLargest.cpp Find the second Largest and Smallest element in an array.
5. dupe.cpp Read n numbers from a file and output
   1. The number of duplicate elements in the array.
   2. The most frequent element in the array.

Lab 2 | 27-07-2024

1. d2b.cpp WAP to convert the first n decimal numbers of a disc file to binary using recursion. Store the binary value in separate disc file.
2. agcdb.cpp WAP to find GCD of first n pairs of numbers from a file using recursion. Save the output to file.

Lab 3 | 03-08-2024

1. RotateRight.cpp WAP to shift the elements of an array to the right by k positions.
2. RotateLeft.cpp WAP to shift the elements of an array to the left by k positions.
3. recrev.cpp WAP to reverse an array using recursion.

Lab 4 | 10-08-2024

1. merge.cpp WAP to sort an array using Merge Sort.

Lab 5 | 17-08-2024

1. quick.cpp WAP to sort an array using Quick Sort.
2. mul2dig.cpp WAP to multiply two numbers using Divide and Conquer.
3. maxsub.cpp Find the Maximum Sum Subarray.

Lab 6 | 24-08-2024

Lab 7 | 31-08-2024

1. huff.cpp Implement Huffman Coding for sequences:
   • BCCABBDDAECCBBAEDDCC
   • 122341322144344
2. knap.cpp Implement Fractional Knapsack with following strategies
   • Non-increasing order of profit
   • Non-decreasing order of weight
   • Non-increasing order of profit/weight ratio

Lab 8 | 28-09-2024

1. jobseq.cpp Implement Job Sequencing Algorithm.
2. prims.cpp Implement Prims Algorithm to find Minimum Spanning Tree and its sum.
3. kruskals.cpp Implement Kruskal's Algorithm to find Minimum Spanning Tree and its sum.

Lab 9 | 05-10-2024

1. dijkstra.cpp Implement Dijkstra's Algorithm to find the shortest path from a source node to all other nodes.

Lab 10 | 26-10-2024

1. binknap.cpp Implement 0/1 Knapsack Problem using Dynamic Programming.
2. mcm.cpp Implement Matrix Chain Multiplication using Dynamic Programming.

Lab 11 | 02-11-2024

1. floyd.cpp Implement Floyd's Algorithm to find the shortest path between all pairs of nodes.
2. lcs.cpp Implement Longest Common Subsequence using Dynamic Programming.
3. msg.cpp Multi Stage Graph Problem.