Data Structures Assignment 1 Solution

Assignment Structure
0. Integrity statement
1. Introduction (Backtracking data structures and algorithms) – Explanatory section
2. Consistent and backtracking algorithms - Explanatory section
3. Backtracking algorithms – Programming "warm-up" section
4. Backtracking Dynamic Set ADT – Programming task section
i. Unsorted array implementation
ii. Sorted array implementation
iii. BST implementation
5. Runtime complexity analysis of chapters 2-3 – Theoretical task section

Important Implementation Notes
● It is strongly recommended to read the entire assignment and FAQ section (in the moodle) before you start writing your solutions.
● Your code should be neat and well documented.
● Your implementation should be as efficient as possible. Inefficient implementations will receive a partial score depending on the magnitude of the complexity.
● As you have learned, in this course in general and specifically in this assignment the analysis of runtime complexity is always a worst-case analysis.
● Your code will be tested in the VPL environment, and therefore you must make sure that it compiles and runs in that environment. Code that will not compile will receive a grade of 0. We provide some basic sanity checks for you to make sure that your code compiles.
● The indices throughout this assignment are zero based.
Section 0: Integrity Statement

I assert that the work I submitted is entirely my own.
I have not received any part from any other student in the class, nor did I give parts of it for others to use.
I realize that if my work is found to contain code that is not originally my own, a formal case will be opened against me with the BGU disciplinary committee.

To sign and submit the integrity statement, fill your name/s in the method “signature” in the class IntegrityStatement. If you submit the assignment alone, write your full name, and if you submit the assignment in pairs, write your full names separated by “and”. See the comment in the method “signature”.



Section 1: Introduction
An algorithm is a series of pre-determined steps that when performed on certain objects (input) achieve a desired result (output). A data structure is a method of organizing data in the memory of a computer in order to efficiently use it.
The algorithms that you have seen so far (insertion sort, bubble sort, binary search etc.) always "progress" in a certain direction and never "regret" a decision that they made. For example, after the binary search algorithm decides to search in a certain half of the input, it will never "regret" and re-evaluate that decision. In the same way, the data structures you have seen can only delete existing data and insert new data. There is no way to regret adding or deleting an object. (Given some data structure S and object x, notice that the outcome applying pairs of insert(S,x) and delete(S,x) or vice versa on a data structure, is not necessarily the same as not inserting x.)
However, in more advanced algorithms that can receive dynamic data structures as an input (a data structure that might change during the course of the algorithm), the ability to undo several steps is sometimes needed, and that ability is made possible by backtracking data structures.
Some well known examples where backtracking is used:
A backtracking dynamic abstract data type (ADT) S is an ADT with the additional method:
● backtrack(S): cancels the last data manipulating action performed by the data structure.




Section 2: Consistent and Backtracking Algorithms
We say that an algorithm is consistent if all its defined properties and invariants hold. An invariant is a property which remains unchanged after any modifications/operations are applied.
For example, the insertion sort algorithm maintains the invariant that at the 𝑖𝑡ℎ iteration, the first 𝑖 cells in the array are sorted. If at some point during the execution of the algorithm, one of the considered cells will receive a new value, this invariant might not hold anymore, and the result of the algorithm will therefore be fallacious. (See an illustration in the figure below.)

In such cases where the input given to the algorithm might change during the algorithm's execution, a backtracking algorithm is needed.


Section 3: Warm up Exercises
Recall the Stack ADT:
Stack ADT
● stack create()
● bool isEmpty()
● void push(x)
● Object pop()

In this section you will implement several basic algorithms with the support of backtracking.
These exercises are given in order to allow you to gain some experience with implementing backtracking algorithms using the stack ADT. So, even though it is possible to implement the functions without a stack, you are required to use a stack for backtracking.
Notice: These exercises are mandatory and will be graded.
Implement the following methods:
a. public int backtrackingSearch(int[] arr, int x, int forward, int back, Stack myStack). The method receives an unsorted array of integers arr and searches for the index of the first occurrence of the value x with the added property that after every forward search steps (steps are defined below), backtracks (undoes) back steps. The algorithm stops if it finds the needed index or reaches the end of the array.
Step:
In this algorithm, a step of the search is an iteration of the main loop if the algorithm is implemented iteratively, or a recursive call if it is implemented recursively. See Appendix A for an example.

