算法作业代写 Algorithm代写 CS代写 cs算法课业代写
932Algorithm in Action CSCI-570 Homework 4 算法作业代写 1 Compute Max-Flow And Min-Cut 2 Escape From the Building In this problem, we need to decide whether there is a feasible plan for all th...
View detailsSearch the whole station
离散数学课业代写 Instructions This homework should be done in groups of one to four students, without assistance from anyone besides the instructional staff
This homework should be done in groups of one to four students, without assistance from anyone besides the instructional staff and your group members. Homework must be submitted through Gradescope by a single representative of your group and received by 11:59pm on the due date. There are no exceptions to this rule.
You will be able to look at your scanned work before submitting it. You must type your solutions. (hand-drawn diagrams are okay.) Your group representative can resubmit your assignment as many times as you like before the deadline. Only the most recent submission will be graded.
Students should consult their textbook, class notes, lecture slides, podcasts, group members, instructors, TAs, and tutors when they need help with homework. You may ask questions about the homework in office hours, but questions on Piazza should be private, visible only to instructors.
This assignment will be graded for not only the correctness of your answers, but on your ability to present your ideas clearly and logically. You should explain or justify, present clearly how you arrived at your conclusions and justify the correctness of your answers with mathematically sound reasoning (unless explicitly told not to). Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.
Key Concepts Graphs, Eulerian tours, Trees, Tree-based data structures, DAGs, topological sort.
We have 8 light switches in a room, each of which can be UP or DOWN. They all start DOWN. To do a complete test of the switches, we want to find a sequence of flipping one switch at a time so that, from each of the 28 possible positions of all the switches, we have flipped every switch at some point in the sequence, and so that we end with all switches DOWN.
For example, if there are only 2 switches,
• from DD, we would need to test DD → DU and DD → UD
• from DU, we would need to test DU → DD and DU → UU
• from UD, we would need to test UD → UU and UD → DD
• from UU, we would need to test UU → DU and UU → UD (Here is an example of a sequence of positions that tests all eight of the transitions above:
(DD, DU, UU, DU, DD, UD, UU, UD, DD)
(a) Use a counting argument to give a lower bound on the minimum length of the sequence of flips of 8 switches that meets the above condition.
(b) Model this problem as a graph problem to give an argument as to how to achieve this lower bound.
A max-tree data structure on n = 2k elements is a complete binary tree data structure of depth k with n leaves, where the leaves store integers and the interior nodes store the maximum value of any leaf in their sub-tree. We view the leaves as being indexed from 1 to n, from left to right.
For each of the operations given below, give a O(k) = O(logn) time algorithm for performing the operation on a max-tree.
You should give an explanation for your algorithms, but don’t need a formal proof of correctness or pseudocode:
(a) Given the following information:
index i such that 1 ≤ i ≤ n, positive integer v and a pointer to the root r of a Max-tree of size n, Describe an algorithm to add v to the current value of the i’th leaf and update the appropriate interior nodes so that it follows the rules of being a max-tree.
(b) Given the following information:
index i such that 1 ≤ i ≤ n, positive integer v and a pointer to the root r of a Max-tree of size n, Describe an algorithm that returns the maximum value of the leaves 1 through i.
For each of the following descriptions of a directed graph, say whether they are DAG’s (in general). If they are not, give an example of a possible directed cycle within the graph. If they are, give the topological order for the DAG.
(a) The graph has a set of non-negative integers as vertices, and there is an edge from x to y if and only if y is a multiple of x and not equal to x .
(b) The graph has a set of ordered pairs of non-negative integers (x, y) as vertices , and (x, y) has an edge to (x’ , y’ ) if and only if x < x’ and y < y’ or x < y’ and y < x’ .
(c) The graph has vertices (x, y) with 1 ≤ x ≤ n, 1 ≤ y ≤ n, and the edges leaving (x, y) are to (x + 1, y) (unless x = n) and (x, y + 1) (unless y = n).
更多代写:CS加拿大考试代写 gre作弊后果 英国宏观经济代上网课 research paper内容代写 北美留学生报告作业代写 怎么写conclusion
合作平台:essay代写 论文代写 写手招聘 英国留学生代写
Algorithm in Action CSCI-570 Homework 4 算法作业代写 1 Compute Max-Flow And Min-Cut 2 Escape From the Building In this problem, we need to decide whether there is a feasible plan for all th...
View detailsCS 170 Efficient Algorithms and Intractable Problems Homework 4 高效算法与难题代写 Design an efficient algorithm that given a directed graph G determines whether there is a vertex v from wh...
View detailsMA1607 | Project 2 数学算法代写 1 Project background This project builds upon the work done from week 11, where we learned the mathematics underlying the Google PageRank algorithm. 1 Projec...
View detailsCSC 445 Homework 2 (version 1) 算法设计代写 The questions are drawn from the material in Chapters 3, 4, and Appendix A of the text, and the lectures in class on asymptotics, sums, recurrences,...
View details