Design and Analysis of Algorithm Lab Program | All in One
Design and Analysis of Algorithm Lab Program
Program 1:
- A] Create a Java class called Student with the following details as variables within it.
- USN
- Name
- Branch
- Phone
Write a Java Program to create n student objects and print the USN, Name, Branch, Phone of all these objects with the suitable headings
- B] Write a Java Program to implement the stack using arrays. Write Push(), Pop(), and Display() methods to demonstrate its working.
2A] Design a superclass called staff with details as StaffId, Name, Phone, Salary. Extend this class by writing three sub-classes namely Teaching(domain, publications), Technical(skills), and Contract(period). Write a Java Program to read and display at least 3 staff objects of all the 3 categories.
2B] Write a Java class called the customer to store their name and date_of_birth. The date_of_birth format should be dd/mm/yyyy. Write methods to read customer data as <name, dd/mm/yyyy> and display as <name, dd, mm, yyyy> using StringTokenizer class considering the delimiter character as ” / “.
3A] Write a Java Program to read two integers a and b. Computer a/b and print when b is not zero. Raise an exception when b is equal to zero
3B] Write a Java Program that implements a multi-thread application that has three threads. The first thread generates a random integer for every 1 second; the second thread computes the square of the number and prints; the third thread will print the value of the cube of the number.
4] Sort a given set of n integer elements using the quick sort method and compute its time complexity. Run the program for varied values of n>5000 and record the time taken to sort. Plot a graph of the time taken versus nongraph sheet. The elements can be read from a file or can be generated using the random number generator. Demonstrate using Java how the divide and conquer method works along with its time complexity analysis: worst case, average case, and best case.
5] Sort a given set of n integer elements using the merge sort method and compute its time complexity. Run the program for varied values of n>5000, and record the time taken to sort. Plot a graph of the time taken varses non-graph sheet. The elements can be read from a file or can be generated using the random number generator. Demonstrate using Java how the divide and conquer method works along with its time complexity analysis: worst case, average case, and best case.
6] Implement in Java, the 0/1 Knapsack problem using
- A] Dynamic Programming method
- B] Greedy method
7] From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra’s algorithm. Write the program in Java
8] Find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal’s algorithm. Use Union-Find algorithms in your program
9] Find Minimum Cost Spanning Tree of a given connected undirected graph using Prim’s algorithm.
10] Write Java Programs to
- A] Implement all-pairs shortest paths problem using Floyd’s algorithm
- B] Implement Travelling sales person problem using dynamic programming
11] Design and implement in java to find a subset of a given set S={S1, S2,….,Sn} of n positive integers whose SUM is equal to a given positive integer d. For example, if S={1,2,5,6,8} and d=9, there are two solutions {1,2,6} and {1,8}. Display a suitable message, if the given problem instance doesn’t have a solution.
12] Design and implement in Java to find all Hamiltonian Cycles in a connected undirected Graph G of n vertices using the backtracking principle.
