# Tag Info

8

This is a very easy question, assuming all scores are integers. Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 zeros. For each score s, we will add 1 to count[s]. To produce the wanted sorted scores, we will output count 1s, count 2s, ..., and finally count 100s. This kind of sorting algorithm is ...

6

Knuth gives a good overview on the history of lists and linked data structures. From The Art of Computer Programming, Volume I, Section 2.6: Linked memory techniques were really born when A. Newell, J. C. Shaw, and H. A. Simon began their investigations of heuristic problem-solving by machine.

4

A balanced binary search tree can support access to arbitrary elements in $O(\log N)$ time per access. Augment the data structure to store, in each node, the number of values stored in the subtree under that node. Then you can find the $i$th largest value in the list in $O(\log N)$ time as well; thus, all basic operations can be done in $O(\log N)$ time.

2

The answer is circular buffer. Such structure could be implemented using array or linked list, but you cannot call explicit array-based circular buffer as linked-list. FSA cannot be "executed" infinitely (type 3 machine only uses fixed input and reads it ones), unless your FSA definition covers Turing Machines.

2

List processing is simultaneously three things in the development of computer science. (1) It is the creation of a genuine dynamic memory structure in a machine that had heretofore been perceived as having fixed structure. It added to our ensemble of operations those that built and modified structure in addition to those that replaced and changed content. (2)...

2

I will assume that initially $y=0$, as this makes no difference in your problem. Look at the very last two elements $a,b$ that you will apply your operation on: The tuple is $([a,b], y$) and, at the next iteration, it will necessarily be $([a+b],$y+a+b$)$, since $a+b = \sum_{i=1}^n x_i$ is a constant, you only want to minimize $y$. Notice that $a$ (resp. ...

2

Yes, using sorting algorithms like merge sort we can achieve this by O(N*logN) we can do better here. The additional information given regarding the bound of test scores is very useful here. do we care about duplicates ? if we are dealing with just scores and doesn't care about the other information like student_name or subject_info and we just want the ...

1

An Indexable Skiplist is a skiplist with the added property that it can quickly lookup the $m$th entry (in order) in a skiplist in $O(\log n)$ time in a skiplist of $n$ entries. In other words, it takes a skiplist that is not an indexable skiplist $O(n)$ time, on average, to find the $m$th element in order in a skiplist, while an ordered skiplist can do ...

1

No, that's not what the author means. The author means the specific sequence of characters the user will actually type. If the user is about to write a letter to Al that might be: 'D'::'e'::'a'::'r'::' '::'A'::'l'::rest The point is that you conceptually have "all" of the characters, and you can (with a bit of care) process this list like any other list.

1

You might not be able to generate lexicographic permutations for any sequence of arbitrary objects. In order to do so, you will need some way of comparing two objects and determining which one is smaller. Assuming you have this, you could use the following algorithm to generate all permutations of a sequence of $n$ objects in lexicographic order. Start by ...

1

You need an interval tree, which queries in O (logn + m) time, where $m$ is the number of intervals the point hits (as opposed to O (n) for n intervals in the data structure). This should produce enough savings that you'll hardly notice the cost of $m$. This output sensitive algorithm is likely the best you can do. The other answer suggests this ...

1

Here's my thought process on this problem: If you only care about "in or out", you can reduce the list of intervals so that no intervals overlap, and the intervals are in sorted order. Sorting by leftmost point takes $O(n \log n)$, then replacing any overlapping pairs with their union takes $O(n)$. But you've said you don't care how long this part takes. ...

Only top voted, non community-wiki answers of a minimum length are eligible