CS代写：COMP20007 Design of Algorithms 算法代写案例

算法是一系列指令，通常被称为“过程”，在解决特定问题时要遵循这些指令。虽然在技术上不受定义限制，但这个词几乎总是与计算机相关联，因为计算机处理的算法可以比人类更快地解决更大的问题。由于现代计算比人类历史上任何时候都更频繁地使用算法，因此围绕它们的设计、分析和改进形成了一个领域。算法设计领域需要强大的数学背景，计算机科学学位尤其受欢迎。

算法按照设计分类

在这种分类中，算法可以分为三个主要类别。他们是：

1. 贪心法：在贪心法中，在每一步中，都会做出选择局部最优值的决定，而不考虑未来的后果。
2. 分而治之：分而治之策略涉及将问题划分为子问题，递归解决它们，然后将它们重新组合以获得最终答案。 
3. 动态规划：动态规划的方法类似于分而治之。不同之处在于，每当我们进行具有相同结果的递归函数调用时，我们不会再次调用它们，而是尝试将结果以表的形式存储在数据结构中并从表中检索结果。因此，降低了总体时间复杂度。“动态”意味着我们动态决定是调用函数还是从表中检索值。 
4. 线性规划：在线性规划中，在输入和最大化或最小化输入的某些线性函数方面存在不等式。 
5. 减少（转换和征服）：在这种方法中，我们通过将一个难题转换为一个已知问题来解决它，我们有一个最佳解决方案。基本上，目标是找到一种简化算法，其复杂性不受最终简化算法的支配。 
6. 回溯：这种技术在解决具有单一唯一解的组合问题时非常有用。我们必须在哪里找到导致任务完成的正确步骤组合。此类问题有多个阶段，每个阶段都有多种选择。这种方法基于在每个阶段逐个探索每个可用选项。在探索一个选项时，如果达到了似乎没有导致解决方案的点，程序控制会回溯一个步骤，并开始探索下一个选项。通过这种方式，程序探索所有可能的行动过程并找到导致解决方案的途径。  
7. 分支定界：该技术对于解决具有多个解决方案的组合优化问题非常有用，我们有兴趣找到最佳解决方案。在这种方法中，整个解空间以状态空间树的形式表示。随着程序的进行，每个状态组合都会被探索，如果先前的解决方案不是当前解决方案的最佳解决方案，则将其替换为新的解决方案。

当新算法的设计被实际应用时，相关学科被称为算法工程。这两个功能经常由同一个人执行，尽管较大的组织（如亚马逊和谷歌）聘请了专业的设计师和工程师，因为他们需要新的和专业的算法。与设计过程一样，算法工程经常涉及具有强大数学背景的计算机科学认证：在它们作为独立的专业职业存在的情况下，算法工程师采用设计师的概念性想法并从中创建计算机可以理解的过程。

COMP20007 算法代写案例，92分通过

Question 1 Answer True or False for each of these statements. You will gain one mark for a correct answer, and lose one markfor an incorrect answer.

Question 2.1

Write a recurrence relation that describes the worst case running time of Quicksort. Briefly justify why you haveused this recurrence relation.

Question 2.2

What is the solution to your recurrence in Question 2.1? Prove it with induction.

Question 3.1

Label this graph with the pre and post numbers that would be assigned with Depth First Search. Assume the numbers begin at 1, and always prefer a lower labelled vertex if there is a choice (so start at A).

Question 3.2

Are there any back edges or cross edges in the graph? If so, what are they?

Question 3.3

Draw the graph with vertices of the graph in a single line in the order they would be sorted by a topological sort.

Question 3.4

How many strongly connected components are there in the graph?

Question 3.5

List all the source vertices of the graph?

Question 3.6

List all the sink vertices of the graph?

Question 3.5

What single edge could be added so that there is only one strongly connected component in the resulting graph?

Question 4

The Federal Government decides to alter the funding model of universities to a strict geographical equity model.

Each university will get funding proportional to the number of eligible students living within kkilometers of travel

time to the university, where kis a parameter set during an election campaign.

The consulting company Sneaky Go8 Inc has employed you to work out the value of kso that Unimelb and Monash

get about the same funding without stealing each others students. You are given the input data as a graph G(V, E),

where

•u1∈Vis the vertex representing Unimelb;

•u2∈Vis the vertex representing Monash;

•ti∈V, i ∈[1, T ] represents a transport intersection, train station, and so on;

•hi∈V, i ∈[1, H] represents the living location of one potential student; and

•weis the cost of traveling along edge e∈E. Here is an example of a 2 small sections of the graph around u1and u2but not showing edge weights (“···”represents more graph that is not shown).

Thus if Uis the set of all hivertices whose path length to u1is < k and Mis the set of hivertices whose pathlength to u2is < k, then an algorithm to solve algorithm should find ksuch that the intersection of Uand Misempty, and |U|3+|M|3is maximum. You may assume the input is a correct graph, and that |U|>1 and |M|>1.Give high-level pseudo code for such an algorithm.Analyse the running time of your algorithm. Full marks will only be given for a correct algorithm that runs inO((E+V) log V+Hlog H) time.