CSC 341 (Fall 2021)

Lab: Time Complexity

\[ \newcommand{\desc}[1]{\langle #1 \rangle} \]

Problem 1: Representation

For each of the following objects, describe a plausible representation for those objects as strings.

  1. An undirected graph \(G\).
  2. A finite collection of objects \(O_1, \ldots, O_n\), weights for each object \(w_i\), and costs for each object \(c_i\).
  3. An assignment of truth values to a finite collection of boolean variables \(x_1, \ldots, x_k\).
  4. A Turing machine configuration \(C\).
  5. A deterministic finite automata \(D\).

Problem 2: Poly Want A Cracker

Show that each of the following languages are in \(P\).