[SOLVED] Cs5800 – discrete structures problem set #6 problem #1 define kn to the graph on n vertices, where each pair of vertices is connected by an edge.

CS5800 – Discrete Structures
Problem Set #6
Problem #1
Define Kn to the graph on n vertices, where each pair of vertices is connected by an edge. Kn is known
as the complete graph on n vertices.
To illustrate, here are the complete graphs Kn, for n = 2, 3, 4, 5, 6, 7.
(a) Draw the complete graph K10, and determine the total number of edges in this graph. Briefly
explain how you calculated this total.
(b) The complete graph Kn has exactly 120 edges.
Determine the value of n. Clearly justify your answer.
(c) Sometime in 2021 (or 2022), a group of CS5800 students meet at the Northeastern campus for the
first time, to have a post-Covid celebration party. Each pair of students shakes hands.
Unfortunately, Paul walks in late. As a result, Paul is only able to shake hands with some of
the other students at the celebration party.
If there are exactly 42 handshakes in total, determine the number of hands that Paul shook. Clearly
and carefully justify your answer.

Problem #2
Consider this binary tree, where each vertex is labelled with a positive integer. The root vertex is 1.
For all positive integers k ≥ 1, vertex k has two children: 2k (Left) and 2k + 1 (Right).
(a) In your own words, describe how Breadth-First Search (BFS) and Depth-First Search (DFS) work.
Does one search algorithm always reach the destination faster than the other? Explain.
(b) Suppose we want to determine a path from vertex 1 (start vertex) to vertex 10 (end vertex).
Using BFS, determine the order in which the vertices will be visited. Using DFS, determine the
order in which the vertices will be visited. Briefly explain your answers.
(c) Suppose that we extend this binary tree to infinitely many levels, so that each vertex k has two
children: 2k (Left) and 2k + 1 (Right).
The path from vertex 1 to vertex 10 can be described by a sequence of Left and Right moves,
namely Left, Right, Left.
Consider the path from vertex 1 to vertex 2021. Determine the sequence of Left and Right moves
for this path. Clearly justify your answer.

Problem #3
In this question, you will create a mini-portfolio consisting of any two LeetCode problems on Graphs,
chosen from the four problems below:
https://leetcode.com/problems/clone-graph/
https://leetcode.com/problems/is-graph-bipartite/
https://leetcode.com/problems/find-the-town-judge/
https://leetcode.com/problems/find-if-path-exists-in-graph/
As always, you may code your algorithms in the programming language of your choice.
Here is how your mini-portfolio will be graded.
There will be a total of 10 points for any of the combination of problems in your mini-portfolio: For
each of these, provide the problem number, problem title, difficulty level, and the screenshot of you getting your solution accepted by LeetCode (10 points).
Note that you are allowed to work with Teammates on this part of the problem. Make
sure you write all names of the collaborators.