Strings Theoretical Practice

Solved Questions

1. Let W be the string ABCD.
   (a) Find the length of W.
   (b) List all substrings of W.
   (c) List all the initial substrings of W.

   (a) The number of characters in W is its length, so 4 is the length of 
   W.
   
   (b) Any subsequence of characters of W is a substring of W. There are 
   11 such substrings:
   
       Substrings: ABCD,  ABC, BCD,  AB, BC, CD,  A, B, C, D,  Λ
       Lengths:    4      3          2          1          0
       
       (Here Λ denotes the empty string.)
   
   (c) The initial substrings are ABCD, ABC, AB, A, Λ; that is, both the 
   empty string and those substrings that begin with A.
   

2. Assuming a programming language uses at least 48 characters (26 letters, 10 digits, and 12 special characters), give the minimum number and the usual number of bits to represent a character in memory.

   To solve this, we need to find the smallest number of bits that can 
   represent at least 48 different characters.
   
   1.  Understanding Bits:** Bits work in powers of 2.
       - 1 bit can represent 2^1 = 2 characters.
       - 2 bits can represent 2^2 = 4 characters.
       - 3 bits can represent 2^3 = 8 characters.
       - 4 bits can represent 2^4 = 16 characters.
       - 5 bits can represent 2^5 = 32 characters. (Not enough for 48)
       - 6 bits can represent 2^6 = 64 characters. (This is enough!)
   
   2.  Minimum Number of Bits:
       Since 5 bits is not enough, the minimum number of bits required is
       6.
   
   3.  Usual Number of Bits:
       In practice, computers commonly use standard sizes. 
       - ASCII uses a 7-bit code, which can represent 128 characters.
       - EBCDIC and modern standards like UTF-8 use an 8-bit code 
       (which is 1 byte), allowing for 256 or even more characters. This
        provides room for many more symbols and is more efficient for 
        computer hardware to handle.
   

3. Describe briefly the three types of structures used for storing strings.

   There are three common ways to store strings in computer memory:
   
   (a) Fixed-Length Storage:
       - A specific, fixed amount of memory is allocated for every 
       string, for example, 80 characters.
       - If a string is shorter than the allocated space (e.g., "hello" 
       in an 80-character space), the rest of the space is padded with
        a special null character or spaces.
       - If a string is longer, it gets cut off (truncated).
       - Pro: Simple and predictable. Con: Wastes memory for short strings.
   
   (b) Variable-Length Storage (with fixed maximums):
       - Similar to fixed-length, a maximum size is allocated for each
        string.
       - However, it also stores the actual length of the string 
       separately (e.g., as the first byte).
       - This avoids the need to scan for a null character to find the 
       end of the string.
       - Pro: More memory efficient than fixed-length. Con: Still has 
       a maximum size limit.
   
   (c) Linked-List Storage:
       - The string is broken into pieces. Each piece is a "node" 
       containing
        a character (or a few characters) and a pointer to the memory 
        address of the next node.
       - The string is stored as a chain of these nodes.
       - Pro: Very flexible with string length and doesn't waste space. 
       Con: 
       Slower to access characters in the middle of the string because you
        have to follow the chain.
   

4. Give some (a) advantages and (b) disadvantages of using linked storage for storing strings.

   Using a linked list to store a string, where each node holds a character, has specific trade-offs compared to using a contiguous array.
   
   Advantages:
   
   1. Dynamic Size: Linked lists can easily grow and shrink. You don't need to define the string's maximum length beforehand. This is very memory-efficient for strings of varying or unknown lengths.
   
   2. Efficient Insertions and Deletions: Adding or removing a character or substring in the middle of a string is very fast. It only requires updating a few pointers (links), without the need to shift subsequent characters as you would in an array.
   
   3. Easy Concatenation: Joining two strings (concatenation) is highly efficient. You can simply point the last node of the first string to the first node of the second string.
   
   Disadvantages:
   
   1. Memory Overhead: Each node in the linked list needs extra space to store a pointer to the next node. For single characters, this overhead can be significant, potentially doubling the memory usage compared to an array.
   
   2. No Direct (Random) Access: To access the character at a specific position (e.g., the 10th character), you must traverse the list from the beginning. This makes indexed access slow (O(n) complexity), whereas arrays offer constant time (O(1)) access.
   
   3. Poor Cache Performance: The nodes of a linked list can be scattered throughout memory. This lack of contiguous storage leads to poor cache locality, which can make traversing the list slower in practice than traversing a compact array.