#ATTENDANCE QUIZ FOR LECTURE 15 of Dr. Z.'s Math454(02) Rutgers University

# Please Edit this .txt page with Answers

#Email  ShaloshBEkhad@gmail.com 
#Subject: p15
#with an attachment called
#p15FirstLast.txt
#(e.g. p15DoronZeilberger.txt)

#Right after finishing watching the lecture but no later than Oct. 27, 2020, 8:00pm


THE NUMBER OF ATTENDANCE QUESTIONS WERE: 4

PLEASE LIST ALL THE QUESTIONS FOLLOWED, AFTER EACH BY THE ANSWER

1. 
i. What is Erdos number?
The Erdos number is the number that describes the "collaborative distance" between the mathematician Paul Erdos and another person
ii. What is Bacon number?
The Bacon number is the number that describes the acquaintance distance between the actor Kevin Bacon and another person.
iii. What is the Erdos-Bacon number?
The Erdos-Bacon number is the number that describes the sum of one's Erdos and Bacon numbers.
iv. What is the Erdos-Bacon number of Dr. Z?
The Erdos-Bacon number of Dr. Z is 5.

2. What does it mean for a problem in cs to be np-hard?
For a problem to be np-hard, the problem is informally "at least as hard as the hardest problems in nondeterministic polynomial time".

3. Cook up a graph with 6 vertices called 1,2,3,4,5,6 with 12 edges that you know for sure has a Hamiltonian cycle
G:=[{2,4,6},{1,3,4,5,6},{2,4,5,6},{1,2,3,5},{2,3,4,6},{1,2,3,5}]
#This is assuming the edge 1,2 is the same as 2,1

4. Using ComboProject1.txt, find the first 10 terms of the following
The number of 3 x n king's tours n=1..10
In other words, use SAW with KiG

seq(nops(SAW(KiG(3, i)[1])), i = 1 .. 8);
             0, 4, 13, 97, 600, 3977, 25762, 168085

n=9,n=10 take too long