Week 4: List-based ADTs (cont'd)
---------------------------------

This week, we studied stacks.
- definition
- properties: LIFO
- operations: pop, push, top, is-empty

We reviewed the following problems that can be solved using stacks:

1. let L be the language of all strings made of "(" and ")" that are well-formed.
	e.g., the string )( is not part of L, but () is
	      similarly, ())( is not part of L, not ())((), but ((())) is, as is (()())
  objective: design an algorithm that, given a string, decides whether this string is part of L
	or not.
  using a stack: each time you read a "(" you push it into the stack.
                 each time you read a ")" you pop the top of the stack (i.e., a "(").
  prove that this algorithm recognize all words from L, and only words of L

2. let L' be the language of all strings made of "(" and ")" such that the number of "(" is
	equal to the number of ")"
	e.g., the string )( is part of L' while ()) is not.
  objective: design an algorithm that, given a string, decides whether this string is part of L
	or not.
  using a stack S: each time you read a "(", if top(S)=")", then pop(S)
							    otherwise push("(",S)
		   each time you read a ")", if top(S)="(", then pop(S)
							    otherwise push(")",S)
  prove that this algorithm recognize all words from L, and only words of L

3. evaluation of arithmetic expressions:
	- definition of post-fix forms
	- how to use a stack to evaluate post-fix expressions
	- what if the expression is in in-fix form:
		* either you convert it to post-fix: cf. algo/recursive function presented
		  in class
		* or evaluation using a recursive function
	- expression trees:
		* how are they related to infix, prefix and postfix forms?
		* how are expressions evaluated when represented as trees?

4. depth-first search (DFS) is implemented using a stack: why?
   how DFS is related to constraint/problem solving? (naive version)


===============================================================
Friday session will be dedicated to reviewing all material covered in class so far.
This is a review session to get ready for the mid-term.