Assignment 01

Name: Kamal Shah

Class ID: CU-4320-2023
Subject: DSA
Submitted to: Sir Ateeq Rehman
Date: 11/ 25/ 2024
 1: String Basics:
What is String?
In C++, a string is a sequence of characters enclosed within double quotes (""). It's
a fundamental data structure used to represent textual information, such as names,
addresses, sentences, or even code itself.

Important data structure:

1: Textual Representation:
Strings are the primary way to represent and manipulate textual data, which is
ubiquitous in computing.

2: Input and Output Interaction:

They are used for input and output operations, allowing users to interact with
programs through text-based interfaces.

3: Data Storage and Retrieval:

Strings are used to store and retrieve information from files, databases, and other
data sources.

4: Algorithm and Data Structure Implementation:

Many algorithms and data structures, such as sorting algorithms, searching
algorithms, and text processing algorithms, rely heavily on string manipulation.

5: Language Syntax:
Strings are essential for defining the syntax and semantics of programming
languages.

Strings Applications:

1: Text Processing:
a: Word processors
b: Text editors
c: Search engines
d: Natural language processing

2: Web Development:
a: HTML, CSS, and JavaScript
b: Web frameworks
c: Web servers

3: Database Systems:
a: Storing and querying textual data
b: Data mining and analysis

4: Operating Systems:
a: Command-line interfaces
b: File systems
c: User interfaces

5: Game Development:
a: Dialogue and story elements
b: User input and output

2: String Operations:
Write code to perform the following operations on strings:
1: Concatenation
2: Length determination
3: Substring extraction
4: Searching for a substring
5: Reversing a string
6: Counting occurrences of a character in a string

Code:
#include <iostream>
#include <algorithm>
using namespace std;

void Concate();
void Length();
void substring();
void search_substring();
void reverse();
void count_char();

int main(){
int n;
cout << "Enter ur choice:\n1 for Concatenation\n2 for Length determination\n"
<< "3 for Substring extraction\n4 for Searching for a substring\n"
<< "5 for Reversing a string\n6 for Counting no. of a character in a string"
<< "\n7 for Exit\n";
cin >> n;
if (n == 1){
Concate();
} else if (n == 2){
Length();
} else if (n == 3){
 substring();
} else if (n == 4){
search_substring();
} else if (n == 5){
reverse();
} else if (n == 6){
count_char();
} else if (n == 7){
cout << "Exit";
return 0;
}
cout << "\nDo U wanna try other choices!!";
return 0;
}

void Concate(){
string str1 = "Kamal";
string str2 = "Shah";
string str3 = str1 + str2;
cout << "The Concatenated String is:" << str3;
}

void Length(){
string str = "Kamal Shah";
int str_length = str.length();
 cout << "The str string length is:" << str_length;
}

void substring(){
string original = "Kamal Shah";
string sub_str = original.substr(6,4);
cout << "The Substring is:" << sub_str;
}

void search_substring(){
string str = "Kamal Shah";
string substr = "Shah";
int found = str.find(substr);
if (found == -1){
cout << "The substring is not Present in a String";
} else {
cout << "The substring is present at indux:" << found;
}
}

void reverse(){
string str = "Bachah";
reverse(str.begin(), str.end());
cout << "Reversing the string:" << str;
}
void count_char(){
string str = "Kamal Shah";
char to_search = 'a';
int presence = 0;
for (int i = 0; i < str.length(); i++){
if (str[i] == to_search){
presence++;
}
}
cout << "The Character is present " << presence << " time in a String";
}

Output:
Explain the time complexity of each operation and analyze the
efficiency of the algorithms used?
1: Concate():

Operation: Concatenates two strings using + operator.

Time Complexity: Concatenation of two strings of lengths m and n takes
O(m+n) because a new string is created and each character from both strings is
copied.

Efficiency: Efficient for small strings but the operation becomes costly for larger
strings due to the need to create a new string.

2: Length():

Operation: Determines the length of a string using .length() method.

Time Complexity: O(1) the .length() method typically stores the string length as
metadata and retrieves it directly.

Efficiency: Highly efficient as it operates in constant time.

3: Substring():

Operation: Extracts a substring using .substr(start, length).

Time Complexity: O(k) where k is the length of the substring being extracted &
the operation copies k characters into a new string.

Efficiency: Efficient for small substrings but may become slower for very large
substrings.

4: Searching substring():

Operation: Searches for the first occurrence of a substring using .find().

Time Complexity:
Worst case: O(m⋅n) where m is the length of the main string and n is the length of
the substring.
Average case: Depending on the implementation it could be reduced to O(m+n)
using efficient string-search algorithms like Knuth-Morris-Pratt (KMP).

