Search the whole station

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

536

## 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 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.

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

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

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.

### 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 < xand y < y’ or x < yand 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).

### Related recommendations

• #### Python算法代写 数据测试代写 算法代写 Python代写

564

Python2 Python算法代写 测试数据 工单数量自由设定,先设定为 20 机器数量自由设定,先设定为 6,编号为[1 2 3 4 5 6] 工人数量自由设定,先设定为 2,编号为[1 2] PTq[5 10 15 20 25 5 10 15 20 25 5 10 15 20 2...

View details
• #### 算法设计代写 hybrid sorting algorithm代写 sums代写

864

CSC 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
• #### 高效算法与难题代写 Efficient Algorithms and Intractable代写

787

CS 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 details
• #### 算法作业代写 Algorithm代写 CS代写 cs算法课业代写

854

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 details
1