#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 the Erdos number?
The Erdős number describes the "collaborative distance" between mathematician Paul Erdős and another person, as measured by authorship of mathematical papers.
(ii) What is the Bacon number?
The Bacon number of an actor is the number of degrees of separation he or she has from Bacon, as defined by the game. This is an application of the Erdős number concept to the Hollywood movie industry. The higher the Bacon number, the greater the separation from Kevin Bacon the actor is.
(iii) What is the Erdos-Bacon number?
A person's Erdős–Bacon number is the sum of one's Erdős number—which measures the "collaborative distance" in authoring academic papers between that person and Hungarian mathematician Paul Erdős—and one's Bacon number—which represents the number of links, through roles in films, by which the person is separated from American actor Kevin Bacon.
(iv) What is the Erdos-Bacon number of Dr.Z?
5


2. What does it mean for a problem in CS to be NP-hard?
An NP-hard problem is at least as hard as the hardest problems in NP, where NP problems consist of computational decision problems for which a given yes-solution can be verified as a solution in polynomial time by a deterministic Turing machine (or solvable by a non-deterministic Turing machine in 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
{2,3,4,5,6},{1,3,5,6,3},{1,2,6},{1,2,5},{4,2,5,1},{3,2,5,1}


4. Using ComboProject1.txt find the first 7 terms of the following: the number of 3xn King's tours n=1..10

KtTours(3,n) for n=1..9 == null
KtTours(3,10) = [1,1],[2,3],[3,1],[1,2],[2,4],[1,6],[3,5]