Question $4(20)$ : The following are ten true$/$false questions, with no explanation needed or wanted, no partial credit for wrong answers, and no penalty for guessing.

$($a$)$ The Peano Axioms for the naturals imply that every natural has a unique predecessor.

$($b$)$ Let $P(n)$ be a predicate on naturals. If we assume $P(n)$ for an arbitrary $n,$ and prove $P(n+1),$ we may conclude that $P(n)$ is true for all naturals $n.$

$($c$)$ A palindrome is a string that is equal to its own reversal. If the strings $u$ and $v$ are palindromes, then the string $uv{u}^R$ is a palindrome $($where $u^R$ is the reversal of $u).$

$($d$)$ Any square $n$ by $n$ chessboard, with any one square removed, can be tiled with L$-$shaped trominoes $($the L$-$shaped pieces we used in Section $4\mathrm{.}11).$

$($e$)$ An undirected tree with $n$ nodes must have exactly $n$ edges.

$($f$)$ Every directed acyclic graph has the property that there can never be two different paths from one node to another.

$($g$)$ Let $G$ be a directed acyclic graph $($with finitely many nodes$)$ and let $x$ be a node in $G.$ Consider either a DFS or a BFS from $x,$ without a closed list or other means to prevent multiple visits to the same node. Then the BFS will terminate with either success or failure, but this is not necessarily true for the DFS$.$

$($h$)$ In a DFS tree of a directed graph, every edge is either a tree edge or a back edge.

$($i$)$ In the BFS tree of a directed graph, every directed edge from a node at level i must go to nodes that are in one of the levels $i-1,i,$ or $i+1.$

$($j$)$ Consider a uniform$-$cost search with start node $s$ and goal node $g,$ where there is a path from $s$ to $g,$ and $d$ is the length of the shortest path. Let $x$ be a node such that there is no path from $s$ to $x$ of length $d.$ Then $x$ will not come off of the priority queur before the search concludes.