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

Ada Important Qa

The document outlines important questions for the BCS401 module on Analysis and Design of Algorithms, categorized into five modules. Each module covers key topics such as algorithm basics, divide and conquer strategies, greedy methods, dynamic programming, and backtracking techniques. The questions are designed to assess understanding of algorithm properties, complexity analysis, and various algorithmic approaches to problem-solving.

Uploaded by

killerkhuni7
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
6 views2 pages

Ada Important Qa

The document outlines important questions for the BCS401 module on Analysis and Design of Algorithms, categorized into five modules. Each module covers key topics such as algorithm basics, divide and conquer strategies, greedy methods, dynamic programming, and backtracking techniques. The questions are designed to assess understanding of algorithm properties, complexity analysis, and various algorithmic approaches to problem-solving.

Uploaded by

killerkhuni7
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

Analysis and Design of Algorithms (BCS401) - Module-wise Important Questions (Strictly from

Syllabus)

Module 1: Algorithm Basics and Analysis

1. Define an algorithm. Explain properties of algorithms.


2. Differentiate between natural language and pseudo code specifications.
3. Explain fundamental steps in algorithmic problem solving.
4. Explain Asymptotic Notations: Big O, Big Ω, Big Θ with graphs.
5. Discuss efficiency classes with examples.
6. Mathematical analysis of non-recursive algorithm: Sequential Search.
7. Mathematical analysis of recursive algorithm: Factorial or Tower of Hanoi.
8. Estimate space and time complexity of a given algorithm.
9. Apply Master’s Theorem to solve recurrence relations.
10. String matching algorithm using brute force technique with time complexity.

Module 2: Divide and Conquer & Decrease and Conquer

1. Write and explain Merge Sort and Quick Sort algorithms. Derive time complexity.
2. Use Master’s theorem to solve: T(n) = 2T(n/2) + n and T(n) = 4T(n/2) + n^2.
3. Write a divide and conquer algorithm to find maximum and minimum in an array.
4. Explain Binary Search using divide and conquer approach.
5. Explain Insertion Sort using decrease and conquer method with complexity.
6. Perform topological sorting on a given DAG using decrease by one method.

Module 3: Greedy Method & Graph Algorithms

1. Solve Job sequencing with deadlines problem using greedy method.


2. Apply Greedy Fractional Knapsack algorithm and derive optimal profit.
3. Construct MST using Prim’s and Kruskal’s algorithms. Analyze time complexity.
4. Apply Dijkstra’s algorithm for single-source shortest path.
5. Build a max-heap and explain how it supports Heap Sort.
6. Explain the construction of Huffman coding tree and derive total cost.

Module 4: Dynamic Programming

1. Explain general method of dynamic programming with example.


2. Apply dynamic programming to solve 0/1 Knapsack problem.
3. Solve multistage graph problem using DP.
4. Solve Bellman-Ford Algorithm for shortest path and check for negative cycles.
5. Apply dynamic programming to solve TSP problem (minimum cost tour).
6. Construct Optimal Binary Search Tree (OBST) using dynamic programming.

1
Module 5: Backtracking, Branch & Bound, NP Problems

1. Explain the general method of backtracking.


2. Solve N-Queens problem using backtracking with step-by-step states.
3. Solve Sum of Subsets problem using backtracking.
4. Write an algorithm for graph coloring using backtracking.
5. Find Hamiltonian cycle using backtracking.
6. Solve Assignment Problem using Branch and Bound with cost matrix.
7. Apply Branch and Bound to solve 0/1 Knapsack or TSP.
8. Explain deterministic vs. non-deterministic algorithms.
9. Define P, NP, NP-Complete, and NP-Hard problems with examples.

You might also like