MA-351 Homework 2

Due at 4:59pm in my mailbox in SAS 3151, Tuesday, October 11, 2016


All solutions must be submitted in hardcopy either to me in class or placed in my mailbox. Note my office hours on my schedule.

  1. DMM, §2.3, Problem 1 on page 49 for digraph (b) only.

  2. Consider the m by n grid graph: n vertices in each of m rows, and m vertices in each of n columns arranged as a grid, and edges between neighboring vertices on rows and columns (excluding the wrap-around edges in the toric mesh). There are m n vertices in total.
    1. What is the diameter of this graph?
    2. From the top left vertex to the bottom right vertex, how many shortest paths are there? Please explain.

  3. DMM, §2.4, Problem 11 on page 59.

  4. Draw the binary tree (with tagged left-right children) corresponding to the parenthesis expression (())(()())()()