Exercise set IV

Note: Students are encouraged to solve as many problems from this set as possible. Some of these will be solved during the lectures, if time permits. We have made attempts to classify the problems based on the difficulty level of solving them. An unmarked exercise is of low to moderate difficulty. Harder problems are marked by H, H² and H³ meaning "just hard", "quite hard" and "very hard" respectively. Exercises marked by M have mathematical flavor (as opposed to computational). One requires elementary knowledge of number theory or algebra or geometry or combinatorics in order to solve these mathematical exercises.

1. Rewrite the dynamic linked list implementations of the ordered list, stack and queue ADTs incorporating the feature that whenever a node is deleted, the memory allocated to that node is freed.

2. Implement the ordered list, stack and queue ADTs with dynamic linked lists but without using the dummy nodes at the beginning of the lists.

3. Dynamic arrays may be used to provide a third implementation of ordered list, stack and queue ADTs. Here the array holding the list is to be allocated memory dynamically depending on the size of the list. Implement the ADTs using dynamic arrays.

4. Implement the ordered list ADT using doubly linked lists. (Recall from Exercise set III that in a doubly linked list each node maintains two pointers, one pointing to the next node in the list, the other to the previous node in the list.)

5. Write a function that takes as arguments two sorted linked lists and outputs a sorted linked list obtained by merging the two input lists.

6. Think of the ordered list ADT modified using the following strategy. Whenever an element is located using the isPresent() operation, that particular element is deleted from the current position and reinserted at the beginning of the list. The motivation behind this relocation is that in many situations an element accessed in a list is expected with high probability to be accessed several times in the future. So keeping the element near the beginning of the list reduces average search time. Modify the ordered list ADT implementations to incorporate this modification.

7. Consider the ADT set that represents a collection of integers. The ADT should support standard set operations:

      S = init();
         /* Initialize S to the empty set */
   
      isEmpty(S);
         /* Return true if and only if S is the empty set */
   
      isSingleton(S);
         /* Return true if and only if S contains only one element */
   
      isMember(S,a);
         /* Return true if and only if a is a member of the set S */
   
      S = addElement(S,a);
         /* Add the element a to the set S. If a is already in S,
            there will be no change, else a new element is to be inserted. */
   
      S = delElement(S,a);
         /* Remove the element a from the set S. No change if a is not
            a member of S. */
   
      S = union(U,V);
         /* Assign to S the union of the sets U and V */
   
      S = intersection(U,V);
         /* Assign to S the intersection of the sets U and V */
   
      S = difference(U,V);
         /* Assign to S the set difference U - V */
   
      S = symmDiff(U,V);
         /* Assign to S the symmetric difference (U - V) union (V - U) */
   
      print(S);
         /* Print the elements of the set S */
   
      printSorted(S);
         /* Print the elements of the set S in the sorted order. */
   

   1. Implement the set ADT using static arrays.
   2. Implement the set ADT using dynamic arrays.
   3. Implement the set ADT using linked lists.

8. A multiset is like a set with the exception that each member of the set may be present multiple times. For example, an aquarium is a multiset specified by the different species of fish it contains and by the number of fish in the aquarium belonging to each such species. For this exercise, concentrate on multisets of integers (because integers are less fishy). The multiset ADT should support the following operations.

      S = init();
         /* Initialize S to the empty multiset */
   
      isMember(S,a);
         /* Return true if and only if a is a member of the multiset S */
   
      count(S,a);
         /* Return the number of occurrences of a in the multiset S */
   
      S = addElement(S,a,n);
         /* Add n occurrences of a to the multiset S */
   
      S = delElement(S,a,n);
         /* Delete n occurrences of a from the multiset S. If S contains
            less than n occurrences of a, only those many that are present
            in S need be deleted. */
   
      S = union(U,V);
         /* Assign to S the union of the multisets U and V. If U and V
            respectively contain m and n occurrences of a, then their
            union would contain m+n occurrences of a. */
   
      S = intersection(U,V);
         /* Assign to S the difference of the multisets U and V. If U and V
            respectively contain m and n occurrences of a, then their
            intersection would contain min(m,n) occurrences of a. */
   
      S = difference(U,V);
         /* Assign to S the difference U - V. If U and V respectively
            contain m and n occurrences of a, then their difference would
            contain max(m-n,0) occurrences of a. */
   
      print(S);
         /* Print all the elements of S with positive multiplicities. Also
            print the corresponding multiplicities. */
   
      printSorted(S);
         /* Same as print(S) except that the elements are printed in the
            sorted order. */
   

   1. Implement the multiset ADT using static arrays.
   2. Implement the multiset ADT using dynamic arrays.
   3. Implement the multiset ADT using linked lists.

