 Rayat Institute of Engineering
& Information Technology
Approved by AICTE, Affiliated to PTU, Jalandhar.

Design & Analysis of Algorithms Lab Introduction to fundamental techniques for designing and analyzing algorithms, including asymptotic analysis; divide-and-conquer algorithms and recurrences; greedy algorithms; data structures; dynamic programming; graph algorithms; and randomized algorithms.

### BTCS 508 Design & Analysis of Algorithms Lab

Objective: To get a first-hand experience of implementing well-known algorithms in a high-level language. To be able to compare the practical performance of different algorithms for the same problem.

1. Code and analyze to compute the greatest common divisor (GCD) of two numbers.
2. Code and analyze to find the median element in an array of integers.
3. Code and analyze to find the majority element in an array of integers.
4. Code and analyze to sort an array of integers using Heap sort.
5. Code and analyze to sort an array of integers using Merge sort.
6. Code and analyze to sort an array of integers using Quick sort.
7. Code and analyze to find the edit distance between two character strings using dynamic programming.
8. Code and analyze to find an optimal solution to weighted interval scheduling using dynamic programming.
9. Code and analyze to find an optimal solution to matrix chain multiplication using dynamic programming.
10. Code and analyze to do a depth-first search (DFS) on an undirected graph. Implementing an application of DFS such as (i) to find the topological sort of a directed acyclic graph, OR (ii) to find a path from source to goal in a maze.
11. Code and analyze to do a breadth-first search (BFS) on an undirected graph. Implementing an application of BFS such as (i) to find connected components of an undirected graph, OR (ii) to check whether a given graph is bipartite.
12. Code and analyze to find shortest paths in a graph with positive edge weights using Dijkstra's algorithm.
13. Code and analyze to find shortest paths in a graph with arbitrary edge weights using Bellman-Fordalgorithm.
14. Code and analyze to find the minimum spanning tree in a weighted, undirected graph.
15. Code and analyze to find all occurrences of a pattern P in a given string S.
16. Code and analyze to multiply two large integers using Karatsuba algorithm.
17. Code and analyze to compute the convex hull of a set of points in the plane.
18. (Mini-project Topic) Program to multiply two polynomials using Fast Fourier Transform (FFT).

Rayat Institute of Engineering & Information Technology
Railmajra, Near Ropar , Distt. S.B.S Nagar, PIN-144533, Punjab
Email : rieit@rayatbahra.com
Home | Study Programmes | Placement | Facilities | Jobs | Online Grievance Cell | Web Mail | Contact Us