Exercises - Sums and Products - First Set

1. What does the notation $\sum_{i \leq j \leq n}a_j$ mean if $n=3.14$? This is equivalent to when $n=3$.
2. Without using $\sum$ notation, write out the equivalent of

Exercises - Permutations and Factorials

1. How many ways are there to shuffle a 52-card deck? 52!.
2. In the

Exercises - Binomial Coefficients

2.3: Trees

Define: Formally, a tree is a finite set T of one or more nodes such that a) there is one specially designated node called the root of the tree, root(T) b) the remaining nodes (excluding the root) are partitioned into $m \geq 0$ disjoint sets $T_1,…,T_m$, and each of these sets in turn is a tree. The trees $T_1,…,T_m$ are called the subtrees of the root.

Binary tree is NOT a specific type of tree, but a different concept entirely. Binary trees can be empty, trees cannot. Why make this distinction?

Ordered: When the order of the subtree matters. Most trees we discuss will be ordered. Oriented: When the order of the subtree doesn’t matter, we only care about the relative orientation of the nodes, not their order.

Exercises - Trees

1. How many different trees are there with three nodes, A, B, and C?

2.2.1 Stacks, Queues, and Dequeues

• The operations we might want to perform on linear lists include, for example, the following:
  • Gain access to the kth node of the list to examine and/or change the contents of its fields.
  • Insert a new node just before or after the kth node.
  • Delete the kth node.
  • Combine two or more linear lists into a single list.
  • Split a linear list into two or more lists.
  • Make a copy of a linear list.
  • Determine the number of nodes in a list.
  • Sort the nodes of the list into ascending order based on certain fields of the nodes.
  • Search the list for the occurence of a node with a particular value in some field.
• A stack is a linear list for which all insertions and deletions (and usually all accesses) are made at one end of the list.
• A queue is a linear list for which all insertions are made at one end of the list; all deletions (and usually all accesses) are made at the other end.
• A dequeue (“double ended queue”) is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list.

2.2.1 Excercises, Stacks, Queues, and Dequeues

1. An input-restricted dequeue is a linear list in which items may be inserted at one end but removed from either end; clearnly an input-restricted dequeue can operate either as a stack or as a queue, if we consistently remove all items from one of the two ends. Can an output-resticted dequeue also be operated either as a stack or as a queue? We can insert at either end but only remove from one end. Yes, this works as a stack as well as a queue.
2. Imagine four railroad cars positioned on the input side of the track in Fig. 1, numbered 1,2,3, and 4, from left to right. Suppose we perform the following sequence of operations (which is compatible with the direction of the arrows in the diagram and does not require cars to “jump over” other cars): (a) move car 1 into the stack; (b) move car 2 into the stack; (c) move car 2 into the output; (d) move car 3 into the stack; (e) move car 4 into the stack; (f) move car 4 into the output; (g) move car 3 into the output; (h) move car 1 into the output. As a result of these operations the original order of the cars, 1234, has been changed into 2431. It is the purpose of this exercise and the following exercises to examine which permutations are obtainable in such a manner from stacks, queues, and dequeues. If there are six railroad cars numbered 123456, can they be permuted into the order 325641? Can they be permuted into the order 154623? (In case it is possible, show how to do it.)
   • First one, yes, SSXSXXSS
   • Second one, impossible, because it is impossible to get the 2 out of the stack before the three.
3. The operations (a) through (h) in the previous exercise can be much more concisely described by the code SSXSSXXX, where S stands for “move a car from the input into the stack,” and X stand for “move a car fro the stack into the output.” Some sequences of S’s and X’s specify meaningless operations, since there may be no cars available on the specified track; for example, the sequence SXXSSXXS cannot be carried out, since we assume that the stack is initially empty. Let us call a sequence of S’s and S’s admissible if it contains n S’s and n X’s, and if it specifies no operations that cannot be performed. Formualte a rule by which it is easy to distinguish between admissible and inadmissible sequences; show furthermore that no two different admissible sequences give the same output permutation.
   • Keep a running sum of the S’s and X’s. If at any point the number of X’s surpasses the number of S’s, then we know that the sequence is inadmissible.
   • There must’ve been a first operation where the two sequences differed. At this operation, we know that the output permutation must have differed at some point. Thus, one sequence must have been S, and the other must have been X. We know that this will then be an inversion in the final output. 4. Find a simple formula for $a_n$, the number of permutations on $n$ elements that can be obtained with a stack like that in exercise 2. We just need to count the number of admissible sequences of length $n$. This means that we need to find the number of length $2n$ sequences with the same amount of S’s and X’s where at any point, the number of X’s never exceed the number of S’s.