question $1$

Given a singly linked and sorted list L of any numbers.

$1,$ what is the worst$-$case running time for searching for an element in L

A proposal was made to improve the search time: we will save another list so that there will be approximately $-$ members only $-$ the first to the last in jumps of $($approximately$).($That is$,$ if for example there are $100$ members in the original list, then the second one will have about $10$ members: the first, the tenth, the twentieth, $...$ the ninetieth and the last$)$

$2.$ Given the two lists $($the original L is strongly linked and sorted as described$),$ explain how a search can be performed and what the running time is in the worst case. $($There is no need to refer to the creation and maintenance of the lists, but only to the search$).$

Clarification: In list L there are votes for the members of the original list $($ie it is possible to reach from each member in L its counterpart in L$).$ See an example

$3.$ Suggest a way to optimize the search given an additional level $("$L$)$

Tutorial: Calculate how you would do this for $1000$ members and for a million members. In order to find the worst case, try to check an element that exists in the list, an element that does not exist, an element that exists relatively at the beginning, relatively at the end and try to generalize your answer.

There is no need to write routines, but only to explain what each level will contain, how the search will be carried out, and what the complications will be in the worst case.

Question $3$:

Given an array A of size n of any numbers $($not necessarily integers$).$ It can be assumed that the numbers are different from each other. We would like to build an array S of size $11$ so that each index and array S will have the number of elements that are to the left of n and are smaller than or equal to $[$A$[$i in the original array. For example, for S$=[0,1,1,2,4,4,5],$ A$[2,7,4,5,15,9,12]$

A$.$ Show that any algorithm for performing the task will perform at least $(1)$ operations.

Hint: first show that if the task in question can be performed in some time T$,$ then it is possible to determine for each member the value of its position in time $($O$($T$.$

B$.$ Describe an algorithm to perform the task that runs in optimal time for the problem.

Question $4$

Propose a data structure S which is maintained by unique integers and supports the following routines at the runtimes indicated next to each routine:

$($Insert$($S: inserting the integer k into the structure S$,$ running time: $($lg$)$

Delete$($S$,$x$)$: deleting the member to which x points from the structure S$,$ runtime: $($Olgn$)$

Change$($S$,$x$)$: changing the sign of the key of the member x that belongs to S$.$ Running time: $($Olgn$)$

that is greater than or equal to S returns the minimal non$-$negative key in : $($Search$\_$Nonnegative$($S$,$k

For the integer k $.$k is not necessarily a value of a key in S$.$ Running time: $($Olgn$)$

Med$\_$Negative$($S: Returns the lower median of the negative key values $$in S$.$ Running time: O$($lgn$)$

Note: In the Change$($x routine, the intention is to change the sign of the member's key from negative to positive or from positive to negative, for example if $3-=($key$($x$)$ then after calling Change$($Sx there will be key$($x$)=3$

The algorithms should be described briefly and precisely. Briefly analyze readiness and complications.