CS 173: Skills list for Examlet 12

Miscellaneous

• Be familiar with how to write numbers in bases other than 10, particularly base 2 and base 3. (See textbook section 1.6.) We don't plan to ask you to do calculation problems such as converting numbers by hand. Rather, these representations may be used in some automata examples.

String notation and regular expressions

• The empty string (ε)
• Concatenation, *, and | operations
• A^* is the set of all finite-length strings with characters from A.
• Know what a "bit string" is (a string of ones and zeroes)

State Diagrams

• Read basic notation for state diagrams, e.g. state diagrams are directed graphs, states are the vertices, actions are labelled on the edges, how are start and end states marked, loops and multi-edges are possible.
• Know what is/isn't allowed in a deterministic state diagram.
• Trace walks in a state diagram: walks must follow the edge directions, therefore cycles and paths also must follow the edge directions, the full description of a walk contains the state sequence and the action sequence.
• Know the basic description of the transition function δ, i.e. each input is a pair of a state plus an action, each output is a set of possible next states. Remember that this means that the co-domain is the powerset of the set of states.
• Have a general familiarity with some common examples of state diagrams: states of a game or puzzle, memory states of a computer program, phone lattice for a set of words.
• Construct state diagrams that meet a (simple) specification, e.g. a phone lattice that represents a set of words.
• Counting states
  • Calculate (or estimate for large cases) the number of states for an example system (e.g. a game).
  • Know that algorithms can be made more efficient by not creating multiple states with identical properties. Or, said another way, organizing your work so that you don't repeatedly re-solve a sub-problem.

NP

• Know that certain classes of sentences have exponentially many parse trees. (And thus producing all parses of a sentence requires exponential time.)
• Know that the Towers of Hanoi puzzle has been proved to require exponential time.
• Know that NP is the set of problems for which we can quickly (polynomial time) justify "yes" answers.
• Know that co-NP is the set of problems for which we can quickly (polynomial time) justify "no" answers.
• Know that problems in NP can be solved in exponential time, but it's not known whether they can be solved in polynomial time.
• Know what an NP-complete problem is: a problem in NP for which a polynomial-time algorithm would imply that any problem in NP can be solved in polynomial time.
• Know some examples of NP-complete problems: graph colorability, circuit satisfiability (Circuit SAT), propositional logic satisfiability, marker making, the travelling salesman problem.
• Know that you can decide in polynomial time whether a graph is 2-colorable (aka bipartite).