CSC 320: Summer 2017 Tutorial #2, Tues. May 16, 1:30pm or 2:30pm

Learning Objectives:

The goals of this tutorial are:

1. A review of Big Oh notation. This material is critical for success in CSC 320 and should have been learned in CSC 225.
2. Please also bring any other questions you have about the course material.

Tutorial Part 1: Time Complexity

For the following questions, assume that G is an undirected graph having n vertices. The vertices of G are numbered 0, 1, 2, ..., n-1. The graph H= G-v is the same as the graph G except that vertex v and all edges incident to v are deleted.

1. Give the time complexity using Big Oh notation of this code segment:

   for (i= 0; i < n; i++)
   {
        for (j=i+1; j < n; j++)
        {
            for (k= j+1; k < n; k++)
            {
                Take an adjacency matrix for G and make
                an adjacency matrix for H= G -i -j -k 
                (i, j, and k are vertices of G).
            }
        }
   }
   

2. Consider:

   for (i= 0; i < n; i++)
   {
        for (j=i+1; j < n; j++)
        {
            for (k= j+1; k < n; k++)
            {
                 Call a function compute_parameter(G) which has 
                 time complexity O(f(n)) where n is the number of
                 vertices of G.
            }
        }
   }
   

   
   (a) Express the time complexity of this code in terms of f(n).
   (b) What is the time complexity when f(n) is O(1)?
   (c) What is the time complexity when f(n) is O(n^3)?
   (d) What is the time complexity when f(n) is O(2^n)?

3. for (i= 0; i < n; i++)
   {
        for (j=i+1; j < n; j++)
        {
            for (k= j+1; k < n; k++)
            {
                Take an adjacency matrix for G and make
                an adjacency matrix for H= G -i -j -k 
                (i, j, and k are vertices of G).
                Call compute_parameter(H) 
            }
        }
   }
   

   What is the time complexity of this code assuming that the time for compute_parameter is in O(f(n)) for some function f(n)?

4. The definition of Big Oh is that for functions f and g which map the natural numbers to non-negative real values, the function f(n) is in O(g(n)) if there exists constants c > 0 and n₀ >= 0 such that for all n >= n₀, f(n) <= c * g(n). Use this definition to prove that the polynomial a₀ x⁰ + a₁ x¹ + a₂ x² ... + a_k x^k is in O(x ^k), when a_i >= 0 for all i= 0, 1, 2, ..., k.

Part 2: Other questions

1. Prove that the set S= { L : L is a language over {0,1}^*} is not countable.