Rayat Institute of Engineering

& Information Technology

Approved by AICTE, Affiliated to PTU, Jalandhar.

& Information Technology

Approved by AICTE, Affiliated to PTU, Jalandhar.

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.

**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.

- Code and analyze to compute the greatest common divisor (GCD) of two numbers.
- Code and analyze to find the median element in an array of integers.
- Code and analyze to find the majority element in an array of integers.
- Code and analyze to sort an array of integers using Heap sort.
- Code and analyze to sort an array of integers using Merge sort.
- Code and analyze to sort an array of integers using Quick sort.
- Code and analyze to find the edit distance between two character strings using dynamic programming.
- Code and analyze to find an optimal solution to weighted interval scheduling using dynamic programming.
- Code and analyze to find an optimal solution to matrix chain multiplication using dynamic programming.
- 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.
- 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.
- Code and analyze to find shortest paths in a graph with positive edge weights using Dijkstra's algorithm.
- Code and analyze to find shortest paths in a graph with arbitrary edge weights using Bellman-Fordalgorithm.
- Code and analyze to find the minimum spanning tree in a weighted, undirected graph.
- Code and analyze to find all occurrences of a pattern P in a given string S.
- Code and analyze to multiply two large integers using Karatsuba algorithm.
- Code and analyze to compute the convex hull of a set of points in the plane.
- (Mini-project Topic) Program to multiply two polynomials using Fast Fourier Transform (FFT).

Railmajra, Near Ropar , Distt. S.B.S Nagar, PIN-144533, Punjab

Home |
Study Programmes |
Placement |
Facilities |
Jobs |
Online Grievance Cell |
Web Mail |
Contact Us

Copyright 2018, RAYAT-BAHRA. All rights reserved. Website designed & maintained by E.D.P. Department.

Copyright 2018, RAYAT-BAHRA. All rights reserved. Website designed & maintained by E.D.P. Department.