Data Structure and Algorithm Homework 1 Solution

Problem 1 - Complexity (80 + 20 pts)

Warning: Conciseness makes everyone’s life easier. You should answer Problem 1 within 3 pages, or you will get some penalties. Also, make sure your answer is clear and easy to read for others.

Suppose that f and g are real-valued functions defined on R+, and g(x) is strictly positive for all sufficiently large x (formally, there is some x1 such that g(x) > 0 for all x > x1). Recall the following asymptotic notations:

    • f (x) = O(g(x)) if and only if there exist positive numbers c and x0 such that

|f (x)| ≤ cg(x) for all x > x0.

    • f (x) = Ω(g(x)) if and only if there exist positive numbers c and x0 such that

|f (x)| ≥ cg(x) for all x > x0.

    • f (x) = Θ(g(x)) if and only if f (x) = O(g(x)) and f (x) = Ω(g(x)).

Note that the definitions here may be slightly different to other versions in different text-books, but they may come in handy in some problems of this section. We ask you to use our definitions here to answer the subproblems below.

Here are some sample tasks and solutions for reference:

    • The word ”brief” means ”very short”. An example of a brief explanation:

Sample task: Write down the time complexity for this function using the Θ notation along with an expression of n.

worship-127-double-n(n)

    • for i = 1..n

    • for j = 1..2n

    • print(”Praise 127”)

Sample solution 1: The iteration of the loops are n and 2n respectively, so there are 2n2 iterations. Hence the time complexity is Θ(n2). 

Sample solution 2: 顯然他總共跑 2n2 次，所以是 Θ(n2)。

3
• An example of a formal proof:

Note: Recall that f (x) = O(g(x)) if and only if there exist positive numbers c and x0 such that

|f (x)| ≤ cg(x) for all x > x0.

If you prove the correctness of a statement S by formal definition, you should specify all constants like c and x0.

Sample problem:  Prove that an + b = Θ(n), where a and b are positive constants.

Sample full-credit formal proof 1: Observe that an ≤ an + b ≤ 2an for n > 2ab , so an + b = Θ(n). 


Sample full-credit formal proof 2: Rewrite an + b = n(a + bn−1). Obviously we have limn→∞(a + bn−1) = a, so for any fixed ϵ > 0, there is some large N such that |a − (a + bn−1)| < ϵ. Take ϵ = a2 , then for some large N, we have the inequality:

a2 ≤ a + bn−1 ≤ 32a


Multiply it by n we have

an2 ≤ an + b ≤ 3an2

so an + b = Θ(n).


Sample full-credit formal proof 3: Obviously an = O(n) and b = O(n), by the theorem 併吞律 we have an + b = O(n). 

Now, imagine that you are on the magic train heading to the empire of God 127, the master of algorithm. To worship God 127, you should have some skills to evaluate the complexity of simple function calls.

Read the following pseudo code carefully. Write down the time complexity for each of the following function using the Θ notation along with an expression of n. Your answer should be as simple as possible. For instance, Θ(n1 + lg(n543) + 8763n2) should be written as Θ(n2). Your answer should also come with a brief explanation.

    1. (5 pts)

func-a(n)

1  sum = 0, i = 1

2  while sum < n

3sum = sum + i

4i = i + 1

4
    2. (5 pts)

func-b(n)

1  m = 2

2  while m < n

3m = m ∗ m

    3. (10 pts)

func-c(n)

1  if n > 87506055

2func-c(n − 1)

3func-c(n − 1)

4func-c(n − 1)

5func-c(n − 1)

6  elseif n > 0

7func-c(n − 1)

8func-c(n − 1)

9func-c(n − 1)

Finally, you arrives at the entrance of 127’s empire. However, the soldiers won’t let you pass the entrance if you are not familiar with asymptotic notations. For the next six subproblems, consider n to be a positive integer and f (n), g(n), i(n), j(n) to be positive, monotonically in-creasing functions with non-negative domains.1 Prove or disprove each of the statement. You should provide a formal proof if you believe the statement to be true, or a counterexample if you believe the statement to be false.

