#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


Question 1:

(i) What is Erdos number
(ii) What is the Bacon number?
(iii) What is Erdos-Bacon number?
(iv) What is the Erdos-Bacon number of Dr.Z? 


Answer 1:

(i) The Erdős number is the number of "hops" needed to connect the author of a paper with the prolific late mathematician Paul Erdős

(ii) Six Degrees of Kevin Bacon or "Bacon's Law" is a parlor game based on the "six degrees of separation" concept, which posits that any two people on Earth are six or fewer acquaintance links apart.
Also the the shortest path between an arbitrary actor and prolific actor Kevin Bacon

(iii) 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) Dr. Z's Erdos-Bacon number is 5.




Question 2:


What does mean for a problem in CS to be NP-Hard?



Answer 2:

A problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, H‎'s solution can be used to solve L in polynomial time.

It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven.




Question 3:


Cook up a path with 6 vertices called 1,2,3,4,5,6 with 12 edges (undirected) that you know for sure has a Hamiltonian cycle. Describe it.



Answer 3:


[{2,3,4,5,6,},{1,6,3},{2,1,6,5,4},{3,1,5},{4,3,1,6},{1,3,3,5}]

The length of every Hamiltonian cycle is the same- 5 edges. 





Question 4:


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



Answer 4:

#MAPLE complained took tooo long

seq(SAW(KiG(3,n)),n=1..10)