Assignment 1

The following are five programming questions. By the end of the semester you are required to be able to do all of them in at least three different languages. For now, do TWO of them in your favorite language.

1. Write a program that prints a staircase of a given number of steps. For example, here is the output when the number is 4.

   
                         +---+
                         |   |
                     +---+---+
                     |   |   |
                 +---+---+---+
                 |   |   |   |
             +---+---+---+---+
             |   |   |   |   |
             +---+---+---+---+
   

   
   
2. The Kruskal count, discovered by a mathematician named Martin Kruskal, is often used by magicians. Given a sequence of 52 integers between 1 and 10 (originally a deck of 52 playing cards counting ace as 1, and king, queen, or jack as 5), and a starting integer S, also between 1 and 10. The Sth integer in the sequence is called the first key, and its value tells how many integers you must count and proceed to reach the next key. So if the value of the first key is K then the (S+K)th integer in the sequence is the second key. You count this way until you run out of the integers. The last key is your "chosen" key. Let's call a sequence a Kruskal sequence if you reach the same "chosen" key regardless of the starting integer. Write a program to detect if a given sequence is a Kruskall sequence.
   
   
3. Priority queues are useful in many applications. A priority queue consists of several plain queues of different priorities. The enqueue method takes also the priority of the element to be added, and the dequeue method always deletes the element at the head of the non-empty queue with the highest priority. Write a program to implement this data structure.
   
   
4. Given four integers between 1 and 10, write a program to construct an expression which results in 24 when evaluated. The expression must be composed of the four integers and the four operations (+, -, *, and /) with each of given integers occurring exactly once. For example, for the four integers 2, 3, 4, and 6, a possible solution is (3-2)*(4*6).
   
   
5. Consider infix expressions defined by the following CFG:

   
         E -> T | E + T | E - T
         T -> F | T * F | T / F
         F -> a | - F | ( E )
   

   where +, -, *, /, a, (, and ) are terminals. Write a program to convert a given infix expression into postfix.