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

If you feel you need extra help, you are welcome to attend both tutorial sections.

Learning Objectives:

1. To make sure you understand the Hamilton Path/Hamilton Cycle question on Assignment #1.
2. To provide a review of induction. You should have already studied induction in Math 122, and either Math 222 or CSC 225/226.

Do these questions before the tutorial but you do not have to write them up as a formal submission. It's better to have incorrect solutions then to just passively absorb it at the tutorial as this will give you more information as to your strong and weak points.

Tutorial Part 1: Graph Theory Review

Before coming to the tutorial:

1. Read the directions on the assignment for the Hamilton Path/ Hamilton cycle programming questions. Download the code (your choice, C or java) and make sure when you run it you get a correct output file.
2. Print the file out.txt (from assignment #1). Draw pictures of all of the graphs If they have a Hamilton cycle, indicate one with a highlighter. Otherwise, if they have a Hamilton Path, indicate one with a highlighter. For the remaining ones, try to figure out why they have no Hamilton Path. Graphs 10-12 contain a Petersen graph with the outer 5-cycle labelled as 0, 1, 2, 3, 4 as a subgraph.

Tutorial Part 2: Induction Proofs

1. (a) Give an inductive definition of the even length strings over the alphabet {a, b}.
   (b) Use your definition from (a) to prove by induction that the number of strings of even length n= 2k for some integer k >= 0 is equal to 4^k.
2. Consider the following recurrence relation which is only defined for n= 2^k for integers k >= 0.
   T(1)= 5, and for n >= 2, T(n) = n + T(n/2).
   Choose either (a) or (b) as the correct formula and then prove that your answer is correct by induction. For the incorrect answer, carry out the steps of an induction proof until the proof fails.
   (a) T(n)= n + log₂n + 4
   (b) T(n)= 2n + 3