CS447 Study Guide - Midterm Guide: Point4, Dangling Pointer, Valgrind
Document Summary
Question 1 (10 points) (tas in charge: jinqiu yang and taiyue liu) We start by noting that cpc requires that tr contains all paths in g. since g is an acyclic graph, it means that no path in g contains any loops. In other words, a path from any one node to another goes through a node at most once. We then note that by de nition, a prime path is a simple path that does not appear as a proper subpath of any other simple path. We now note that in an acyclic graph, all simple paths are prime paths themselves or are subpaths of one of the prime paths. Therefore, any test set t that satis es ppc cover all simple path. Since all paths in g are simple paths, t also satis es cpc. If you answer no , you are awarded at most 2 points.
