# 数据结构代考 | CSC 3102: Advanced Data Structures and Algorithm Analysis

1. Construct a sux trie for abacabc.
2. Consider the following graph (see page 2). Apply Prim’s algorithm starting from the leftmost vertex, and
nd the minimum spanning tree.
3. Given the following directed graph (see page 3) perform a dfs on it and list (draw) all the trees that the
dfs results in. Also, mark discovery and nish times for each node.
4. Consider the following directed (multi) graph (see page 3). Each edge here represents a ight and is
annotated with (departure time, arrival time). If we leave from airport A at 8am what is the soonest one
can reach airport F. Please nd this itinerary. You will use modi ed dijkstra’s algorithm for this. The
interpretation of d-value d(v) in this case will be that earliest time (based on so far what we know) we can
reach the airport v.
5. Given an array A[1::n] – our task is to select a subsequence of this array. The sum of the numbers selected
for this subsequence is to be minimized. The constraint is that any number which is not selected must have
at least one of its neighbor selected. Give a dynamic programming algorithm for this task. You will need
to set up subproblems, de ne metric(s) to compute for each subproblem and then write recurrences for how
to compute.
Here are some example for helping with your understanding. If A = 1; 5; 3; 7; 6; 4; 1; 2 then the best subse-
quence you can choose is 1; 3; 4; 1. This has cost 9. If the subsequnce you choose is 1; 3; 1; 2 that will be
lesser cost but it is invalid because there is no one covering 6. On the othe hand 5; 6; 1 is valid but has
higher cost.
6. Given a set of n tasks T1; T2; :::; Tn, where each task comes with processing time pi and each has a deadline
di. We denote Ti = (pi; di). A task is executed successfully if it is performed and completed before its
deadline. Now our question FEASIBILITY CHECK is: given this set of tasks, can all the tasks be executed
by their respective deadlines (you can choose in which order you execute these tasks)? Given algorithm to
determine this, and analyze its complexity?
For example, if we have 4 tasks (3; 6); (4; 12); (3; 4); (1; 3) it is impossible to execute all of them by their
deadline in whichever order you try. However, if your task set is (2; 4); (5; 12); (1; 3) – we can execute them
in this order (2; 4); (1; 3); (5; 12). E-mail: itcsdx@outlook.com  微信:itcsdx 