Scribd
Upload
2 views3 pages

ADA Assignment 2

This document outlines the assignment questions for the Analysis & Design of Algorithms course at City Engineering College for the academic year 2025-26. It includes ten questions covering various topics such as AVL trees, heaps, Horspool's algorithm, Strassen's matrix multiplication, dynamic programming, Kruskal's algorithm, counting sort, applications of algorithms, decision trees, and classifications of computational problems. The assignment is due on April 29, 2026, with the announcement made on May 19, 2026.

Uploaded by

vk20062019123
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
2 views3 pages

ADA Assignment 2

This document outlines the assignment questions for the Analysis & Design of Algorithms course at City Engineering College for the academic year 2025-26. It includes ten questions covering various topics such as AVL trees, heaps, Horspool's algorithm, Strassen's matrix multiplication, dynamic programming, Kruskal's algorithm, counting sort, applications of algorithms, decision trees, and classifications of computational problems. The assignment is due on April 29, 2026, with the announcement made on May 19, 2026.

Uploaded by

vk20062019123
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

CITY ENGINEERING COLLEGE

Approved by AICTE New Delhi & Affiliated by VTU, Belagavi


Doddakallasandra, Off Kanakapura Main Road,
Next to Gokulam Apartment, Bangalore - 560 062.

Department of Artificial Intelligence and Machine Learning

Academic Year: 2025-26 Semester: IV


Course Title: Analysis & Design of Algorithms Course Code: BCS401

Assignment -2 Questions
(COs Mapped: CO-4 and CO-5)
Date of Announcement: 19.05.2026 Date of Submission: 29.04.2026

Question No. 1
What are the properties of an AVL tree? Explain rotations used to construct an AVL tree.
Get an AVL tree for the set 5, 6, 8, 3, 2, 4, 7.

Question No. 2
Define heap. Write bottom-up heap construction algorithm.
Construct heap for the list 1, 8, 6, 5, 3, 7, 4 using bottom-up algorithm and successive key insertion
method.

Question No. 3
Write Horspool’s algorithm. Apply Horspool algorithm to search for the pattern BAOBAB in the text
BESS_KNEW_ABOUT_BAOBABA.

Question No. 4

Explain Strassen’s matrix multiplication [Link] Strassen’s matrix multiplication to multiply


the following matrices. Compare it with conventional method.

Question No. 5

Write an algorithm for solving change making problem using dynamic


programming method. Solve the instance: Denominations: [1,2,3,4,5]
n: 16

Question No. 6

Find the minimum spanning tree using Kruskal’s Algorithm.


CITY ENGINEERING COLLEGE
Approved by AICTE New Delhi & Affiliated by VTU, Belagavi
Doddakallasandra, Off Kanakapura Main Road,
Next to Gokulam Apartment, Bangalore - 560 062.

Question No. 7
Explain Comparison Counting Sort with algorithm and example. And Sort the list using
comparison counting method:
45, 2, 19, 10, 33, 22, 1, 23

Question No. 8

Write applications of:


 Huffman coding
 Minimum spanning trees
 Shortest path algorithms

Question No. 9
Explain Decision Tree model in sorting. Derive lower bound for comparison-based
sorting using decision trees.

Question No. 10
Differentiate P, NP, and NP-Complete problems. What are NP-Hard problems? Compare NP-Hard and NP-
Complete.
CITY ENGINEERING COLLEGE
Approved by AICTE New Delhi & Affiliated by VTU, Belagavi
Doddakallasandra, Off Kanakapura Main Road,
Next to Gokulam Apartment, Bangalore - 560 062.

You might also like