Invariant:
Every cell of arr that was accessed by the algorithm in previous steps does not contain the value x.

Example:
An illustration of the call backtrackingSearch(A, 10, 3, 2) with the array A={17, 62, 19, 10, 1, 78, 20, 20, 20, 10} appears next. The stack S depicted in the illustration is holding the steps performed by the algorithm.
Disclaimer: the example below only illustrates the idea of the search, but the implementation most probably work in a different way.







b. public int consistentBinSearch(int[] arr, int x, Stack myStack).
The method receives a sorted array of integers and searches for the index of the occurrence of the value x by using the binary search algorithm with the added property that before each step (a step is defined below), the algorithm checks the array for inconsistencies by calling the function:

public static int isConsistent(int[] arr).

The function isConsistent() will be a part of the environment in which your code will be tested in, and you do not need to implement it or worry about its operation.

We recommend you test your code with the following function (explanation below):

double res = Math.random() * 100 – 75; if (res > 0){
return (int) Math.round(res / 10);
}
else {
return 0;
}
}

This function is a simple random function that operates in the following manner:
● Returns 0 ~ 80% of the time
● Returns 1 ~ 10% of the time
● Returns 2 ~ 10% of the time
Step: (This is exactly the same as 1.a)
In this algorithm, a step of the search is an iteration of the main loop if the algorithm is implemented iteratively, or a recursive call if it is implemented recursively. See Appendix B for an example.

Invariants:
1. The array arr is sorted.
2. If at some step of the algorithm a cell 𝒂𝒓𝒓[𝑖] was accessed and compared with 𝑥 and the comparison gave that 𝒂𝒓𝒓[𝑖] was smaller than 𝑥, then for every 𝑗 ≤ 𝑖,
𝒂𝒓𝒓[𝑗] < 𝑥.
3. If at some step of the algorithm a cell 𝒂𝒓𝒓[𝑖] was accessed and compared with 𝑥 and the comparison gave that 𝒂𝒓𝒓[𝑖] was bigger than 𝑥, then for every 𝑗 ≥ 𝑖,
𝒂𝒓𝒓[𝑗] > 𝑥.
Intuitively, invariants 2 and 3 mean that all of the comparisons made by the algorithm so far are still valid.
Example:
An illustration of the call consistentBinSearch(A, 13) with the array A={1, 1, 2, 14, 15, 16, 23, 99, 100, 100, 100, 132, 193, 196, 197}. The stack S depicted in the illustration is holding the steps performed by the algorithm.
Disclaimer: the example below only illustrates the idea of the search, but the implementation most probably work in a different way.



Notice:
● A search that did not find the desired index should return -1.
● The methods are described as if they take the data structure as an input. This is done for generality. Since you implement the assignment in Java, when we write something in the form of operation(S,x), you should write public void operation(int x) and use the standard S.operation(x) form.

