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

# Please Edit this .txt page with Answers

#Email  ShaloshBEkhad@gmail.com 
#Subject: p13
#with an attachment called
#p13FirstLast.txt
#(e.g. p13DoronZeilberger.txt)

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


THE NUMBER OF ATTENDANCE QUESTIONS WERE: 6

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

-----------------------------------
Attendance Question 1:
Describe the problem that Euler solved regarding 7 bridges.

The graph theory problem regarding 7 bridges is called the Seven Bridges of Konigsberg. Basically, the city was divided into two sides by a river and in that river were two large islands. These sides and islands were connected by a total of seven bridges. The problem was deciding whether or not there existed a path throught the city that crossed each of the bridges exactly once. Euler eventually proved that there is no such solution for the problem.


-----------------------------------
Attendance Question 2:
Draw it on a piece of paper with a line segment representing every edge.


1-----------2
 \		   /|
  \		  / |
   \     /  |
    \   /   |
     \ /    |
      X     |
     / \    |
    /   \   |
   /     \  |
  /       \ |
 /         \|
4-----------3

-----------------------------------
Attendance Question 3:
If you toss a fair coin 2000 times what is the probability that you get exactly 1000 heads (and exactly 1000 tails)?

Using a binomial distribution, P(X = 1000) = (2000 choose 1000) * (0.5)^1000 * (0.5)^1000 = 0.01783901115


-----------------------------------
Attendance Question 4:
If you roll a fair die 6000 times what is the probability that each of the possible outcomes occurs exactly 1000 times?

(6000 choose 1000) * (5000 choose 1000) * (4000 choose 1000) * (3000 choose 1000) * (2000 choose 1000) * (1000 choose 1000) is the number of outcomes where that each of the possible outcomes occurs exactly 1000 times. 

6^6000 is the number of outcomes total. 

So, the probability is the first value divided by the second value which is:
0.7823747737e-9

-----------------------------------
Attendance Question 5:
Pick 5 random Facebook friends. For each of them, pick 3 friends. For each of the friends of friends, pick 3 friends. Label the people picked 1,2,...,n.
Write the Graph in our data structure.

V={1,2,3,...,32}
G={{2,3,4,6,19,33}, {1,5,6,7}, {1,6,8,9}, {1,10,11,12}, {2,6,7,13,14,33}, {1,2,3,5}, {2,5}, {3}, {3}, {4}, {4}, {4}, {5}, {5}, {16,17,18,33}, {15}, {15}, {15}, {1,20,33}, {19,21,22,23}, {20}, {20}, {20}, {25,26,33}, {24,27,28,29}, {24,30,31,32}, {25}, {25}, {25}, {26}, {26}, {26}, {1,5,15,24}}

------------------------------------
Attendance Question 6:

Look at the cities that border Piscataway and for each of those that border them and again until you get to Princeton.
i) Construct the graph
ii) Find the number of paths from Piscataway to Princeton
a) Find the actual set using Paths (and list them)
b) By using NuPaths
c) By using GFt

Key:
1:  Piscataway
2:  Edison
3:  New Brunswick
4:  Sayreville
5:  East Brunswick
6:  Plainfield
7:  Somerville
8:  Flemington
9:  Freehold
10: Princeton

i) G := [{2,3,4,5}, {1,3,4,5,6}, {1,2,5,7,10}, {1,2,5}, {1,2,3,4,9,10}, {2,7}, {3,6,8}, {7,10}, {5,10}, {3,5,8,9}] the undirected graph. The number of paths will be infinite for the undirected graph so I assume we use a Directed, acyclic graph for the rest of the questions.

G := [{2,3,4,5}, {3,4,5,6}, {5,7,10}, {5}, {9,10}, {7}, {8}, {10}, {10}, {}]

ii)
a)
[seq(op(Paths(G,1,10,i)), i = 1..10)]
[[1, 3, 10], [1, 5, 10], [1, 2, 3, 10], [1, 2, 5, 10], [1, 3, 5, 10], [1, 4, 5, 10], [1, 5, 9, 10], [1, 2, 3, 5, 10], [1, 2, 4, 5, 10], [1, 2, 5, 9, 10], [1, 3, 5, 9, 10], [1, 3, 7, 8, 10], [1, 4, 5, 9, 10], [1, 2, 3, 5, 9, 10], [1, 2, 3, 7, 8, 10], [1, 2, 4, 5, 9, 10], [1, 2, 6, 7, 8, 10]]

nops(%)
17

b)
add(NuPaths(G,1,10,i), i = 1..20)
17

c)
sum(coeff(taylor(GFt(G,10,t)[1],t = 0,21),t,i),i=1..20)
17

------------------------------------

Hi, Professor Z. 

I just wanted to write this note to mention that I think some of these attendance problems are getting to be a little overly complicated. 
I think some problems like the Facebook and Piscataway-Princeton ones end up taking a lot of time for students to look up and figure out details rather than learning or comprehending the math and reasoning behind the problem. 
I personally think more concrete and simpler examples like those with just numbers are easier to work with for students and still allow them to demonstrate their understanding.

Regards,
-Kent Mei