HWx4 Concepts

Focused on Permall and nested parentheses

Nested Parentheses: determining validity of pairs

Think: a combination of stack and do-undo

for every left parenthesis, “do“ and add it onto the stack. for every right parenthesis, remove a left parenthesis from stack to “undo“ and complete a pair. by the end, the stack should be empty like it initially was.

What is the equivalence between do-undo and Permall?

The idea of do-undo is: what goes in comes out as everything is undone by inverses

In order to maintain the combination, Permall requires an “undo” to counter unnecessary rearrangement done

Permall Visualization

root signifying start. its consists of n children, which each have n-1 children, W.E.H n-2 children…….

hence: each path is a new permutation, leading to n! paths

Permall: Caution for Error

Think: we are being asked to do a swap. what is the undo of a swap? the same swap

Why: when recursively called we cannot be sure the order of Buffer is maintained

Nested Parentheses: tree to list

think: preorder printing of left parentheses, postorder printing of right parentheses

Nested Parentheses: list to tree

think: for each left parentheses, a node is created and the following must be a child aka preorder traversal

for each right parentheses a node’s sibling is created, aka the parent node has a new child aka postorder traversal