Efficiency: Not ideal for very large strings.

5: Reverse():

Operation: Reverses a string using reverse() from <algorithm>.

Time Complexity: O(n) where n is the length of the string & reverse() function
swaps elements in place iterating half the string length.

Efficiency: Efficient as it performs in-place swapping without additional memory

allocation.

6: Counting characters in a string():

Operation: Counts occurrences of a specific character in the string.

Time Complexity: O(n) where n is the length of the string. The function iterates
through the entire string, comparing each character.

Efficiency: Efficient for moderate sized strings but could be optimized for larger
datasets by using frequency tables.

3: Memory Representation of Strings:

a: Describe how strings are represented in computer memory?
Strings in computer memory are represented as contiguous blocks of memory, with
each character occupying one or more bytes. Strings are of two types;
Null-Terminated Strings:
Characters are stored sequentially in memory, ending with a special null character
(\0) to denote the end of the string.

Length-Prefixed Strings:
The first part of the memory stores the string's length followed by the characters.

b: Discuss the concepts of string literals and dynamic memory

allocation for strings?
1: String Literals:

String literals are fixed strings embedded directly in the program binary during
compilation. String literals are immutable in many programming languages to ensure
safety.
Example:
‘Hello’ is stored in read-only memory and its address is returned when used in code.

2: Dynamic Memory Allocation:

Strings can be allocated in the heap at runtime, allowing flexibility for variable-
length strings. Requires explicit allocation (new in C++ or malloc() in C) and
deallocation (delete).
Example:
char* my_string = (char*) malloc (20 * sizeof(char));
strcpy(my_string, "Dynamic String");
free(my_string);

c: Explain the advantages and disadvantages of different string

representation methods such as null-terminated strings and length-
prefixed strings.
Null-Terminated Strings: Characters are stored sequentially in memory and
terminated by \0.
Advantages:
Simple to implement & interoperable with C-style string handling functions like
strlen() & strcpy() etc.
Disadvantages:
a: Performance: Traversing the string requires finding the null character, leading to
O(n) operations for length determination.
b: Error-Prone: Forgetting the null terminator can lead to undefined behavior.
c: Wasteful: Strings that require frequent modifications are inefficient due to
repeated memory allocations.

Length-Prefixed Strings: The first part of memory contains the length of the
string, followed by the actual characters.
Advantages:
a: Efficiency: Length is known instantly (O(1)).
b: Safety: Easier to avoid buffer overflows since length is explicitly stored.
Disadvantages:
a: Compatibility: Cannot be used directly with C-style string functions.
b: Overhead: Additional space is required to store the length.

4: Practical Applications:
a: Choose a real-world application of strings in computer science (e.g.,
text processing, searching algorithms, or data compression) and explain
how strings are used in that context?

Searching Algorithms: In searching algorithms strings are used to find patterns

or substrings within larger texts. This application is crucial in areas like;
a: Search Engines:
Search engines use string searching to match user queries against a database of web
pages.
b: DNA Sequence Analysis:
In bioinformatics, string algorithms help find gene patterns in DNA sequences.
c: Plagiarism Detection:
String matching detects similarities between documents.
d: Spam Filtering:
Email content is analyzed for specific patterns to identify spam.
Examples:
1: In DNA analysis, locating "AGCT" in a genome is another example of string
usage.

b. Discuss any data structure choices that can enhance the performance
of string related operations in the selected application?
The performance of string searching operations can be greatly improved using
specialized data structures. Some common choices are;

a: Suffix Trees: A tree-like structure representing all suffixes of a string.

Advantages:
1: Efficient for pattern matching (O(m) where m is the length of the pattern).
2: Useful for multiple string operations like longest repeated substring & LCS etc.
Drawbacks:
1: High space complexity (O(n^2) in the worst case for naive implementations).

b: Suffix Arrays: An array of all suffixes of a string, sorted lexicographically.

Advantages:
1: Space-efficient compared to suffix trees.
2: Supports pattern searching using binary search (O(m⋅logn)).
Drawbacks:
1: Slower than suffix trees for some operations.

c: Trie (Prefix Tree): A tree where each node represents a character of a string,
with paths forming words or prefixes.
Advantages:
1: Efficient for prefix searches.
2: Space-efficient for storing a dictionary of strings.
Drawbacks:
1: Slower for suffix operations compared to suffix trees.

d: Hash Tables: Use hash functions to map substrings to unique keys.

Advantages:
1: Fast average-case lookup time (O(1)).
2: Useful for checking if a substring exists in a dataset.
Drawbacks:
1: Collisions can degrade performance.