9. [H] A nested ordered list of integers is recursively defined as follows:

      The empty tuple () is a nested list.
      If A0,A1,...,An-1 are nested lists or integers for some n >= 1,
         then (A0,A1,...,An-1) is again a nested list.
   

   Here are some examples:

      ()
      (3,4,5)
      ((),3,(),(4),5)
      (3,(4),((5),(),(6,7,(8))),((9),()))
   

   A nested list should support the following functions:

      L = init(); 
         /* Initialize the nested list L to the empty list */
   
      isEmpty(L);
         /* Returns true if and only if L is the empty list */
   
      L = insertInt(U,a,k);
         /* If U = (U0,U1,...,Um-1) is a list and a an integer, then assign to L the
            nested list (U0,U1,...,Uk-1,a,Uk,...,Um-1). Report error if k > m. */
   
      L = insertList(U,V,k);
         /* If U = (U0,U1,...,Um-1) is a list and V a nested list, then assign to L the
            nested list (U0,U1,...,Uk-1,V,Uk,...,Um-1). Report error if k > m. */
   
      L = join(U,V);
         /* If U = (U0,U1,...,Um-1) and V = (V0,V1,...,Vn-1) are nested lists,
            assign to L the nested list (U0,U1,...,Um-1,V0,V1,...,Vn-1). */
   
      L = joinAt(U,V,k);
         /* If U = (U0,U1,...,Um-1) and V = (V0,V1,...,Vn-1) are nested lists,
            assign to L the nested list (U0,U1,...,Uk-1,V0,V1,...,Vn-1,Uk,...,Um-1).
            Report error if k > m. */
   
      L = delete(U,k);
         /* If U = (U0,U1,...,Um-1) is a nested list, assign to L the nested list
            (U0,U1,...,Uk-1,Uk+1,...,Um-1). Report error if k >= m. */
   
      L = sublist(U,k,l);
         /* If U = (U0,U1,...,Um-1) is a nested list, return the sub-list (Uk,...,Ul).
            Report error for improper indices k,l. */
   
      print(L);
         /* Print the nested list L as a fully parenthesized expression. */
   

10. Implement the (univariate) polynomial ADT with all standard arithmetic operations on polynomials. First mention the prototypes of the ADT functions and then implement. Use dynamic memory management to implement the list of coefficients.

11. A multivariate polynomial in n variables X₁,...,X_n is a finite sum of terms of the form aX₁^e₁,...,X_n^e_n, with each e_i being a non-negative integer and with the coefficient a being an integer. Arithmetic operations on a multivariate polynomial are carried out following standard rules.
    1. Write the ADT functions for polynomials. Include standard arithmetic operations and partial derivatives.
    2. Assume that the number of variables is small, like 2 or 3. Implement the ADT using static multi-dimensional arrays to store the coefficients.
    3. Also implement the ADT using dynamic multi-dimensional arrays to store the coefficients.
    4. [H] Each term in a multivariate polynomial is identified by the coefficient and the exponents. For example, the term aX₁^e₁,...,X_n^e_n is determined by the tuple (a,e₁,...,e_n). So a structure capable of storing n+1 fields suffices to store a term, and a polynomial is an array of such structures. Use this strategy to implement the polynomial ADT. You should think of a way to order the exponent tuples (e₁,...,e_n) and store the terms sorted under this ordering.
    5. [H²] An n-variate polynomial can be thought of as a univariate polynomial whose coefficients are (n-1)-variate polynomials. This recursive definition provides us with yet another handle for implementing the polynomial ADT. Use a nested linked list structure for a concrete recursive realization of the multivariate polynomial ADT.

