Scribd
Upload
86 views

Design and Analysis of Algorithm Assignment

This document contains 3 assignments on algorithms: 1. The first assignment asks students to sort functions by asymptotic growth order, solve recurrence relations, and implement quicksort. 2. The second assignment asks students to apply minimum spanning tree algorithms (Kruskal's and Prim's) to a graph, use Floyd-Warshall for shortest paths, and solve a Traveling Salesman Problem using branch and bound. 3. The third assignment involves applying breadth-first search, depth-first search, Dijkstra's algorithm, and finding a Hamiltonian circuit using backtracking to various graphs.

Uploaded by

sunnybagga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
86 views

Design and Analysis of Algorithm Assignment

This document contains 3 assignments on algorithms: 1. The first assignment asks students to sort functions by asymptotic growth order, solve recurrence relations, and implement quicksort. 2. The second assignment asks students to apply minimum spanning tree algorithms (Kruskal's and Prim's) to a graph, use Floyd-Warshall for shortest paths, and solve a Traveling Salesman Problem using branch and bound. 3. The third assignment involves applying breadth-first search, depth-first search, Dijkstra's algorithm, and finding a Hamiltonian circuit using backtracking to various graphs.

Uploaded by

sunnybagga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Design and Analysis of Algorithm Assignment

Assignment 1

1. Sort all functions below in increasing asymptotic growth order (big-O). It is important to
note that some of them have the same asymptotic growth. Base 2 is used as usual for lg.

5n, 4 lg n, 4lg lg n, n4, n1/2lg4n, (lg n)5lg n, n lg n, 5n, 4n4, nn^ 1/5

2. Solve the following recurrence relation

a. T(n) = 4T(n/5) + 5n
b. T(n) = 25T(n/5) + n2
c. T(n) = 4T(n/5) + lg5 n √n
d. T(n) = 4T( √n) + lg2 n
e. T(n) = T( n) + 5
f. T(n) = 7T(n/3) + n2
3. Sort the following element using Quick sort.
{13,19, 9, 5,12, 8, 7 ,4, 21, 2, 6}
4. Discuss the steps in Mathematical analysis for recursive algorithm. Do the same for finding
factorial of a number.
Assignment 2

1. Apply Kruskal’s and Prim’s algorithm for the following graph.

2. Use the Floyd-Warshall algorithm and find shortest path between all pair of vertices for the
following graph.

1
3. Consider the following initial cost matrix for Traveling Salesman Problem. Solve this
Problem using branch and bound techniques.

4. Find a Hamiltonian circuit using Backtracking Method.

Assignment 3

1. Apply BFS and DFS algorithm for the following graph.

2
2. Find the shortest path for vertex 1 to vertex 3 in the following graph using Dijkstra’s greedy
algorithm.

3
4

You might also like