Design and Analysis of Algorithms Lab

 Share more and more And comment for help



 List of Experiment:

Task 1: Code and analyze solutions to the following problem with given strategies:

i. Knap Sack using a greedy approach

ii. Knap Sack using a dynamic approach

Task 2: Code and analyze to find an optimal solution to matrix chain multiplication

using dynamic programming.

Task 3: Code and analyze to find an optimal solution to TSP using dynamic

programming.

Task 4: Implementing an application of DFS such as:

i. to find the topological sort of a directed acyclic graph

ii. to find a path from source to goal in a maze.

Task 5: Implement an application of BFS such as:

i. to find connected components of an undirected graph

ii. to check whether a given graph is bipartite.

Task 6: Code and analyze to find the shortest paths in a graph with positive edge weights

using Dijkstra’s algorithm.

Task 7: Code and analyze to find shortest paths in a graph with arbitrary edge

weights using the Bellman-Ford algorithm.

Task 8: Code and analyze to find shortest paths in a graph with arbitrary edge

weights using Flyods’ algorithm.

Task 9: Code and analyze to find the minimum spanning tree in a weighted,

undirected graph using Prims’ algorithm

Task 10: Code and analyze to find the minimum spanning tree in a weighted,

undirected graph using Kruskals’ algorithm.

Task 11: Coding any real-world problem or TSP algorithm using any heuristic

technique.

Lab Outcomes:

The student will be able to:

1. Improve practical skills in designing and implementing complex problems with

different techniques;

2. Understand the comparative performance of strategies and hence choose appropriate, to

apply to specific problem definition;

3. Implement Various tree and graph-based algorithms and become familiar with their

design methods; &

4. Design and Implement heuristics for real-world problems.

Reference Books

1. Data Structures and Algorithms in C++, Weiss, 4th edition, Pearson

2. Data Structures and Algorithms Using Python and C++, David M. Reed and John

Zelle, 2009 edition (available as e-book), Franklin Beedle& Associates.


Comments

Post a Comment

Popular posts from this blog

AMCAT

Image
 Share more and more And comment for help AMCAT  : Introduction:  AMCAT tests students from different fields in various domains with the help of in-depth micro analysis in each domain. The test consists of various sections/modules which you can choose according to your profile or educational background. There are certain modules that are compulsory for everyone (Language and Aptitude Modules), whereas others are optional. During the test, you will be given an option to select any two domain-specific modules. It is recommended that you go through the module description and befitting job profiles before you go to take the AMCAT. Your choice of modules increases your visibility for particular kinds of jobs, for instance, if you take the Programming Module, you will be visible to more IT companies whereas taking an HR module will help you find HR profiles. It is best for you to go through the module list now and decide which optional modules you would like to take. Provided below is the li
Read more

all question papers second (2) semester

Image
 Share more and more And comment for help of mathematics  pre-mst 1( of 2nd semester2020 )            read online                                         click here   download                                             click here MST click here  (2020 second semester  )               click here               ................................................ university paper   (December 2019)        read online        click here download           click here university paper   (May 2019)                   read online        click here download           click here ....................................... of chemistry PreMST 1      (  2020   )                                  click here MST 1       (2020)                                               click here ........................................................... Of PPS  PreMST 1   (2020)                                            click here MST     1     (2020)                                             click here ...............
Read more

Operating Systems Lab

Image
 Share more and more And comment for help List Of  Experiments: Task 1:  Installation Process of various operating systems. Task 2:  Implementation of CPU scheduling algorithms to find turnaround time and waiting time. a) FCFS b) SJF c) Round Robin (pre-emptive) d) Priority. Task 3:  Virtualization, Installation of Virtual Machine Software and installation of Operating System on Virtual Machine. Task 4:  Commands for files & directories: cd, ls, cp, md, rm, mkdir, rmdir. Creating and viewing files using cat. File comparisons. Disk related commands: checking disk free spaces. Processes in linux, connecting processes with pipes, background processing, managing multiple processes. Background process: changing process priority, scheduling of processes at command, batch commands, kill, ps, who, sleep. Printing commands, grep, fgrep, find, sort, cal, banner, touch, file. File related commands ws, sat, cut, grep. Task 5:  Shell Programming: Basic of shell programming, various types of she
Read more