12. Suppose you want to implement two stacks in a single array. Two possibilities are outlined here:

    Odd-even strategy: Stack 1 uses locations 0,2,4,... of the array, whereas Stack 2 uses the array locations 1,3,5,...

    Colliding strategy: The two stacks start from the two ends of the array and grow in opposite directions (towards one another).

    Implement both the strategies. Write two sets of initialize, push and pop functions.

13. Write a function that uses the stack ADT calls in order to reverse a character string.

14. [M] Suppose that you have a stack and push to the stack the integers 1,2,...,n in that sequence. In between these push operations you also invoke some pop operations in such a way that a pop request is never sent to an empty stack. Immediately before each pop operation you also print the top of the stack. After all of the integers 1,2,...,n are pushed, the elements remaining in the stack are printed and popped resulting in an eventually empty stack. The printed integers form a permutation of the integers 1,2,...,n. An example is given below for n = 5:

       S = init();
       S = push(S,1);
       S = push(S,2);
       print top(S);
       S = pop(S);
       S = push(S,3);
       S = push(S,4);
       print top(S);
       S = pop(S);
       print top(S);
       S = pop(S);
       S = push(S,5);
       print top(S);
       S = pop(S);
       print top(S);
       S = pop(S);
    

    This sequence prints the permutation:

       2,4,3,5,1
    

    Prove or disprove: All permutations of 1,2,...,n can be generated by a suitable sequence of such push and pop operations.

