Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Data Structures and Algorithms – (COMP SCI 2C03)

Fall, 2021

Assignment 4

● No late assignments accepted.

● Make sure to submit a version of your assignment ahead of time to avoid last minute uploading issues.

● Submit one assignment solution as a PDF file on Avenue.

● If the solution submitted by any student is identical to another student, both students will get a zero mark on the assignment.

● Present your algorithms in Java or Pseudocode (Pseudocode is pre-ferred).

● It is advisable to start your assignment early.

This assignment consists of 4 questions, and is worth 20 marks.

1. Give the Pseudocode or Java of an algorithm that checks whether or not a given permutation of a DAG’s vertices is a topological order of that DAG. [5 marks]

2. Given a connected edge-weighted undirected graph G and a specified set of edges S (having no cycles), give the pseudocode or Java code for an algorithm to find a minimum-weight spanning tree of G that contains all the edges in S. [5 marks]

3. Give an outline of your algorithm for finding an edge, whose removal causes maximal increase in the shortest-paths length from one given vertex to another given vertex in a given edge-weighted digraph. [5 marks]

4. Give Pseudocode or JAVA code of your algorithm that runs in O(|A|+ |B|) to find the longest suffix of a string A that exactly matches a prefix of another string B. Explain the running time of your algorithm. [5 marks]