> #Attendence quiz 15
;
> #THE NUMBER OF ATTENDANCE QUESTIONS WERE: 4
;
> 
;
> #Q1
;
> #What is an Erdos number? What is the Bacon number? What is the Erdos-Bacon number? What is the Erdos-Bacon number of Dr. Z? 
;
> 
;
> #The Erd
Qs number is the number of "hops" needed to connect the author of a paper with the prolific late mathematician Paul Erd
Qs. An author's Erd
Qs number is 1 if he has co-authored a paper with Erd
Qs, 2 if he has co-authored a paper with someone who has co-authored a paper with Erd
Qs, etc. (Hoffman 1998, p. 13).
;
> #The Bacon number of an actor or actress is the number of degrees of separation they have from actor Kevin Bacon, as defined by the game known as Six Degrees of Kevin Bacon. It applies the Erd
Qs number concept to the movie industry. The higher the Bacon number, the farther away from Kevin Bacon the actor is.For example, Kevin Bacon's Bacon number is 0. If an actor works in a movie with Kevin Bacon, the actor's Bacon number is 1. If an actor works with an actor who worked with Kevin Bacon in a movie, the first actor's Bacon number is 2, and so forth.
;
> #The Erdos-Bacon number is the sum of one's Erdos number and Bacon number. 
;
> # the Erdos-Bacon number of Dr. Z is 5. Great.
;
> 
;
> #Q2
;
> #What does it mean for a problem in computer science to be NP-Hard? 
;
> 
;
> #A problem is NP-hard if an algorithm for solving it can be translated into one for solving any NP-problem (nondeterministic polynomial time) problem. NP-hard therefore means "at least as hard as any NP-problem," although it might, in fact, be harder.
;
> 
;
> #Q3
;
> #Cook up a graph with 6 verticies with 12 edges that you know for sure has a hamiltonian cycle.
;
> 
;
> #[{1,3,5},{2,3,4,5,6},{1,2,4,6},{1,2,3,5},{1,2,4,6},{1,3,4,5}]

;
> 
;
> #Q4
;
> #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.
;
> 
;
> #KiG(k,n): The King graph on a k by n board
> KiG:=proc(k,n) local V,E,i,j,T1,v,Neighs,Moves,m,pt:
> 
> #The set the list of  vertices in the k by n board (using matrix indexing)
> V:=[seq(seq(seq([i,j],j=1..n),i=1..k))]:
> 
> #T1 is a labelling of the vertices in V
> 
> for i from 1 to nops(V) do
> T1[V[i]]:=i:
> od:
> 
> #E is a list such that its i-th entry is the set of neighbors of V[i] using the above-indexing
> 
> E:=[]:
> 
> for i from 1 to nops(V) do
>  pt:=V[i]:
> 
> Moves:={[1,0],[-1,0],[0,1],[0,-1],[1,1],[-1,-1],[1,-1],[-1,1]}:
> #There are up to 8 neighbors of any vertex 
> Neighs:={seq(pt+m,m in Moves)}:
> 
> #But many of them fall off the board, 
> Neighs:=Neighs intersect convert(V,set):
> 
> #We append to the "list of neighbors" the set of neighbors of the current vertex BUT in terms of their "ids" (given by T1)
> #getting a description of the graph in "cannical form"
> E:=[op(E),{seq(T1[v],v in Neighs)}]:
> od:
> 
> #We return the graph in "canonical form" where the vertices (members of V), are labelled by positive inetegers from 1 to nops(V)
> #together with the "dictionary"
> E,V:
> end:
> #SAW1(G,a,b,k,S): Inputs a graph G of {1, ..., n} and two vertices a and b and a pos. integer k and a set of vertices S, outputs the
> #set of walks of length k from a to b that avoid S. Try
> #SAW1(KtG(3,5)[1],1,2,5,{}):
> SAW1:=proc(G,a,b,k,S) local gu,n,a1,lu,lu1,mu:
> option remember:
> n:=nops(G):
> if not (1<=a and a<=n and 1<=b and b<=n) then
>  RETURN(FAIL):
> fi:
> 
> if k=1 then
>  if member(b,G[a]) and  not member(a,S) and not member(b,S) then
>   RETURN({[a,b]}):
>  else
>   RETURN({}):
>  fi:
> fi:
> 
> 
> if (member(a,S) or member(b,S)) then
>  RETURN({}):
> fi:
> 
> mu:=G[a] minus (S union {a}):
> 
> gu:={}:
> 
> for a1  in mu do
>  lu:=SAW1(G,a1,b,k-1,S union {a}):
>  gu:=gu union {seq([a,op(lu1)],lu1 in lu)}:
> od:
> 
> gu:
> 
> end:
> 
> #SAW(G): The set of Closed Hamiltonian paths in the graph G (in canonical form) starting at 1 and G[1][1]
> #Try: SAW(KtG(3,10)[1]):
> #
> SAW:=proc(G) local i:
> {seq(op(SAW1(G,1,G[1][i],nops(G)-1,{})),i=1..nops(G[1]))}:
> end:
> 

;
> seq(nops(SAW(KiG(3,n)[1])),n=1..9)
Warning,  computation interrupted
;
> #Sorry Dr.Z, it takes too long for my computer.
;