Design and Analysis of Algorithms

This repository contains all the C programs that I have executed in my Design and Analysis of Algorithms course for my 3rd Year of Undergrad in Computer Science at Dayananda Sagar University, Bengaluru, India in Q4 2022.

List of Programs

Serial No.	C File Name	Description
1	1_towerOfHanoi.c	A C program to implement Tower of Hanoi using recursion.
2	2_binarySearch.c	A program to search for a key element in an array using binary search algorithm.
3	3_mergeSort.c	A C program to sort an array using Merge Sort Algorithm.
4	4_quickSort.c	A C program to sort an array using Quick Sort Algorithm.
5	5_primsAlgorithm.c	A C program to find the Minimum Cost Spanning Tree of a given graph using Prim's Algorithm.
6	6_kruskalsAlgorithm.c	A C program to find the Minimum Cost Spanning Tree of a given graph using Kruskal's Algorithm.
7	7_knapSack.c	A C program to solve the 0/1 Knapsack Problem using Dynamic Programming.
8	8_longestCommonSubsequence.c	A C program to find the Longest Common Subsequence of two given strings using Dynamic Programming.
9	9_allPairsShortestPath.c	A C program to find the All Pairs Shortest Path given graph using Floyd's Algorithm.
10	10_travellingSalesmanProblem.c	A C program to find the shortest path that visits each city exactly once and returns to the starting point using Dynamic Programming.

Miscellaneous Programs

Serial No.	C File Name	Description
1	M_printFactorial.c	Write a C program to find the factorial of a number using Recursion.

How to Run

1. Ensure that you have a C compiler installed on your system.

   gcc --version

   It should look something like this

   If you don't have a C compiler installed, you can download one from here or using your package manager.

   Examples:

   • Ubuntu -

   sudo apt install gcc

   • Arch Linux -

   sudo pacman -S gcc

   • macOS -

   brew install gcc

   Additionaly, if you are using Windows, follow the steps specified here.

2. Clone the repository using the following command:

   gh repo clone rexgraystone/daa

   or

   git clone https://github.com/rexgraystone/daa.git

3. Change the directory to the cloned repository:

   cd daa

4. Compile the C program using the following command:

   gcc <C File Name> -o <Output File Name>

5. Run the program using the following command:

   ./<Output File Name>

Note

The programs are written in C and compiled using GCC compiler on macOS Ventura 13.0.