We'd like to implement a data structure RandomQueue with the following interface:
q.add(x) – add an element to the queue
q.remove() - removes a random element from the queue
q.isEmpty() - test if a RandomQueue is empty.
All operations should be fast, i.e. not run in linear time. How can we implement this structure?
A binary heap is initially empty. We call its add() operation N times to add N distinct integers to the heap. How long will this take in the worst case? In the best case?
Prove that we can convert an unordered array of N integers into a binary heap in time O(N) in the worst case.
Write a function evalInfix(s: string) that takes a
string containing an infix expression such as ((2 + 3) * (4 +
5)) and returns an integer containing the value of the expression.
The expression will be fully parenthesized, but there will be no parentheses around individual numbers.
All numbers will contain only a single digit.
The expression may contain embedded spaces.
5. Postfix Evaluation
Write a function evalPostfix(s: string) that takes a
string containing a postfix expression such as 2 3 + 4 5 + *
and returns an integer containing the value of the expression.
All numbers will contain only a single digit.
The expression may contain embedded spaces.
Write a function that takes a undirected graph in adjacency matrix representation, and returns the same graph in adjacency list representation. Assume that the graph's vertices are numbered from 0 to (N – 1).
Write a function that takes a undirected graph in adjacency list representation, and returns the same graph in adjacency matrix representation. Assume that the graph's vertices are numbered from 0 to (N – 1).
8. Depth-First Running Time
Suppose that a graph is connected and has V vertices and E edges. What is the running time of a depth-first search on the graph, as a function of V and E?