[go: up one dir, main page]
Scribd
Upload
11 views2 pages

Tutorial - III

The document outlines a tutorial for the course CSE3004 - Design and Analysis of Algorithms, with a due date of December 19, 2024, and a total of 50 marks. It includes five problems requiring the application of various algorithms, such as Naïve String Matching, dynamic programming for minimum-cost paths, the N-Queens problem, the Traveling Salesman Problem, and a Non-Deterministic Polynomial Algorithm for Sequential Search. Each problem requires detailed explanations, analyses, and solutions.

Uploaded by

Ayush pandey
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views2 pages

Tutorial - III

The document outlines a tutorial for the course CSE3004 - Design and Analysis of Algorithms, with a due date of December 19, 2024, and a total of 50 marks. It includes five problems requiring the application of various algorithms, such as Naïve String Matching, dynamic programming for minimum-cost paths, the N-Queens problem, the Traveling Salesman Problem, and a Non-Deterministic Polynomial Algorithm for Sequential Search. Each problem requires detailed explanations, analyses, and solutions.

Uploaded by

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

SCHOOL OF COMPUTING SCIENCE AND ENGINEERING (SCSE)

CSE3004 - DESIGN AND ANALYSIS OF ALGORITHMS


TUTORIAL - III
Due Date: 19.12.2024 Total Marks: 50
Part A (5*10=50)
1. Given a text T="mississippi" and a pattern P="issi", apply the Naïve String Matching
Algorithm to find all occurrences of the pattern in the text. Also, describe the algorithm
and analyze its best-case and worst-case time complexities.
2. Given a directed, weighted multi-stage graph (as shown in the image), where each edge
has an associated weight. The graph consists of 5 stages, with node 1 as the source and
node 9 as the destination. Using the dynamic programming approach, compute the
minimum-cost path from 1 to 9. Provide the total cost of this path and list the sequence
of nodes that make up the minimum-cost path.

3. Explain the N-Queens problem in detail, illustrate the state space tree for the 4-Queens
problem, solve it using the backtracking algorithm, and determine the algorithm's time
complexity.

Dr.I.Jasmine, VIT Bhopal University, SCOPE


4. Given a graph representing the Traveling Salesman Problem (TSP to find an
approximate solution and provide the total cost of the tour.

5. Read the given problem statement for Sequential Search and write the Non-
Deterministic Polynomial Algorithm.

Dr.I.Jasmine, VIT Bhopal University, SCOPE

You might also like