15. Use stack ADT calls to recognize strings with balanced parentheses. Examples of such strings: (), ((())), ()()(), ()(()(()(()()))). Non-examples: ((), (()(()))), )()(.

16. Use stack ADT calls to recognize strings with balanced parentheses and square brackets. Examples of such strings: (), ([()]), []()[], ()[()(()[()()])]. Non-examples: (], (()[)()), ([], [()[[]]]), ]()[.

17. [HM] The usual infix notation for writing arithmetic expressions requires parentheses in order to specify the exact sequence of operations. For example, 2+3x4 refers to 2+(3x4). If we want to do the addition first and then the multiplication, we must put explicit parentheses like (2+3)x4. The postfix notation for 2+(3x4) is 2 3 4 x + and that for (2+3)x4 is 2 3 + 4 x. In the postfix notation we do not require parentheses and still the meaning (i.e., the exact sequence of operations) is uniquely determined by the expression. In the rest of this exercise you are asked to prove this property of the postfix notation. The result continues to hold for any mix of binary, unary, ternary, ... operators. In this exercise, assume for the sake of simplicity that all operators are binary. An arithmetic expression contains operands and operators. A token is either an operator or an operand. Prove the following assertions:
    1. An arithmetic expression (involving binary operations only) contains an odd number of tokens.
    2. A postfix expression starts with an operand and ends with an operator provided that it is of length bigger than 1.
    3. A postfix expression with (exactly) 2m+1 tokens has m operators and m+1 operands.
    4. For any postfix expression and any position in the expression, the number of operands to the left of the position is strictly larger than the number of operators to the left of the same position.
    5. No proper suffix of a valid postfix expression is again a valid postfix expression.
    6. Let op be the last token (an operator) in a postfix expression with more than one tokens. Then the expression looks like arg1 arg2 op, where arg1 and arg2 are the two arguments for op and are again valid postfix expressions. The arguments arg1 and arg2 can be uniquely identified from the original postfix expression.

18. Write a function that takes a fully parenthesized arithmetic expression in the infix notation as the input and outputs the value of the expression. You may restrict only to binary operations (+,-,*,/,%). You may also assume that all operands are integers.

    In order to evaluate a parenthesized arithmetic expression in the infix notation, one may use a stack. A token in such an expression is either an operand (an integer) or an operator (+,- etc.) or the left parenthesis or the right parenthesis. One starts with an empty stack and reads the input string from left to right. Once a token other than the right parenthesis is read from the input, the token is pushed to the stack. When a right parenthesis is encountered, pop operations are performed until a left parenthesis is popped out. The tokens (excluding the parentheses) that are popped out form a simple (sub)expression (either a single integer or two integers separated by an operation). Evaluate that sub-expression and push the value back to the stack. When the entire input is read, the stack should contain a single integer which is the value of the input expression.

19. Suppose you have the stock prices p₁,...,p_n of a company for n consecutive days. The span of day i is the maximum number of consecutive days (starting at and including day i) over which the stock price p_i remains maximum. For example, for the stock prices 5,4,3,3,4,2,6,3 on 8 days, the respective spans are 6,5,2,1,2,1,2,1. Use stack ADT calls to compute the span of each day.

20. Suppose that you have an mxn maze of rooms. Each adjacent pair of rooms has a door that allows passage between the rooms. At some point of time some of the doors are locked, the rest are open. A mouse sits at room number (s,t) and there is fabulous food for the mouse at room number (u,v). Your task is to determine whether there exists a route for the mouse from room (s,t) to room (u,v) through the open doors. The idea is to start a search at room no (s,t), then investigate rooms (s₁,t₁),...,(s_k,t_k) that can be reached from (s,t) and then those rooms that can be reached from each (s_i,t_i), and so on. There is no need to revisit a room during the search. Maintain an mxn array of flags in order to keep track of the rooms that are visited.
    1. [Depth-first search] Use a stack to implement the search. Initially push (s,t) to the empty stack. Subsequently, as long as the stack is not empty, consider the room (x,y) at the top of the stack. If (x,y) has a yet unvisited neighboring room, push that room at the top of the stack. If (x,y) does not have an unvisited neighboring room, pop (x,y) out of the stack. If during these operations, the desired room (u,v) ever appears at (the top of) the stack, then a route from (s,t) to (u,v) is detected. If the search completes (i.e., the stack becomes empty) without ever having (u,v) in the stack, then there is no (s,t)-(u,v) path.
    2. [Breadth-first search] Implement the search using a queue. Maintain a queue of rooms to search from. Initially enqueue (s,t) to an empty queue. Subsequently, as long as the queue is not empty, look at the room (x,y) at the front of the queue. If (x,y) = (u,v), then report success and return. Else dequeue (x,y) from the front and enqueue all unvisited neighboring rooms at the back of the queue. If the search stops (i.e., the queue becomes empty) without ever having (u,v) at the front of the queue, report failure.
    3. [Random walk] Also implement a memoryless version of the search. Your program does not have to remember what rooms have already been visited by the mouse. The mouse would instead randomly select one of the open doors for going to an adjacent room (which may be visited earlier). If there is no (s,t)-(u,v) path, then whatever random sequence of movements the mouse makes, it can never reach the room (u,v). On the other hand, if there exists an (s,t)-(u,v) path, the mouse would eventually reach the desired room (u,v) with high probability. However, in this case there remains a chance that the room selection of the mouse is so bad that it misses a desired path for ever. The probability that this awkward incident happens decreases considerably with the number of moves. Since your program has to run for a finite time, you cannot obviously wait for an indefinitely long exploration by the mouse. Assume instead that the mouse dies of hunger and exhaustion, after it makes million room changes without ever reaching the food at room (u,v).
    4. Prepare some configurations of the rooms for which there actually exist (s,t)-(u,v) path(s). Run the above three algorithms on these configurations and compare the numbers of room changes that the mouse makes under the three different strategies in order to reach room (u,v).

21. Use queue ADT calls to implement round-robin scheduling as exemplified in this animation.

22. Write a function making suitable stack and queue ADT calls to solve each of the following problems:
    1. Given a string, check if it is of the form w#w, where w is a string with alphanumeric characters only.
    2. Given a string, check if it is of the form ww, where w is a string with alphanumeric characters only.
    3. Given a string, check if it is of the form w#w^r, where w is a string with alphanumeric characters only, and where w^r stands for the reverse of the string w.
    4. Given a string, check if it is of the form ww^r, where w is a string with alphanumeric characters only.
    5. Given a string, check if it is a palindrome.

23. A double-ended queue is a queue with the exception that it supports insertion and deletion at both the ends. Each insert/delete operation must specify the end at which the operation is to be performed. Implement initialization, insertion and deletion functions on a double-ended queue using:
    1. Static arrays
    2. Dynamic arrays
    3. Linked lists
    4. Doubly linked lists

---

Course home