Scribd
Upload
23 views3 pages

Practice Sheet - Advanced Algorithms

The document outlines various advanced algorithms and sorting techniques, including selection sort, insertion sort, merge sort, quick sort, heap sort, radix sort, and greedy methods for problems like activity selection and fractional knapsack. It presents specific arrays and problems to solve, such as sorting arrays, constructing heaps, maximizing profits, and finding longest common subsequences. Each section requires computations or constructions related to the respective algorithm or problem.

Uploaded by

azmansikder143
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
23 views3 pages

Practice Sheet - Advanced Algorithms

The document outlines various advanced algorithms and sorting techniques, including selection sort, insertion sort, merge sort, quick sort, heap sort, radix sort, and greedy methods for problems like activity selection and fractional knapsack. It presents specific arrays and problems to solve, such as sorting arrays, constructing heaps, maximizing profits, and finding longest common subsequences. Each section requires computations or constructions related to the respective algorithm or problem.

Uploaded by

azmansikder143
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/ 3

Practice Sheet – Advanced Algorithms

1. Sorting (Selection, Insertion, Merge, Quick Sort)

Sort the following array using (selection sort, insertion sort, merge sort, quick sort).​
Also, compute the number of passes, comparisons, and exchanges for selection and
insertion sort.

Array:​
Index: 1 2 3 4 5 6 7 8​
Value: 45 12 78 34 23 89 56 10

2. Sorting (Selection, Insertion, Merge, Quick Sort)

Sort the following array using (selection sort, insertion sort, merge sort, quick sort).​
Also, compute the number of passes, comparisons, and exchanges for selection and
insertion sort.

Array:​
Index: 1 2 3 4 5 6 7 8​
Value: 64 25 12 22 11 35 90 50

3. Heap Sort (Max Heap)

Given the array:​


Index: 1 2 3 4 5 6 7 8​
Value: 15 30 10 50 40 35 5 20

●​ Heapify the array and construct a Max Heap.​

●​ Apply Heap Sort to sort it in ascending order.​

4. Heap Sort (Min Heap)

Given the array:​


Index: 1 2 3 4 5 6 7 8​
Value: 72 45 90 12 33 54 10 27

●​ Heapify the array and construct a Min Heap.​

●​ Apply Heap Sort to sort it in descending order.​

5. Radix Sort
Sort the following array using Radix Sort:​
Array: 329, 457, 657, 839, 436, 720, 355

6. Activity Selection Problem

Meetings with start and end times:

Meeting A B C D E F G H I J

Start 2 1 5 0 8 3 6 8 12 11

End 4 6 7 3 9 5 10 11 14 13

Find the maximum number of non-overlapping meetings that can be scheduled.

7. Fractional Knapsack (Greedy)

A shopkeeper has a bag with capacity 50 kg. Items available:

Item Weight (kg) Profit ($)

A 10 60

B 20 100

C 30 120

D 25 75

Find how much of each item should be included to maximize profit.

8. Huffman Coding

Compress the message:​


Message: “AABACADABACABAACD”

●​ Build a Huffman Tree.​

●​ Encode the message.​

●​ Find the original size (in bits, assuming 8 bits/char) and the compressed size.​

9. 0/1 Knapsack

You have a backpack with capacity 20 kg. Items available:

Item Weight (kg) Value ($)


1 4 40

2 8 100

3 5 50

4 3 60

5 7 70

Select items to maximize total value without exceeding the weight limit.

10. Rod Cutting

You have a rod of length 10 units. Prices for different lengths are given:

Length 1 2 3 4 5 6 7 8 9 10

Price 2 5 7 8 10 13 17 20 24 30

Find the maximum revenue obtainable by cutting the rod optimally.

11. Longest Common Subsequence (LCS)

Find the length and string of the LCS for:

●​ String1: "ABCBDAB"​

●​ String2: "BDCAB"

You might also like