Module 2 - Graphs: Advanced (Written Problems)
CS 3100: DSA II
Page 1 of 2
Fall 2022
Module 2 - Graphs: Advanced (Written Problems)
The purpose of this homework is to practice solving new problems related to Graphs on your own. Each of the problems below will ask you to develop / describe an algorithm, reason about / prove something, or reason about runtimes. For algorithms, your descriptions should be detailed enough that someone could produce code from your description. Proofs should be logically sound and pithy, but do not need to be fully formalized. Runtimes need to be provided and argued succinctly. Good luck!
1. Describe an algorithm that, given a directed graph G represented as an adjacency matrix, returns whether or not the graph contains vertex with in-degree |V | - 1 and out-degree 0. In other words, does the graph have a node such that every other node points to it, but it does not point to any other node. Your algorithm must be O(V ). Note that there are (V 2) cells in your adjacency matrix so you'll need to be clever here.
2. Write clear pseudo-code to solve the following:
given a graph G, a start vertex s, and a vertex node t, use DFS to find any path from s to t and return the list of vertices in that path. Your algorithm should stop the search as soon as it finds any path. If t is not reachable from s, return an empty path (i.e., an empty list). The vertices in the list that is returned should be in order from s to t. G could be directed or undirected. For this problem, please use an implementation of the search algorithm taught in class and modify it. Note: You are going to need this exact algorithm on a future programming assignment, so take the time to think about it carefully here.
3. Let G be an undirected graph with n nodes (let's assume n is even for simplicity). Prove
or provide a counterexample for the following claim: If every node of G has a degree of at
least
n 2
,
then
G
must
be
connected.
Note:
G
cannot
have
any
loops
(edges
from
a
node
to
itself).
4. This problem is about robots that need to reach a particular destination. Suppose that you have an area represented by a graph G = (V, E) and two robots with starting nodes s1, s2 V . Each robot also has a destination node d1, d2 V . Your task is to design a schedule of movements along edges in G that move both robots to their respective destination nodes. You have the following constraints:
? You must design a schedule for the robots. A schedule is a list of steps, where each step is an instruction for a single robot to move along a single edge.
? If the two robots ever get close, then they will interfere with one another (perhaps start an epic robot fight?). Thus, you must design a schedule so that the robots, at no point in time, exist on the same or adjacent nodes.
CS 3100: DSA II
Page 2 of 2
Fall 2022
? You can assume that s1 and s2 are not the same or adjacent, and that the same is true for d1 and d2.
Your solution must contain the following items:
1. Describe an algorithm that produces an optimal schedule for the two robots. 2. What is the runtime of your algorithm? 3. How would the runtime change as the number of robots grows?
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- part 3 module 1 statistical graphs charts tables percentages
- modules in graphs department of computer science university of toronto
- event detection using ``variable module graphs for researchgate
- module 2 graphs advanced written problems
- module 05 graphs pie charts component band read only
- eventdetectionusing variablemodulegraphs for homecareapplications
- module module embedding for knowledge graphs arxiv
- module 2 basic data management graphs and log files
- 4th quarter module 4 data representation
- 4th quarter module 5 appropriate graphs to represent organized data
Related searches
- problems 2018 chevy equinox 2 0t
- advanced calculus problems and solutions
- advanced calculus problems examples
- 2 digit division problems worksheet
- 2 step word problems for 3rd grade
- 2 step word problems printable
- 2 step word problems pdf
- advanced calculus problems and answers
- plot 2 separate graphs matlab
- 2 step word problems 2nd grade
- algebra 2 problems and answers
- 2 step math word problems worksheet