Analysis and Design of Algorithms (IT-3002) - B.E RGPV CBCS & CBGS Scheme Notes -->

## Course Objectives

Data structure includes analyzing various algorithms along with time and space complexities. It also helps students to design new algorithms through mathematical analysis and programming.

## Syllabus

UNIT 1:
Introduction of Algorithms, Analysis of algorithms: Space Complexity, Time Complexity, recurrence relation and Asymptotic Notation, Divide and Conquer: General Methods, Analysis and Design, Binary Search, Quick sort, Merge sort, Strassen’s matrix multiplication.

UNIT 2:
Greedy Strategy: Introduction, examples of greedy method like optimal merge pattern, Huffman coding, Minimum spanning trees, knapsack problem, job sequencing with dead lines single source shortest path algorithms.

UNIT 3:
Dynamic Programming: Introduction, Problem based on this approach such as 0/1 Knapsack Multistage graph, reliability design, Floyd-warshall algorithms.

UNIT 4:
Backtracking Concept and its example like 8 Queen’s problem, Hamiltonian cycle, Graph coloring problem, 15 Puzzle problem, Least Cost Search

UNIT 5:
Introduction to branch & bound method, examples of branch & bound methods like traveling sales man problem, meaning of lower bound theory and its use in solving algebraic problem. NPcompleteness & NP hard problems. Basic Concept of non deterministic algorithms. NP hard and NP complete classes.

• Unit 1
• Unit 2
• Unit 3
• Unit 4
• Unit 5

## Course Outcomes

1. Students will be able to understand fundamentals of algorithms.
2. Understanding various design methods for graphs.
3. Learning different concepts of backtracking including puzzle problem and graph coloring.
4. Getting familiar with non-deterministic algorithms and techniques of branch and bound.

## Reference Books:

1. Horowitz, Sahani,Rajasekaran “ Fundamentals of Computer Algorithms”, Universities Press. 2. Thomas H. Cormen, “Introduction to Algorithms”, PHI.
3. Harsh Bhasin “Algorithms Design and Analysis” Oxford.
4. I.Chandra Mohan “ Design and Analysis of Algorithms” PHI

## List of Experiments:

1. Implement Binary Search using C++.
2. Implement Quick sort using C++.
3. Implement Strassen Matrix multiplication on the given matrix.
4. Implement Merge sort on the given list of elements.
5. Implement Job sequencing problem using C++.
6. Implement Floyd warshall algorithm using C++.
7. Implement 8 – queens problem using backtracking.
8. Implement graph coloring problem using C++.
9. Implement 0/1 knapsack using branch and bound.
10. Implement travelling salesman problem using C++.

## You May Also Like

#### Services

###### COMPLETELY FREE !!!

Yup, everything is free....

###### NO REGISTRATION REQUIRED

User doesn't have to register for accessing the files, all the files are free & universally accessible without any condition or restriction.

###### RESPONSIVE DESIGN & USER-FRIENDLY

Our webpages are responsive & user-friendly, which means it will automatically adjust according to your device screen size and you will find stuff without ant hustle.

All the files are uploaded on our super-fast servers so that they can be easily downloaded with high speed.

###### NEW PROJECTS

For providing a better experience to our users we are developing our Android application, the application will have a lot of awesome features so stay tuned ;).

###### AWESOME SUPPORT TEAM

Our AI-powered Chatbots are always here to help you so, feel free to ask any question or report if you face any problem. Our team also monitors all chatbots traffic & they will contact you if chatbot fails to help.