Section 4: Backtracking Dynamic Set ADT
In this section you will implement backtracking dynamic set ADT using different underlying data structures.
Your implementations must include all methods of the dynamic set ADT:
● search(S, k)
● insert(S, x)
● delete(S, x)
● minimum(S)
● maximum(S)
● successor(S, x)
● predecessor(S, x)
In addition your implementation must include the following methods:
In order to avoid grade reduction, make sure that your function prints exactly as described. We strongly recommend that you use the tests we provide to verify the correctness of the printing format. (see below printing examples)
backtrack(S) – This method should cancel the last insert(S,x) or delete(S,x) performed by the data structure and return the data-structure to exactly the same state prior to that action. This means that after backtracking, the data structure should look as if the backtracked action was never performed. If no insert/delete actions were performed by the data structure, then the method should not change anything in the data structure.
Notice: The interface of a dynamic set is provided in the assignment files.
Exercises:
i. Implement the backtracking dynamic set ADT using an unsorted array as the underlying data structure.
ii. Implement the backtracking dynamic set ADT using a sorted array as the underlying data structure.
iii. Implement the backtracking dynamic set ADT using a BST as the underlying data structure. The nodes of the BST should contain the fields key and value. Although you will only use the key field in this assignment, the implementation should be general, and every node should contain a null object in its value field.
iv. Implement the double backtracking dynamic set ADT using a BST as the underlying data structure. This ADT has all of the methods of the backtracking dynamic set ADT, and also the method retrack(S).
Intuitively, you are required to implement the mechanism of the "undo" and "redo" as you know them from programs such as Word and PowerPoint for the dynamic set ADT.
The method retrack(S) cancels the cancellation of the last insert(S,x) or delete(S,x) canceled by a backtrack(S) action and returns the data-structure to its state prior to that backtracking action. This action can only be performed if the last modifying operation was a backtrack(S) action, and can only be performed i times consecutively if the last i modifying operations were backtrack(S) actions. After inserting or deleting an item in S, no retrack(S) action can be performed before an action is backtracked. If no backtrack(S) actions were performed by the data structure after the last insert/delete action, then the method retrack(S) should not change anything in the data structure.

Mandatory Remarks!
To simplify the requirements, assume that every element has a unique key, i.e. duplicated keys will never be inserted to the set. Only for array-based implementations:
get(S, i) – returns the key stored in the underlying array at index i. Notice that this is not a part of the dynamic set ADT, and is required only for testing.
Only for BST-based implementations:
getRoot(S) – returns the root of the underlying BST. Notice that this is not a part of the dynamic set ADT, and is required only for testing.

The methods search, minimum, maximum, predecessor and successor should return (if the requested value exists in the set):
a. a tree node if the implementation is BST-based;
b. an index if the implementation is array-based.
If the requested value doesn’t exist in the set:
c. for unsuccessful search, return null for BST-based implementation, and -1 for arraybased implementation;
d. for minimum, maximum, predecessor and successor throw an appropriate exception (Notice!! it should be of type Exception).

Recall that the methods are described as if they take the data structure as an input. This is done for generality. Since you implement the assignment in Java, when we write something in the form of operation(S,x), you should write public void operation(int x) and use the standard S.operation(x) form.

Printing examples:












Example for a series of steps on an unsorted array based dynamic set ADT:
















NOTICE: In the following BST based examples, when the function call is written with the key value, e.g., insert(T,1) and delete(T,20), we mean that we call the function with the reference/pointer to the element itself (the node in case of a tree) with the specified key value. This is, the Node with a key value of 1 (or 20) and not 1 (or 20) as the integer 1 (or 20)!
Example for a series of steps on a BST based dynamic set ADT:








Example for a series of steps on a BST based dynamic set ADT:






Section 4: Analysis of Backtracking Data Structures and Algorithms

For each of the implementations mentioned in sections (i)-(iv), given that the backtracking dynamic set ADT is _______-based, analyze the runtime of the backtrack(S) method when the backtracked action is delete(S,x).
i. Unsorted array based. ii. Sorted array based.
iii. BST based.
iv. AVL-tree based.

For sections (v)-(vi), analyze the minimal space complexity needed for printing a BST in preorder when the implementation is done by _______.
v. Recursion.
vi. Iteration.
Hint: the recursive function which calculates factorial demands 𝑂(𝑛) space complexity, because whenever a recursive call is committed, a new variable for the numerical parameter is kept in the memory, and there are 𝑛 −1 recursive calls.
You are supplied a class in the templates with 6 methods, each for any of the section of this question. All the answers are marked as comments. Uncomment the correct answers in each section. For example, if the answer for section ii is 𝛩(𝑓(𝑛)), then you should return the following (note which line is uncomment): public static String section_ii() { String answer = null;
// answer = “Theta(t(n))”;
answer = “Theta(f(n))”; // answer = “Theta(g(n))”;
// answer = “Theta(h(n))”;
return answer;
}
Assume that the implementations are efficient, and the runtimes are as you have seen in the lectures and practical sessions.
Appendix A:
Below you can see two pseudo-code "implementations" of a function that iteratively searches an unsorted array arr for the value x. The highlighted part is a search step. Notice that the first uses a for loop, and the second uses a while loop. This pseudo-code is only intended to give some intuition of what a search step is.
[The break command means to abort the execution of the loop (either for loop or while loop) and continue from the line after the loop.]

