# 数据结构与算法代写 | CIS 477 Fall

这个作业是完成数据结构中的堆栈、np问题等算法问题

CIS 477 Fall

**Problem 1: **

In the homework, you saw the special data structure of a stack

with the MultiPop operation. Suppose that we again have a stack with this

operation, and all operations have the same costs as before, except MultiPop

now has an additional overhead cost of $1 each time it is called (regardless

of how many elements are being multipopped). Use amortized analysis to

determine the average cost per operation for the worst-case sequence of operations on this stack.

**Problem 2: **

In class, we saw how to implement a queue using two stacks.

The user has access to two operations: Enqueue and Dequeue. Behind

the scenes, the OS implements these using Push and Pop on the two stacks

as described in class. Suppose that we change this problem so that now

popping from a stack still costs $1, but pushing onto a stack costs $2 if that

stack currently has any items on it, and $1 if the stack is currently empty.

Use amortized analysis to determine the average cost per operation for the

worst-case sequence of operations on this queue.

**Problem 3: **

In class, we learned about the extensible array data structure.

Suppose we change this so that now instead of doubling the array size when

it is full, we triple the size. The costs are the same as in class: i.e., writing

an element (either originally or as part of a copy) costs $1, and there are no

costs associated with things like allocating memory. Use amortized analysis

to determine the average cost per operation for the worst-case sequence of

operations on this extensible array.

**Problem 4: **

In class, we saw how to implement a queue using two stacks.

The user has access to two operations: Enqueue and Dequeue. Behind

the scenes, the OS implements these using Push and Pop on the two stacks

as described in class. Suppose that we change this problem so that now pushing onto Stack A costs $1 and popping from Stack A costs $2; and pushing

onto Stack B costs $2 and popping from Stack B costs $1. Use amortized

analysis to determine the average cost per operation for the worst-case sequence of operations on this queue.

**Problem 5:**

The Half-Edge Capture problem is as follows: Given a graph

G and some value c, return a set of at most c vertices in the graph such that

1

at least half of the edges in the graph are adjacent to at least one of those c

vertices (in other words, at least half of the edges must have at least one of

their two endpoints included in the set of c vertices). Show that Half-Edge

Capture is NP-Complete.

**Problem 6: **

The Weighted Complete Path problem is as follows: Suppose you are given an undirected graph G with weights on each edge, specific

starting and ending nodes s and t, and an integer k. Find a path from s

to t such that the path touches every node in the graph exactly once, and

has total weight less than or equal to k. Show that Weighted Complete

Path is NP-Complete.