What is the difference between user_is_anonymous() and user_is_logged_in()? What is the difference between the two functions? When should one be used instead of the other?
The functions are essentially opposites.

The only real difference is the user_is_anonymous() function has an additional check for $GLOBALS['menu_admin'] to allow menu admins to be able to administer menu links that are visible to anonymous users only.

It's used by drupal_valid_path() as well as the menu_overview_form() function:

function drupal_valid_path($path, $dynamic_allowed = FALSE) {
  global $menu_admin;
  // We indicate that a menu administrator is running the menu access check.
  $menu_admin = TRUE;
  if ($path == '&lt;front&gt;' || url_is_external($path)) {
    $item = array('access' =&gt; TRUE);
  }
  elseif ($dynamic_allowed &amp;&amp; preg_match('/\/\%/', $path)) {
    // Path is dynamic (ie 'user/%'), so check directly against menu_router table.
    if ($item = db_query("SELECT * FROM {menu_router} where path = :path", array(':path' =&gt; $path))-&gt;fetchAssoc()) {
      $item['link_path']  = $form_item['link_path'];
      $item['link_title'] = $form_item['link_title'];
      $item['external']   = FALSE;
      $item['options'] = '';
      _menu_link_translate($item);
    }
  }
  else {
    $item = menu_get_item($path);
  }
  $menu_admin = FALSE;
  return $item &amp;&amp; $item['access'];
}