𝑠𝑒𝑎𝑟𝑐ℎ(𝑎𝑟𝑟, 𝑥):
𝑛 ← 𝑠𝑖𝑧𝑒(𝑎𝑟𝑟)
𝑓𝑜𝑟 𝑖 = 0 → (𝑛 − 1) 𝑑𝑜:
𝑖𝑓 (𝑎𝑟𝑟[𝑖] = 𝑥): 𝑏𝑟𝑒𝑎𝑘
𝑒𝑛𝑑 //𝑓𝑜𝑟
𝑖𝑓 (𝑎𝑟𝑟[𝑖] = 𝑥): 𝑟𝑒𝑡𝑢𝑟𝑛 𝑖
𝑒𝑙𝑠𝑒 ∶ 𝑟𝑒𝑡𝑢𝑟𝑛 – 1
𝑒𝑛𝑑 //𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛

𝑠𝑒𝑎𝑟𝑐ℎ(𝑎𝑟𝑟, 𝑥):
𝑛 ← 𝑠𝑖𝑧𝑒(𝑎𝑟𝑟)
𝑖 = 0
𝑤ℎ𝑖𝑙𝑒 𝑖 < 𝑛 𝑑𝑜:
𝑐𝑢𝑟𝑟 ← 𝑎𝑟𝑟[𝑖]
𝑖𝑓 (𝑐𝑢𝑟𝑟 = 𝑥): 𝑏𝑟𝑒𝑎𝑘
𝑖 ← 𝑖 + 1
𝑒𝑛𝑑 //𝑤ℎ𝑖𝑙𝑒
𝑖𝑓 (𝑎𝑟𝑟[𝑐𝑢𝑟𝑟] = 𝑥): 𝑟𝑒𝑡𝑢𝑟𝑛 𝑐𝑢𝑟𝑟
𝑒𝑙𝑠𝑒 ∶ 𝑟𝑒𝑡𝑢𝑟𝑛 – 1
𝑒𝑛𝑑 //𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛
Appendix B:
In the following pseudo-code of a function that searches a sorted array arr for the value x using the binary search algorithm. The highlighted part is a search step. This pseudo-code is only intended to give some intuition of what a search step is.

𝑏𝑖𝑛_𝑠𝑒𝑎𝑟𝑐ℎ(𝑎𝑟𝑟, 𝑥):
𝑚𝑖𝑛 ← 0
𝑚𝑎𝑥 ← 𝑠𝑖𝑧𝑒(𝑎𝑟𝑟) – 1
𝑤ℎ𝑖𝑙𝑒 max ≥ min 𝑑𝑜:
𝑐𝑢𝑟𝑟 ← ⌊⌋
𝑚𝑎𝑥+𝑚𝑖𝑛

2
𝑖𝑓 (𝑎𝑟𝑟[𝑐𝑢𝑟𝑟] = 𝑥): 𝑏𝑟𝑒𝑎𝑘
𝑒𝑙𝑠𝑒 ∶
𝑖𝑓 (𝑎𝑟𝑟[𝑐𝑢𝑟𝑟] < 𝑥): 𝑚𝑎𝑥 ← 𝑐𝑢𝑟𝑟 − 1
𝑒𝑙𝑠𝑒 ∶
𝑚𝑖𝑛 ← 𝑐𝑢𝑟𝑟 + 1
𝑒𝑛𝑑 //𝑤ℎ𝑖𝑙𝑒
𝑖𝑓 (max ≥ 𝑚𝑖𝑛): 𝑟𝑒𝑡𝑢𝑟𝑛 𝑐𝑢𝑟𝑟
𝑒𝑙𝑠𝑒 ∶ 𝑟𝑒𝑡𝑢𝑟𝑛 – 1
𝑒𝑛𝑑 //𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