4.
(10 pts) (Prove or disprove) f (n) + g(n) = Θ( max(f (n), g(n))
).


5.
(10
pts) (Prove or disprove)
If
f (n) = O i(n)
and g(n) = O j(n) , then f (n)
·
g(n) =

O i(n)
·
j(n) .

(  )
(
)



(


)




2g(n)).


6.
(10
pts) (Prove or disprove) If f (n) = O(g(n)), then 2f (n) = O(



Did you have fun warming up? Now the soldiers are giving you more challenging ones. Try your best! Some calculus tricks may help. We encourage you to use results from the lecture slides to make your proof shorter.

7. (10 pts) (Prove or disprove) The harmonic series

n
1

= Θ(lg n).








k=1 k
























if for all n
, n


that n











1A function f is monotonically increasing


2


1
< n
2
, we have
f(n
)

f(n
)
.
1


such∑






1

≤
2





















5
8. (10 pts) (Prove or disprove) lg(n!) = Θ(n lg n).

Finally, you get to meet God 127 face to face. He decides to give you the final trial with a recursive function to test if you are able to pass this course. ;-)

9. (10 pts) Define
1,






f (n) =


n


if n = 1


2f (
⌊


⌋
) + n lg n,
otherwise




2




Please find the tightest bound of f (n) with Θ notation. You should provide a proof to get credits. Answers without any proof will receive NO credits.

Congratulations on completing all the proof—or not? Those mathematically inclined can try two more subproblems below. Those subproblems are harder and do not carry many points, but tackling them surely gives you some self-satisfaction!

10. (Bonus 10 pts) (Prove or disprove) Let {fk(n)}∞k=1 be a sequence of real-valued functions defined on R+ such that fk(n) = O(n2) for k ∈ N, then ∑n fk(n) = O(n3).
k=1

    11. (Bonus 10 pts) The following pseudo code is the famous Euclidean algorithm for comput-ing the greatest common divisor—hmm, where have you seen this task? ;-)

euclidean-gcd(m, n)

    • while m ≠ 0

    • (m, n) = (n mod m, m)

3  return n

Please show that the worst time complexity for this algorithm is O(lg(m + n)).





















6
Problem 2 - Stack / Queue (60 pts)

@

First, please design an algorithm that reverses the content of a source queue using an additional helper queue that is initially empty. For example, consider a source queue originally contains [1,2,3], where 3 is at the front of the queue. After running the algorithm, the source queue should become [3,2,1], where 1 is at the front, with the helper queue empty. The algorithm can only use O(1)-extra space in addition to the two queues. You have to guarantee that the algorithm runs in O(n2)-time where n is the number of elements in the queue. In addition to the usual enqueue, dequeue, and f ront of the queue, you may assume that the queues above also supports size, which returns the current number of elements in the queue.

    1. (10 pts) Show your algorithm with any pseudo code.

    2. (10 pts) Prove that your algorithm in the previous subproblem runs in O(n2)-time.

Next, let’s play with another data structure. Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double-ended queue) allows insertion and deletion at both ends. Please use any pseudo code to implement a deque by using two stacks and at most O(1)-extra space, and answer the following five subproblems. A deque should support four operations, as listed below. You can assume that there is no invalid operation like popping from an empty deque.

    3. (10 pts) Illustrate your design, in particular, how you achieve each of the four operations below (preferably with figures).

Then, briefly describe the time complexity of each operation under your design—the faster the better.

    4. (5 pts) void push_front(int x): Insert an element to the front end of the deque.

    5. (5 pts) void push_back(int x): Insert an element to the back end of the deque.

    6. (5 pts) int pop_front(): Remove and return the element at the front end of the deque.

    7. (5 pts) int pop_back(): Remove and return the element at the back end of the deque.

Finally, let’s have more fun with the stack. Arguably the simplest way to implement a stack is to use a consecutive array and push to the “end” of the consecutive region. However, the array-based one is limited by the allocated capacity of the underlying array. One way to conquer the limitation is to dynamically enlarge the array when it is full, which is commonly called a dynamic-array implementation.

7
    8. (10 pts) Consider the following dynamic-array implementation of a stack; please analyze the time needed for n consecutive push operations. You can assume that each realloc operation takes O(m)-time where m is the number of elements in the array.

struct Stack {

int top;

int capacity;

int *arr;

}


struct Stack *createStack() {

struct Stack *S = malloc(sizeof(struct Stack));

S->capacity = 1;

S->top = -1;

S->arr = (int*)malloc(S->capacity * sizeof(int)); return S;

}


int isFullStack(struct Stack *S) {

return (S->top == S->capacity-1);

}


void enlarge(struct Stack *S) {

int new_capacity = (S->capacity * 3);

S->capacity = new_capacity;

S->arr = (int*)realloc(S->arr, new_capacity * sizeof(int));

}


void push(struct Stack *S, int data) { S->arr[++S->top] = data;

if (isFullStack(S))

enlarge(S);

}








8
Problem 3 - Array / Linked Lists (60 pts)

For all subproblems below, your answers should include the following parts:

    (a) Describe the workflow of your algorithm and briefly explain why it works.

    (b) Analyze the time complexity and extra-space complexity of your algorithm. If your algorithm is not efficient enough in time or in space, you may not get full points.

First, consider a read-only array A that contains n integers ∈ {0, 1, . . . , n −1}, where “read-only” means that you cannot modify the contents of the array. A frog, starting from some legitimate initial position within A, jumps within A[0], A[1], . . . , A[n − 1] by the following rule.

    • If the frog is on the ith position and A[i] ≠ i, it will jump to the (A[i])th position.

    • If the frog is on the ith position and A[i] = i, it will stop.

    1. (15 pts) Given the initial position of the frog, design an algorithm that computes whether the frog will stop somewhere or keep jumping forever.

    2. (15 pts) Given an A such that A[i] ≠ i, ∀i 0 ≤ i < n, which means that the frog is doomed to keep jumping forever from any initial position. Then, the frog will eventually jump into a “loop” of indices. Given the initial position of the frog, design an algorithm that computes the length of the loop.

For example, A = [1, 0, 4, 2, 3, 1, 4, 6].

        ◦ When the initial position is on 0, 1, or 5, the frog jumps into the loop 0 → 1 → 0 → 1 · · · . The length of the loop is 2.

        ◦ When the initial position is on 2, 3, 4, 6, or 7, the frog jumps into the loop 2 → 4 → 3 → 2 → 4 → 3 · · · . The length of the loop is 3.

Enough with the frog. The next subproblem is about the sorted array.

    3. (15 pts) A is a strictly increasing array with n integers, where A = [a0, a1, · · · , an−2, an−1], n ≥ 3. Now, consider the following definitions.

        ◦ As,t = [as, as+1, · · · , at−2, at−1], where 0 ≤ s < t ≤ n

        ◦ Ms,t = the median of As,t

        ◦ f (i, j) = max(M0,i, Mi,j , Mj,n) − min(M0,i, Mi,j , Mj,n), where 0 < i < j < n




9
In short, A is partitioned into three subarrays by index i and index j. Each subarray has its own median. f (i, j) equals to ”the maximum of three medians” minus ”the minimum of three medians”.

Design an algorithm to find a pair (i, j), where 0 < i < j < n, such that f (i, j) is minimized.

Finally, let’s play with a new kind of linked list.

    4. (15 pts) A circularly linked list is a linked list such that the last node of the linked list is connected to the head instead of some nil (NULL) value. We call a node A decreasing in the circularly linked list if A.next.value < A.value.

Consider a circularly linked list L with n integers, represented by some head node. Assume that there are two decreasing nodes within L. Design an algorithm that “sorts” all nodes within L such that head points to a new circularly linked list with only one decreasing node. We expect the algorithm to run in O(n)-time and O(1)-extra-space .










































10
Programming Part





Problem 4 - Evil Eval (100 pts)

Problem Description

In this problem, you “simply” have to implement a calculator like what has been taught in the classes. The calculator should support the following operator on double-precision floating points with correct precedence:

    • arithmetic operators: +, -, *, /

    • parentheses: (, )

It is guaranteed that the divisor would not be zero during the process of the calculation. Please do not try to solve this problem by calling other program in your source code. If (and

only if) you patiently, wholeheartedly code the homework out, you will gain a better coding skill and a deeper understanding of the data structure!

Input

The input contains T lines, each representing an arithmetic expression.


Output

For each test case print a double-precision floating point number in one line, which indicates the answer of the expression. Your solution will be considered correct if the absolute or relative error between the answer and your output is less than 10−12. Formally, let your answer be a,
and the jury’s answer be b, your answer is accepted if and only if    |a−b|    ≤ 10−12

max(1,|b|)

Constraints

    • 0 < the length of each line L < 106

    • 0 < ai < 108 for each number ai in the expression

    • L·T ≤106

    • every numbers in the input will be an integer containing only of digits. We expect the final output to be a floating point number, though.




11
Subtask 1 (25 pts)

• the operator include only +, -


Subtask 2 (25 pts)

• the operators include only +, -, *, /


Subtask 3 (50 pts)

• all operators are possible


Sample Cases

Sample Input 1

1+3-2


Sample Output 1

2.000000000000000


Sample Input 2

1+2*3

1-2*3


Sample Output 2

7.000000000000000

-5.000000000000000


Sample Input 3

(1+2)*3


Sample Output 3

9.000000000000000





12
Problem 5 - Waston and Abili (100 pts)

Problem Description

Waston and Abili runs a consulting detective service. In a recent case, a train storage station of British Railway drew their attention. They suspect that the operator of the station hid something illegal in the train storage station by manipulating the records. To check if there is any mismatch with the official record, they sneaked into the station and have only one night to find out which train cabin is not recorded.

As their friend and one who has extreme self-confidence in programming, you want to write a program that reads in the parking logs and print out a map of the storage station. The log begins with two integers, k, n, denoting the mount of parking rails and the records in the log respectively.

There are three types of logs in the official record.

    1. Cabin with label l enters the r-th rail

In this station, each parking rail has only one entrance, which is also the exit, so only the last cabin that entered the rail can leave the rail. If a cabin with label l entered the r-th parking rail, the corresponding log will be enter r l

    2. The last cabin stored in the r-th rail leaves that rail

If the last cabin of r-th rail leaves the station, the corresponding log will be leave r

    3. The ra-th rail is shut down for maintenance, all the cabins is migrated to the rb-th rail one by one.

Sometimes, the operator shutdowns certain rails for railway maintenance. In such sce-nario, all cabins of the maintenance rail leaves and enters another one by one. If the ra-th rail is shut down, and all its cabins is migrated into the rb-th cabin, then the correspond-ing log will be migrate r_a r_b


There might be some mistakes in the logs, for example, a cabin leaving from an empty rail. In such case, just ignore all the illegal logs. After processing all logs, please output what the cabin arrangement should be like in the station from the 0-th rail to (k − 1)-th rail.

Below is an illustration of a station with 3 rails and 6 cabins.




13























Input Format

The first line contains two integer k, n. The next n lines may be in below three formats:

    1. enter follow by two integer r, l

    2. leave follow by one integer r

    3. migrate follow by two integer ra, rb


Output Format

You should output k lines, each containing the labels of train cabins parked in each rail by the order they entered the rail. For example, the i-th line contains the labels of cabins parked in rail i.

Constraint


    1. 1 ≤ n ≤ 106

    2. 2 ≤ k ≤ 103

    3. 0 ≤ r, ra, rb < k, ra ≠ rb

    4. 0 ≤ l ≤ 104, noted that l is not necessarily unique




14
Subtasks

Subtask 1 (25 pts)

    • 1 ≤ n ≤ 103

    • 1 ≤ k ≤ 10

    • No migrate operation


