Exercise 1

Date:24-07-2024

BCSE204P Design and Analysis of Algorithms Lab

1. The symbols a, e, i, o, u are called as vowels and the remaining symbols of English
alphabet are called consonants. A word of length 6 (a word with 6 symbols) w1 is
said to be vowel − greater than another word w1 of lenght 6 if the number of distinct
vowels is greater than or equal to the number of distinct vowels in w2. If two words
w1, w2 have the same number of vowels, the word which comes later in an
alphabetical order, is said to be vowel−greater than the other. The number of distinct
vowels in abbaae is 2. The word aaeoub is said to be vowel − greater than the word
abedfg since the number of distinct vowels in the first word is 4 and the number of
distinct vowels in the second word is 2. Similarly, the word deoudd is vowel − greater
than cedodu. Here, both the words have the same number of vowels and the first
word deoudd comes later in the alphabetical order when compared with the second
word cedodu. Given the three words dedodu, aeiouu, befghs, they are arranged in an
ascending order with respect to the operator vowel − greater, as befghs, dedodu,
aeiouu. Consider an array of n distinct words of same length (ie., no two words are
same), design an algorithm and c++ code to sort the array in an ascending order with
respect to the relational operator vowel − greater. Analyse the algorithm with all the
required steps.

2. Consider a set S of positive integers, does there exist two disjoint subsets S1, S2 of S
such that the sum of the integers in S1 equals the sum of the integers of S2. For the
input S = {3, 4, 2, 5}, the solution to the problem is ‘yes’ since there exist two subsets
S1 = {3, 4}, S2 = {2, 5} such that the sum of the elements of S1 equals the sum of the
elements of S2 and both subsets are of equal size. The solution to the problem is ‘no’
if no such subsets exist where the sum of the elements in S1 equals the sum of the
elements in S2 and both subsets are of equal size. Design a pseudocode and c++ code
to solve this problem. Analyse the algorithm with all the required steps.

3. Let A( 1...n) be a sorted array of n integers. It is observed that elements in this array
occur one or more times. The problem is to find the frequency of the elements of A.
Write an algorithm and c++ code to output the frequency of each element in A.

Answers

1)

Algorithm:
1)Count Distinct Vowels:

 Create a function to count the number of distinct vowels in a word.

 Use a set to store vowels and find the size of the set to get the number of distinct
vowels.

 2)Comparison Function:

 Create a comparison function that compares two words based on the number of
distinct vowels.
 If two words have the same number of distinct vowels, compare them
lexicographically (alphabetical order).

 3)Sort the Array:

 Use the std::sort function with the custom comparison function to sort the
array.

 4)Analysis:

 The time complexity for counting distinct vowels in a word is O(1) since the word
length is fixed (6).
 The time complexity for comparing two words is O(1) for counting vowels and O(6)
for lexicographic comparison.
 The overall time complexity for sorting is O(n log n), where n is the number of words.

Code:

#include <iostream>

#include <vector>

#include <algorithm>

#include <set>

#include <string>

using namespace std;

// Function to count distinct vowels in a word

int countDistinctVowels(const string& word) {

set<char> vowels;

for (char c : word) {

if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {

 vowels.insert(c);

return vowels.size();

// Custom comparison function

bool compareWords(const string& w1, const string& w2) {

int vowelsW1 = countDistinctVowels(w1);

int vowelsW2 = countDistinctVowels(w2);

if (vowelsW1 != vowelsW2) {

return vowelsW1 < vowelsW2;

} else {

return w1 < w2; // Lexicographical comparison

// Function to sort array of words

void sortWords(vector<string>& words) {

sort(words.begin(), words.end(), compareWords);

int main() {

vector<string> words = {"dedodu", "aeiouu", "befghs"};

sortWords(words);

for (const string& word : words) {

cout << word << " ";

}
 cout << endl;

return 0;

output:

2)

Algorithm:

1.Initial Check:

 Calculate the total sum of the elements in the set S.

 If the total sum is odd, it's impossible to split S into two subsets of equal sum,
so return "no".
2. Dynamic Programming Table:

 Use a 3D DP table dp[i][j][k] where:

 i is the current index in the set S,
 j is the remaining sum we need to achieve in subset S1,
 k is the number of elements used in subset S1.
3. Recursive DP:

 Initialize the table with base cases.

 Fill the table based on whether we include the current element in S1 or S2.
4. Check Feasibility:
  After filling the DP table, check if it's possible to partition the set into two
equal-sum subsets with equal size.

Code:

#include <iostream>

#include <vector>

#include <numeric>

using namespace std;

bool canPartitionEqualSize(const vector<int>& S) {

int totalSum = accumulate(S.begin(), S.end(), 0);

int n = S.size();

if (totalSum % 2 != 0) return false;

int halfSum = totalSum / 2;

int halfSize = n / 2;

vector<vector<vector<bool>>> dp(n + 1, vector<vector<bool>>(halfSum + 1,

vector<bool>(halfSize + 1, false)));

dp[0][0][0] = true;

for (int i = 1; i <= n; ++i) {

for (int j = 0; j <= halfSum; ++j) {

for (int k = 0; k <= halfSize; ++k) {

dp[i][j][k] = dp[i - 1][j][k];

if (j >= S[i - 1] && k > 0) {

dp[i][j][k] = dp[i][j][k] || dp[i - 1][j - S[i - 1]][k - 1];

}
 }

return dp[n][halfSum][halfSize];

int main() {

vector<int> S = {3, 4, 2, 5};

if (canPartitionEqualSize(S)) {

cout << "yes" << endl;

} else {

cout << "no" << endl;

return 0;

Output:
PseudoCode:

function canPartitionEqualSize(S):

totalSum = sum(S)

n = length(S)

if totalSum % 2 != 0:

return "no"

halfSum = totalSum / 2

halfSize = n / 2

dp = 3D array of size (n+1) x (halfSum+1) x (halfSize+1) initialized to False

dp[0][0][0] = True

for i from 1 to n:

for j from 0 to halfSum:

for k from 0 to halfSize:

dp[i][j][k] = dp[i-1][j][k]

if j >= S[i-1] and k > 0:

dp[i][j][k] = dp[i][j][k] or dp[i-1][j-S[i-1]][k-1]

return "yes" if dp[n][halfSum][halfSize] else "no"

3)

Algorithm:

 Initialize a counter and a variable to store the current element.

 Traverse the array from the beginning to the end.

 For each element:

 If it is the same as the current element, increment the counter.

 If it is different from the current element:
  Output the current element and its count.
 Reset the counter and update the current element.

 After the loop, output the last element and its count.

PsuedoCode:
function findFrequencies(A):

n = length(A)

if n == 0:

return

currentElement = A[0]

count = 1

for i from 1 to n:

if A[i] == currentElement:

count += 1

else:

output(currentElement, count)

currentElement = A[i]

count = 1

output(currentElement, count)

Code:

#include <iostream>

#include <vector>

using namespace std;

void findFrequencies(const vector<int>& A) {

int n = A.size();

if (n == 0) return;
 int currentElement = A[0];

int count = 1;

for (int i = 1; i < n; ++i) {

if (A[i] == currentElement) {

count += 1;

} else {

cout << currentElement << " occurs " << count << " times" << endl;

currentElement = A[i];

count = 1;

// Output the count for the last element

cout << currentElement << " occurs " << count << " times" << endl;

int main() {

vector<int> A = {1, 1, 2, 2, 2, 3, 3, 4};

findFrequencies(A);

return 0;

Output: