#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: PLEASE LIST ALL THE QUESTIONS FOLLOWED, AFTER EACH BY THE ANSWER Q1. Describe the problem that Euler solved regarding 7 bridges (origin of graph theories) A1. It's the seven bridges of konigsberg. The task is to walk through the city that would cross each of those bridges once and exactly once. This means to find a Eulerian walk for the following graph C // \ A --- B \\ / D Q2. Draw it on a piece of paper with a line segment representing every edge [15:00] A2. 2 ---- 4 / \ / 1 ---- 3 Q3. If you toss a fair coin 2000 times, what is the probability that you get exactly 1000 heads (and exactly 1000 tails) A3. (1/2)^1000 Q4. If you roll a fair die 6000 times what is the probability that each of the possible outcome occurs exactly 1000 times A4. (1/6)^1000 Q5. 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. A5. first layer: 1 2 3 second layer: 4 5 6 7 8 9 10 11 12 third layer: 13 14 15 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 [[4,5,6],[7,8,9],[10,11,12],[13,14,15],[17,18,19],[20,21,22],[23,24,25],[26,27,28],[29,30,31],[32,33,34],[35,36,37],[38,39,40]] Q6. Look at the cities that border piscataway, and for each of them those that border and again until you get to princeton (i). construct the graph (ii). Find the number of paths from piscataway to princeton in 3 ways (a). Find the actual set using paths (and list them) (b). By using NuPaths (c). By using the GFt procedure A6. (i). # BFS LEVEL 1 Piscataway: [Middle Sex, Dunellen, South Plainfield, Edison, Highland Park, New Brunswick, Franklin, South Bound Brook] # BFS LEVEL 2 Middle Sex: [Piscataway, Dunellen, Green Brook, Bound Brook, South Bound Brook] Dunellen: [Piscataway, Middle Sex, Green Brook, Plainfield] South Plainfield: [Edison, Plainfield, Piscataway] Edison: [Metuchen, South Plainfield, Woodbridge, Sayreville, East Brunswick, Highland Park, New Brunswick, Piscataway, South Plainfield, Scotch Plains, Clark] Highland Park: [Piscataway, Edison, New Brunswick] New Brunswick: [Franklin, Piscataway, Highland Park, North Brunswick, East Brunswick] Franklin: [Princeton] <- TARGET FOUND, BFS END ID LIST 1: Piscataway 2: Middle Sex 3: Dunellen 4: South Plainfield 5: Edison 6: Highland Park 7: New Brunswick 8: Franklin 9: South Bound Brook 10: Green Brook 11: Bound Brook 12: Plainfield 13: Metuchen 14: Woodbridge 15: Sayreville 16: East Brunswick 17: Scotch Plains 18: Clark 19: North Brunswick 20: Princeton Undirected Graph List: [[2, 3, 4, 5, 6, 7, 8, 9, 2, 3, 4, 5, 6, 7], [1, 1, 3, 10, 11, 9, 3], [1, 2, 1, 2, 10, 12], [1, 5, 12, 1, 5, 5], [1, 4, 13, 4, 14, 15, 16, 6, 7, 1, 4, 17, 18, 6], [1, 5, 1, 5, 7, 7], [1, 5, 6, 8, 1, 6, 19, 16], [1, 7, 20], [1, 2], [2, 3], [2], [3, 4], [5], [5], [5], [5, 7], [5], [5], [7], [8]] (ii). (a),(b),(c) In the question, it says that to find number of paths from piscataway to princeton. There should be unlimited amount of paths if we are allowed to visit verticies more than once. However, if we assume we cannot visit vertex more than once. Then there can be a limited amount of paths (a). If we want to use Paths to find paths that dont allow repeated vertex visits, then we have to call Paths(G, 1, 20, 20) then filter out results that have repeated vertex. K=20 as in worse case senario we might have to go through every vertex to get to princeton. However, based on the implementation of Paths, maple will certainly complain, so this is not calculatable. (b). NuPaths can't solve this problem as it doesn't filter out paths that have repeated vertices. (c). GFt can't solve this problem as well as it doens't filter out paths that have repeated verticies. Since the problem dont state the upper bound of k. So we assumed that no vertex revisit is allowed. This can be solved by using DFS algorithm. After DFS, this is the result: [[1, 2, 3, 12, 4, 5, 6, 7, 8, 20], [1, 2, 3, 12, 4, 5, 7, 8, 20], [1, 2, 3, 12, 4, 5, 16, 7, 8, 20], [1, 2, 10, 3, 12, 4, 5, 6, 7, 8, 20], [1, 2, 10, 3, 12, 4, 5, 7, 8, 20], [1, 2, 10, 3, 12, 4, 5, 16, 7, 8, 20], [1, 3, 12, 4, 5, 6, 7, 8, 20], [1, 3, 12, 4, 5, 7, 8, 20], [1, 3, 12, 4, 5, 16, 7, 8, 20], [1, 4, 5, 6, 7, 8, 20], [1, 4, 5, 7, 8, 20], [1, 4, 5, 16, 7, 8, 20], [1, 5, 6, 7, 8, 20], [1, 5, 7, 8, 20], [1, 5, 16, 7, 8, 20], [1, 6, 5, 7, 8, 20], [1, 6, 5, 16, 7, 8, 20], [1, 6, 7, 8, 20], [1, 7, 8, 20], [1, 8, 20], [1, 9, 2, 3, 12, 4, 5, 6, 7, 8, 20], [1, 9, 2, 3, 12, 4, 5, 7, 8, 20], [1, 9, 2, 3, 12, 4, 5, 16, 7, 8, 20], [1, 9, 2, 10, 3, 12, 4, 5, 6, 7, 8, 20], [1, 9, 2, 10, 3, 12, 4, 5, 7, 8, 20], [1, 9, 2, 10, 3, 12, 4, 5, 16, 7, 8, 20]] All the possible non-repeated vertex path from 1 to 20