讲解CIS 675、辅导Python编程语言、讲解Java/python语言、辅导c/c++z

IS 675 (Fall 2018) Disclosure Sheet

Name:

HW #

Yes No Did you consult with anyone on parts of this assignment, including other students, TAs, or

the instructor?

Yes No Did you consult an outside source (such as an Internet forum or a book other than the course

textbook) on parts of this assignment?

If you answered Yes to one or more questions, please give the details here:

By submitting this sheet through my Blackboard account, I assert that the information on this sheet is true.

This disclosure sheet was based on one originally designed by Profs. Royer and Older.

Homework 3:

Due October 15 at midnight Eastern time. Submit your solutions typed and

in a pdf document. To receive full credit, explain your answers.

If you collaborate with another student or use outside sources, please list

those students’ names and the URL/title/etc. of the sources that you referred

to. Collaboration is permitted, but you must write up your own solutions.

1. Suppose we have a directed graph with non-negative edge weights. It is

possible for this graph to have multiple shortest paths between two nodes. In

class, we saw how to find the length of the shortest path from a node s to all

other nodes. Suppose that in addition to finding the length of these shortest

paths, we also want to know how many shortest paths there are. Describe

an algorithm to do this.

2. There is a series of lectures that you would like to attend. Each lecture

i has a start time si and an end time ei. To attend a lecture, you must

attend the whole thing, and you can only attend one lecture at a time. Your

goal is to maximize the number of lectures that you attend. Design a greedy

algorithm to find the number of lectures that you can attend.

Hint: Consider the ending times of each lecture. If you pick a lecture that

ends at time t, which other lectures are you still able to attend? If you can

choose a lecture that ends sooner or a lecture that ends later, which gives

you more freedom for later selections? The algorithm that I am looking for

here follows the simple rule of at each step, selecting the lecture that has the

earliest ending time (and of course, don’t pick anything that interferes with

your past choices).

3. In the Grand Tour problem, you are given a list of n cities along with their

pairwise distances (i.e., you know the distance between every two cities). All

distances are positive and symmetric (the distance between A and B is equal

to the distance between B and A). You begin at a specified city C0, and

must perform a ‘tour’, in which you visit every other city exactly once, and

then return to C0. The goal is to minimize the total distance traveled.

Design a reasonable greedy algorithm for solving this problem. Does it al-

1

ways find the correct answer (i.e., the shortest tour)? If yes, prove that it is

always correct, and if no, provide a counterexample.

4. Suppose that you have a weighted, undirected graph, and are trying to

find the length of the shortest path from a node s to some other node t. You

decide to use Dijkstra’s algorithm for this. However, your graph is gigantic,

and running Dijkstra’s on the whole thing will take a very long time. So

instead, you perform two simultaneous searches in parallel. In one search,

you begin at node s, and gradually discover shortest paths from s to other

nodes. In the other search, you begin at node t, and gradually discover

shortest paths from t to other nodes (and because the graph is undirected,

this process also tells you the shortest paths from those nodes to t). In each

iteration, suppose the first search has discovered shortest paths from s to

some set of nodes Rs, and the second search has discovered paths from t to

some set of nodes Rt.

Initially, Rs only contains s and Rt only contains t. This process continues

until Rs and Rt have some overlap; that is, you find some node u that is

present in both Rs and Rt. Then if the distance from s to u is d1 and the distance

from u to t is d2, you report that the distance between s and t is d1+d2.

Will this procedure give you the correct shortest path from s to t? If yes,

prove that it will work. If no, give an example showing where it can fail.

5. Let G be a directed graph. Let s be a ‘start vertex’. An infinite path

of G is an infinite sequence v0, v1, v2, ... of vertices such that v0 = s and for

all i > 0, there is an edge from vi to vi+1. In other words, this is a path of

infinite length. Because G has a finite number of vertices, some vertices in

an infinite path are visited infinitely often.

1. If p is an infinite path, let Inf(p) be the set of vertices that occur

infinitely many times in p. Prove that Inf(p) is a subset of a single

strongly connected component of G.

2. Describe an algorithm to determine if G has an infinite path. Prove

that it is correct.

Extra Credit: A perfect matching in a graph G is a set of edges S such that

every node from G is adjacent to (i.e., appears in) exactly one edge from S

2

(no more and no less). The graph might represent students in a classroom:

each student is willing to work with some other students on a partner project,

and we want to figure out how to pair them so that everyone has one partner.

For example, in the graph below, the bolded edges represent a perfect

matching.

Suppose you are given a binary tree T with vertices V and edges E. This

tree is not necessarily a complete binary tree: i.e., every node has at most

2 children, but might only have 0 or 1 child. Describe an ecient

greedy

algorithm to determine if T has a perfect matching. Your algorithm does not

have to work for non-tree graphs.