#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
#p14FirstLast.txt
#(e.g. p14DoronZeilberger.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 the Erdos Number?
(ii) What is the Bacon Number?
(iii) What is the Erdos-Bacon Number?
(iv) What is the Erdos-Bacon Number of Dr.Z?

ANSWER:

(i) According to Wikipedia, it describes the collaborative distance between mathematician Paul Erdos and another person, as measured by authorship of papers.
(ii) The number of degrees of separation a person has from Kevin Bacon
(iii) The sum of one's Erdos Number and one's Bacon Number
(iv) Dr. Z has an Erdos-Bacon number of 5.

QUESTION #2:

What does it mean for a problem in CS to be NP hard?

ANSWER:

NP problems are can be solved in nondeterministic polynomial time.

QUESTION #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

ANSWER:

We have V={1,2,3,4,5,6}

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

QUESTION #4:

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

In other words, use SAW with KiG.

ANSWER:

Running seq(SAW(KiG(3,n)[1]),n=1..10) returns:

(empty set), [1, 2, 3, 5, 6, 4], [1, 2, 3, 5, 6, 9, 8, 7, 4], [1, 2, 3, 4, 7, 8, 12, 11, 6, 9, 10, 5], [1, 2, 3, 4, 5, 9, 10, 15, 14, 8, 7, 13, 12, 11, 6], [1, 2, 3, 4, 5, 6, 11, 12, 18, 17, 10, 9, 16, 15, 8, 13, 14, 7], [1, 2, 3, 4, 5, 6, 11, 12, 18, 17, 10, 9, 16, 15, 8, 13, 14, 7],