Subtask 2 (50 pts)

    • 1 ≤ n ≤ 104

    • 10 ≤ k

Subtask 3 (25 pts)

    • No ⊕ther constraints!

    • You might want to search for “how to reverse a linked list in less than O(n) time” to solve this problem

    • GL&HF:P


Sample Cases

Sample Input 1    Sample Output 1

3 7

enter 1 1    1 2 4 3

enter
1
2
enter
2
3

enter 2
4

enter
2
5

leave
2


migrate 2
1

Note that there are two empty lines , one above and the other below 1 2 4 3. For more sample cases, go to the problem page on DSA Judge.




15
Problem 6 - K-Least Element in the Sequence (100 pts)

Problem Description

Giver is a beginner at programming, so he practices hard everyday for improving his skill. One day, someone asks him a problem: “Given a sequence a1, a2, . . . , an, please find the k-least element in the sequence.” However, Giver is so clever that this problem is too easy for him. Therefore, He tries to modify the problem to make it harder. Now, the problem becomes as follows:


Given a sequence a1, a2, . . . , an, you are asked to support the following operations.

    • Insert i x - insert an integer x before the ith element of the sequence. If i − 1 equals the length of the sequence, then insert x at the end of it.
    • Delete i - delete the ith element of the sequence.

    • Reverse l r - reverse the elements between the interval [l, r] of the sequence.

    • Query l r k - find the k-least element between the interval [l, r] of the sequence.


Input

The first line contains two integers n, q (1 ≤ n, q ≤ 50000), representing the length of the initial sequence and the number of operations respectively. The second line contains the initial sequence, which consists of n integers a1, a2, . . . , an (−105 ≤ a1, a2, . . . , an ≤ 105).
Each of the next q lines is an operation with the format mentioned above.

It is guaranteed that all operations are valid. Formally, suppose that the current length of the sequence is N, then it must satisfy the following constraints.

    • Insert i x: 1 ≤ i ≤ N + 1, −105 ≤ x ≤ 105.

    • Delete i: 1 ≤ i ≤ N.

    • Reverse l r: 1 ≤ l ≤ r ≤ N.

    • Query l r k: 1 ≤ l ≤ r ≤ N, 1 ≤ k ≤ r − l + 1.

Output

For each ”Query l r k” operation, print an integer, representing the k-least integer between the lth element and the rth element.




16

Subtask 1 (20 pts)
Subtask 3 (5 pts)
• n, q ≤ 3000.
• There are only “Insert”, “Delete”, “Re-

verse” operations.



Subtask 2 (25 pts)
Subtask 4 (50 %)
• There are only “Query” operations.
• No other constraints.



Sample Input 1
Sample Output 1
5 5


-3
-1014-3-5
-10
Query 4 4 1
-3
Query 1 2
1
4
Query 4
5
2
-5
Query 2
3
2

Query 4
5
1



Sample Input 2
Sample Output 2
5
5
4
-244-72
-7
Delete 5

Delete 1

Insert 2 6

Query 3 3 1

Query 4 4 1

Sample Input 3
Sample Output 3
5 5
-6
-67330
-6
Reverse 1 4

Insert 3 -6


Query
3
4
1
Reverse 4
5
Query
1
4
2


17
Hints

    1. You may need the data structure like linked list to support efficient modification.

        ◦ Due to the bad performance on interval operation and indexing, you may want to reduce the number of nodes.

        ◦ Try to bind some elements into one node, that is, store a sequence of elements using an sequence in a node.

        ◦ Try to maintain the nodes such that both the number of nodes and the number of elements in a node are not too big. That is, you may need to split a node or rebuild the data structure if one of them is too large.

    2. How to reverse a segment that can be represented by a sequence of nodes? what if not, can you make it become the same case? You may need to add a tag on each node and reverse it some time later to preserve a good time complexity.

    3. You may need to use the binary search algorithm when finding the k-least element. You may also need to maintain some more information for each node to support efficient query.








































18