离散数学课业代写 CSE 21代写 算法代写 数学算法代写

CSE 21 Homework 6

离散数学课业代写 Instructions This homework should be done in groups of one to four students, without assistance from anyone besides the instructional staff

Instructions

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.

1. (20 points) 离散数学课业代写

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 2⁸ 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.

2. (20 points) 离散数学课业代写

A max-tree data structure on n = 2^k 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.

3. (18 points) 离散数学课业代写

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代写 论文代写 写手招聘 英国留学生代写