数据结构与算法代写 | 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.