[go: up one dir, main page]
Scribd
Upload
41 views1 page

Bhagwan Mahavir College of Engg & Technology Subject: - Analysis and Design of Algorithms. Subject Code:-3150703 Semester: 5 Dept:Ce

This document contains an assignment for a class on Analysis and Design of Algorithms. The assignment contains 7 questions about algorithms topics including the Rabin-Karp algorithm, finite automata, complexity classes P, NP, NP-complete and NP-hard, the travelling salesman problem, naive string matching, and Hamiltonian problems. Students are asked to explain, analyze, and prove concepts related to these algorithms and provide examples where applicable. The assignment is for a 5th semester computer engineering course and is due on October 15th, 2020.

Uploaded by

Lion Kenan
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
41 views1 page

Bhagwan Mahavir College of Engg & Technology Subject: - Analysis and Design of Algorithms. Subject Code:-3150703 Semester: 5 Dept:Ce

This document contains an assignment for a class on Analysis and Design of Algorithms. The assignment contains 7 questions about algorithms topics including the Rabin-Karp algorithm, finite automata, complexity classes P, NP, NP-complete and NP-hard, the travelling salesman problem, naive string matching, and Hamiltonian problems. Students are asked to explain, analyze, and prove concepts related to these algorithms and provide examples where applicable. The assignment is for a 5th semester computer engineering course and is due on October 15th, 2020.

Uploaded by

Lion Kenan
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/ 1

Bhagwan Mahavir College Of Engg & Technology

Subject: - Analysis And Design of Algorithms.


Subject Code:-3150703
SEMESTER: 5th DEPT:CE

ASSIGNMENT - 4

1. What is the basic idea behind Rabin – Karp algorithm? What is expected
running time of this algorithm? Explain it with example.
2. What is Finite Automata? How it can be used in string matching.
3. Define P, NP, NP complete and NP-hard problems.
4. Explain travelling salesman problem. Prove that it is NP complete problem.
5. Explain naïve string matching algorithm with example.
6. State whether Hamiltonian problem is a NP-Complete problem? Justify your
answer.
7. Explain Class of problems beyond NP – P SPACE .

SUBJECT INCHARGE: Prof.Twinkle Ankleshwaria


(BMCET-CE DEPT)
Submission date :-15 /10/2020

You might also like