0 votes
1 answer
2
Give a $\Theta(n)$ time nonrecursive procedure that reverses a singly linked list of $n$ elements. The procedure should use no more than constant storage beyond that need...
1 votes
1 answer
4
Implement the dictionary operations $INSERT$, $DELETE$, and $SEARCH$ using singly linked, circular lists. What are the running times of your procedures?
1 votes
2 answers
6
Implement a queue by a singly linked list $L$. The operations of $ENQUEUE$ and $DEQUEUE$ should still take $O(1)$ time.
1 votes
1 answer
7
Implement a stack using a singly linked list $L$. The operations $PUSH$ and $POP$ should still take $O(1)$ time.
0 votes
1 answer
8
Can you implement the dynamic-set operation $INSERT$ on a singly linked list in $O(1)$ time? How about $DELETE$?
4 votes
2 answers
9
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
1 votes
2 answers
10
Show how to implement a queue using two stacks. Analyze the running time of the queue operations.
0 votes
1 answer
12
1 votes
1 answer
14
0 votes
2 answers
17
Show that the second smallest of $n$ elements can be found with $n+\lceil lg\ n \rceil -2$ comparisons in the worst case. (Hint: Also find the smallest element.)
1 votes
1 answer
20
Let $X$ be a random variable that is equal to the number of heads in two flips of a fair coin. What is $E[X^2]$? What is $E^2[X]$?