Submission instructions: Call InsertAt$(i,x)b$ times. That is$,$ we will insert one element into $A$ at a time,

and repeat the insertion for each element in X $.$

Shift $A\text{'}$s elements between index $i,n-1$ to the right by $b$ units. And then set

the $A\text{'}$s elements with index $i,i+b$ according to the values in $x.$

Compare these two algorithms and explain which one you prefer. Explain why based on the

run time complexity. $(15$ points$)$

Write a function to determine whether a LinkedList is sorted in the increasing order. Return

true if it is sorted, false otherwise. $(10$ points$)$

struct Node $\{$

int value;

Node$*$ next;

$\}$;

bool Sorted$($Node$*$ head$)\{$

$//$ Your implementation

$\}$

Implement the DeleteAt$($i$)$ function for LinkedList. $(30$ points$)$

Node$*$ DeleteAt$($Node$*$ head, int index$)\{$

$//$ Your implementstion here

$\}$

Standard template library $($STL$)$ of $C++$ has implemented the Sequence interface.

For Sequence, it is called $\text{'}$std: : vector $($:$T$:$)\text{'}$

Here $T$ can be any data type, such as int, double, char, etc.

Solve the following problem and analyze the run time complexity of your algorithm. You can

use STL in this question instead of implementing your own Sequence data structure. You may

want to check the use of $\text{'}$std::vector $\text{'}$ first. $(20$ points$)$

Given an ArrayList$/$Vector of integers numbers, return the sum of all the elements in the

array. Return zero if the array is empty. We assume that the results can be held in the 'int'

type.

Hint:

Access the i$-$th element of vector 'nums': nums$[$i$]$

Get the size of vector 'nums': nums.size$()$

Create a folder named 'homework$\_l_{-}zx\text{'},$ where $\text{'}zx\text{'}$ is your $z-$number. For example,

if my z$-$number is $\text{'}$z$1234567\text{'},$ my folder should be named 'homework$\_$l$\_$z$1234567\text{'}.$

This folder should contain two sub files. $(1)$ A cpp file named

'Homework$\_1.$cpp$\text{'},$ which contains all your codes for this homework, including

Question $1($c$),3,4,$ and $5.$ Use the provided 'Homework$\_1\_$template.cpp$\text{'}$ file as a

starting point and fill in the empty functions. $(2)$ A PDF file named

'homework$\_1.$pdf$\text{'},$ which contains your answers for all the other questions.

Compress the folder as a zip file named as 'homework$\_1\_$zxxx$.$zip'. Similarly, $\text{'}$zxxxx$\text{'}$ is

your z$-$number.

Submit the compressed zip file through Canvas.

Submissions that do not follow the naming conventions can result in loss of points.

Read the following $C++$ codes and answer the following questions.

int GetSum$($int n$)\{$

int sum $=0$;

for $($int i$=\backslash$theta; i AnInsertAt$(i,x)xiA(i,x)xA=\{1,2,3\}x=\{7,8,9,10\}(1,x)AA=\{1,7,8,9,10,2,3\}bxn=10,$ what's the output $of$ the function? $(5$ points$)$

$(b)$ What $is$ the run time complexity $of$ the function, and briefly explain why? $(5$ points$)$

$(c)$ Write a function whose run time complexity $is$ tightly bounded $byO(logn)*(10$ points$)$

Given $an$ ArrayList $\text{'}A\text{'}$ with $n$ elements, answer the following questions. For the following

questions, you can assume that the reserved space $is$ large enough for inserting new elements.

That $is,$ there $isno$ need $to$ consider the cost for reserving a larger space $if$ the array space $is$

full. Meanwhile, the input index $is$ always valid.

$a$