Contents
`
`Basic Data Types
`3
`Stacks and Queues
`3.1
`Lists
`3.2
`3.3 Arrays
`3.4
`Compressed Boolean Arrays (Type int set)
`3.5
`Random Sources
`3.6
`Pairs, Triples, and such
`3.7
`Strings
`3.8 Making Simple Demos and Tables
`
`Bibliography
`
`Index
`
`page 2
`2
`5
`17
`21
`23
`38
`39
`40
`
`43
`
`44
`
`1
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 001
`
`

`

`3
`Basic Data Types
`
`The basic data types stack, queue, list, array, random number, tuple, and string are ubiqui-
`tous in computing. Most readers are probably thoroughly familiar with them already. All
`sections of this chapter can be read independently.
`
`3.1
`
`Stacks and Queues
`
`A stack is a last-in-first-out store for the elements of some type E and a queue is a first-in-
`first-out store. Both data types store sequences of elements of type E; they differ in the set
`of operations that can be performed on the sequence. In a stack one end of the sequence is
`designated as the top of the stack and all queries and updates on a stack operate on the top
`end of the sequence. In a queue all insertions occur at one end, the rear of the queue, and
`all deletions occur at the other end, the front of the queue. The definitions
`
`a k<E> S;
`
` e e<E> ;
`
`define a stack S and a queue Q for the element type E, respectively. Both structures are
`initially empty. The following operations are available on stacks. If x is an object of type
`E then the insertion S.push(x ) adds x as the new top element. We can inspect the contents
`of a stack: S.top( ) returns the top element and S.pop( ) deletes and returns the top element.
`Of course, both operations are illegal if S is empty. The call S.empty( ) returns true if the
`stack is empty and false otherwise and S.size( ) returns the number of elements in the stack.
`So S.empty( ) is equivalent to S.size( ) == 0. All elements of a stack can be removed by
`S.clear( ).
`We illustrate stacks by a program to evaluate a simple class of expressions. The character
`1 is an expression and if E1 and E2 are expressions then (E1 + E2) and (E1 ∗ E2) are
`
`2
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 002
`
`

`

`3.1 Stacks and Queues
`
`3
`
`expressions. Thus, (1 + 1) and ((1 + 1) ∗ (1 + (1 + 1))) are expressions, but 1 + 1 and
`(1 + 2) are not. The former is not an expression since it is not completely bracketed and the
`latter is not an expression since we only allow the constant 1 as an operand. We will ask
`you in the exercises to evaluate more complex expressions. There is a simple algorithm to
`evaluate expressions. It uses two stacks, a stack<int> S to hold intermediate results and a
`stack<char> Op to hold operator symbols. Initially, both stacks are empty. The expression
`is scanned from left to right. Let c be the current character scanned. If c is an open bracket,
`we do nothing, if c is a 1, we push it onto S, if c is a + or ∗, we push it onto Op, and
`if c is a closing bracket, we remove the two top elements from S, say x and y, and the
`top element from Op, say op, and push the value x op y onto S. When an expression is
`completely scanned, its value is the top element of S, in fact, it is the only element in S.
`The following program assumes that a well-formed expression followed by a dot is given
`on standard input. It prints the value of the expression onto standard output.
`
`hstack demo.ci(cid:17)
`
`#i de<EDA/a k.h>
`
` ai
`
`{ ha ;
`
`a k<i> S; a k< ha> ;
`
`whie   = ead_ ha"ex y b = " != . 
`
`{ wi h 
`
`{ ae  : beak;
`
` ae 1 : { S. h1; beak; }
`
` ae  : { . h ; beak; }
`
` ae  : { . h ; beak; }
`
` ae  : { i x = S. ; i y = S. ;
`
` ha  = . ;
`
`if   =   S. hxy; ee S. hxy;
`
`beak;
`
`}
`
`}
`
`}
`
`  << "\\va e = " << S.  << "\\";
`
`}
`
`On input ((1 + 1) ∗ (1 + (1 + 1))) this program prints 6, on input (1 + (1 + 1)) it prints 3, and
`on input () it crashes because it attempts to pop from an empty stack. This is bad software
`engineering practice and we will ask you in the exercises to remedy this shortcoming.
`We turn to queues. The two ends of a queue are called the front and the rear of the queue,
`respectively. An insertion Q.append(x ) appends x at the rear, Q.top( ) returns the front
`element, and Q.pop( ) deletes and returns the front element. Of course, the latter two calls
`require Q to be non-empty. The function Q.empty( ) checks for emptiness and Q.size( )
`returns the number of elements in the queue. Q.clear( ) removes all elements from the
`queue.
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 003
`
`

`

`4
`
`Basic Data Types
`
`Queues and stacks are implemented as singly linked lists. All operations take constant
`time except clear, which takes linear time. The space requirement is linear. LEDA also
`offers bounded queues and stacks, for example,
`
`b a k<E> S;
`
`defines a stack S that can hold up to n elements. Bounded stacks and queues are imple-
`mented by arrays and hence always use the same amount of space independently of the
`actual number of elements stored in them. They are preferable to unbounded queues and
`stacks when the maximal size is known beforehand and the number of elements stored in
`the data structure is always close to the maximal size.
`In the remainder of this section we show how to implement a queue by two stacks. This
`is to demonstrate the versatility of stacks, to illustrate that the same abstract data type can be
`implemented in many ways, to give an example of an amortized analysis of a data structure,
`and to amuse the user; it is not the implementation of queues used in LEDA. We use two
`stacks Sfront and Srear and split the queue into two parts: If a1, . . . , am is the current
`content of Sfront and b1, . . . , bn is the current contents of Srear with am and bn being the
`top elements, respectively, then am, . . . , a1, b1, . . . , bn is the current contents of the queue.
`Appending an element to the queue is realized by pushing it onto Srear. Popping an element
`from the queue is realized by popping an element from Sfront. If Sfront is empty, we first
`move all elements from Srear to Sfront (by popping from Srear and pushing onto Sfront).
`Note that this will reverse the sequence as it should be.
`
`hstrange queue.hi(cid:17)
`
`#i de <EDA/a k.h>
`
`e ae< a E>
`
` a  e e {
`
`a k<E> Sf  Sea;
`
` bi :
`
` e e<E>{ } // iiiaizai   e y  e e
`
`v id aed  E x{ Sea. hx; }
`
`E  
`
`{ if  Sf .e y 
`
`{ whie  !Sea.e y  Sf . hSea. ; }
`
`if  Sf .e y  e _hade1" e e:   f e y  e e";
`
`e  Sf . ;
`
`}
`
`b e y { e  Sf .e y  Sea.e y; }
`
`i ize
`
`{ e  Sf .ize  Sea.ize; }
`
`};
`
`It is interesting to analyze the time complexity of this queue implementation. We claim
`that a sequence of n queue operations takes total time O(n). To see this we note first that
`the constructor and the operations append, empty, and size run in constant time. A pop
`operation may take an arbitrary amount of time. More precisely, it takes constant time
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 004
`
`

`

`3.2 Lists
`
`5
`
`first
`
`5
`
`3
`
`1
`
`5
`
`last
`
`2
`
`Figure 3.1 A list of five integers.
`
`plus time proportional to the number of elements moved from Srear to Sfront. Since each
`element is moved at most once from Srear to Sfront, we incur a constant cost per element for
`moving elements from Srear to Sfront. We conclude that the time spent in all pop operations
`is linear.
`
`Exercises for 3.1
`1
`Implement the type stack.
`2
`Implement the type queue.
`3
`Extend the expression evaluator such that it complains about illegal inputs.
`4
`Extend the expression evaluator such that it can handle arbitrary integers as operands.
`5
`Extend the expression evaluator such that it can handle expressions that are not com-
`pletely bracketed. The usual precedence rules should be applied, i.e., a + b ∗ c is in-
`terpreted as (a + (b ∗ c)). More specifically, the evaluator should be able to handle all
`expressions that are generated by the following four rules:
`A factor is either an integer or a bracketed expression.
`A term is either a factor or a factor times a term.
`An expression is either a term or a term plus an expression.
`That’s all.
`
`3.2
`
`Lists
`
`Lists are a simple, yet powerful, data type. It is difficult to implement a combinatorial or
`geometric algorithm without using lists. Moreover, the implementation of several LEDA
`data types, e.g., stacks, queues, and graphs, is based on lists. In this section we discuss lists
`for unordered and ordered element types, we sketch the implementation of lists, and in the
`final subsection we treat singly linked lists.
`
`3.2.1 Basics
`
`i<E> ;
`
`declares a list L for elements of type E and initializes it to the empty list. Generally, a list
`L over element type E (type list<E >) is a sequence of items (of predefined type list item),
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 005
`
`

`

`6
`
`Basic Data Types
`
`each holding an element of type E. Figure 3.1 shows a list of integers. It consists of five
`items shown as rectangular boxes. The contents of the first item is 5, the contents of the
`second item is 3, and so on. We call the number of items in a list the length of the list
`and use hx i to denote an item with contents x. Lists offer an extremely rich repertoire of
`operations.
`
`.e y;
`
`checks L for emptiness. Let’s assume that L is non-empty. Then
`
`E
`
`x = .head;
`
`i ie i = .fi;
`
`assign the contents of the first item of L to x and the first item to it. Please pause for a
`moment to grasp the difference. L.first( ) returns the first item and L.head( ) returns the
`contents of the first item. Thus, if L is the list of Figure 3.1, the value of x is now 5 and the
`value of it is the first box. The content of the item (box) it can be accessed by L.contents(it)
`or L[it]. So
`
`x == . ei
`
`evaluates to true and so do
`
`3 == . e. .fi;
`
`.a != .fi;
`
`i == .ed.fi;
`
`.ai == [. y i ed.fi℄;
`
`.a == . y i ed.fi.
`
`We need to explain these expressions a bit further. For a list L, L.head( ) and L.tail( )
`return the contents of the first and last item of L, respectively (5 and 2 in our example) and
`L.first( ) and L.last( ) return the first and last item of L, respectively (the first and the fifth
`box in our example). The items in a list can be viewed as either arranged linearly or arranged
`cyclically. The operations succ and pred support the linear view of a list and the operations
`cyclic succ and cyclic pred support the cyclic view. Thus, if it is an item of a list L different
`from the last item then L.succ(it) returns the successor item of it and L.succ(L.last( ))
`returns nil and if it is different from the first item then L.pred(it) returns the predecessor
`item of it and L.pred(L.first( )) returns nil. L.cyclic pred(it) and L.cyclic succ(it) return the
`cyclic predecessor and successor, respectively, where the cyclic predecessor of the first item
`is the last item. So in the next to last expression above both sides evaluate to the contents of
`the last item of L and in the last expression both sides evaluate to the last item of L.
`We further illustrate the use of items by the member function print. It takes two argu-
`ments, an output stream O and a character space and prints the elements of a list separated
`by space onto O. The default value of space is the space character. It requires that the type
`E offers a function Print(x , O) that prints an object x of type E onto O, see Section 2.8 for
`a discussion of the Print-function for type parameters.
`
`e ae< a E>
`
`v id i<E>::i ea   ha a e = " "
`
`{ i ie i = fi;
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 006
`
`

`

`3.2 Lists
`
`7
`
`whie  i != i 
`
`{ i ei;
`
`if  i != a ie    << a e;
`
`i =  i;
`
`}
`
`}
`
`Note how it steps through the items of the list. It starts at the first item. In the general step,
`we first print the contents of it and then advance it to its successor item. We do so until it
`falls off the list.
`Iterating over the items or elements of a list is a very frequently occurring task and there-
`fore LEDA offers corresponding iteration macros. The iteration statements
`
`f ax << b dy >>
`
`and
`
`f a ie i << b dy >>
`
`step through the elements and items of L, respectively, and execute body for each one of
`them. Thus,
`
`i ie i;
`
`f a ie i i[i℄ ;
`
`E x;
`
`f ax ix ;
`
`prints the elements of L twice. The forall items loop is a macro that expands into
`
`f  i ie  i = .fi;
`
`i =  i  i = .ex ie   i i; 
`
`{ << b dy >> }
`
`and the forall loop is a macro that essentially expands into
`
`f   i ie i = .fi; i; i = . i 
`
`{ x = [i℄;
`
`<< b dy >>;
`
`}
`
`As one can see from the expansions both iteration statements work in time proportional to
`the length of the list. However, since the assignment x = L[it] may be a costly operation
`(if E is a complicated type) it is usually more efficient to use the forall items loop. The fact
`that the iteration statements for lists (and any other LEDA data type, for that matter) are
`realized as macros is a possible source for programming errors; we advise to never write
`forall items(it, f ( )), where f is a function that produces a list, see Sections 2.5 and 13.9
`for details.
`Next, we turn to update operations on lists.
`
`[i℄ = x;
`
`changes the contents of the item it and
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 007
`
`

`

`8
`
`Basic Data Types
`
`.aedx;
`
`adds a new item hx i after the last item of L and returns the item. We may store the item for
`later use:
`
`i ie i = .aedx;
`
`The operations
`
`.de ie i;
`
`. ;
`
`. ;
`
`remove the item it, the first item, and the last item of L, respectively. Each operation returns
`the contents of the item removed. So we may write x = L.pop( ). The program fragment
`
`i<i> ;
`
`.aed5;
`
`.aed3;
`
`i ie i = .aed1;
`
`.aed5;
`
`.aed2;
`
`builds the list of Figure 3.1 and assigns the third item of L to it. So L[it] evaluates to 1 and
`L.del item(it) removes the third item from L, i.e., L consists of four items with contents 5,
`3, 5, and 2, respectively, after the call.
`Two lists L and L1 of the same type can be combined by
`
`.  1di;
`
`where dir determines whether L1 is appended to the rear end (dir = LEDA::after) or front
`end (dir = LEDA::before) of L; before and after are predefined constants. As a side effect,
`conc clears the list L1. The lists L and L1 must be distinct list objects. A list L can be split
`into two parts. If it is an item of L then
`
`.ii12di;
`
`splits L before (dir = LEDA::before) or after (dir = LEDA::after) item it into lists L1 and
`L2. The lists L1 and L2 must be distinct list objects. It is allowed, however, that one of them
`is equal to L. If L is distinct from L1 and L2 then L is empty after the split. Split and conc
`take constant time. Given split and conc, it is easy to write a function splice1 that inserts a
`list L1 after item it into a list L. If it = nil, L1 is added to the front of L.
`
`if  i == i 
`
`.  1EDA::bef e;
`
`ee
`
`{ i<E> 2;
`
`.ii2EDA::afe;
`
`.  1EDA::afe;
`
`.  2EDA::afe;
`
`}
`
`1 splice is a member function of lists and so there is no need to define it at the user level. We give its
`implementation in order to illustrate split and conc.
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 008
`
`

`

`3.2 Lists
`
`9
`
`The apply operator applies a function to all elements of a list, i.e., if f is a function defined
`for objects of type E then
`
`.ayf;
`
`performs the call f (x ) for all items hx i of L. The element x is passed by reference. For
`example, if L is a list of integers then
`
`v id i i i { i; }
`
`.ayi ;
`
`increases all elements of L by one. apply takes linear time plus the time for the function
`calls.
`LEDA provides many ways to reorder the elements of a list.
`
`.evee ie ;
`
`reverses the items in L and
`
`.e e;
`
`randomly permutes the items of L. Both functions take linear time and both functions
`are good examples to illustrate the difference between items and their contents. The call
`L.reverse items( ) does not change the set of items comprising the list L and it does not
`change the contents of any item, it changes the order in which the items are arranged in the
`list. The last item becomes the first, the next to last item becomes the second, and so on.
`Thus,
`
`i ie i = .fi;
`
`.evee ie ;
`
`b b =  i == .a ;
`
`assigns true to b.
`For contrast, we give a piece of code that reverses the contents of the items but leaves the
`order of the items unchanged. It makes use of a function leda swap that swaps the contents
`of two variables of the same type. We use two items it0 and it1 which we position initially
`at the first and last item of L. We interchange their contents and advance both of them. We
`do so as long as the items are distinct and it0 is not the successor of it1. The former test
`guarantees termination for a list of odd length and the latter test guarantees termination for
`a list of even length. If the list is empty the first and the last item are nil and the former test
`guarantees that the loop body is not entered.
`
`/ hi i   he i e eai  f evee ie  /
`
`i ie i0 = .fi;
`
`i ie i1 = .a;
`
`whie  i0 != i1  i0 != . i1 
`
`{ eda wa[i0℄[i1℄;
`
`i0 = . i0;
`
`i1 = .edi1;
`
`}
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 009
`
`

`

`10
`
`Basic Data Types
`
`The above code implements
`
`.evee.
`
`We turn to sorting. We will discuss general sorting methods in the next section and
`discuss bucket sorting now. If f is an integer-valued function on E then
`
`.b ke  f;
`
`sorts L into increasing order as prescribed by f . More precisely, bucket sort rearranges the
`items of L such that the f -values are non-decreasing after the sort and such that the relative
`order of two items with the same f -value is unchanged by the sort. Such a sort is called
`stable. For an example, assume that we apply bucket sort to the list L of Figure 3.1 with f
`the identity function. This will make the third item the first item, the fifth item the second
`item, the second item the third item, the first item the fourth item, and the fourth item the
`fifth item. bucket sort takes time O(n + r − l), where n is the length of the list and l and r
`are the minimum and maximum value of f (e) as e ranges over the elements of the list.
`We give an application of bucket sort. Assume that L is a list of edges of a graph G
`(type list<edge>) and that dfs num is a numbering of the nodes of G (type node array<int>).
`Our goal is to reorder L such that the edges are ordered according to the number of the
`source of the edge, i.e., all edges out of the node with smallest number come first, then all
`edges out of the node with second smallest number, and so on. For an edge e of a graph
`G, G.source(e) returns the source node of the edge and hence dfs num[G.source(e)] is the
`number of the source of the edge. We define a function ord that, given an edge e, returns
`dfs num[G.source(e)] and then call bucket sort with this function.
`
`i dedge e{ e  df  [G.  ee℄; };
`
`.b ke   d;
`
`Lists for Ordered Sets
`3.2.2
`Recall that a type E is linearly ordered if the function int compare(const E&, const E&) is
`defined and establishes a linear order on E, cf. Section 2.10. For lists over linearly ordered
`element types additional operations are available.
`
`i ie .ea hE x;
`
`searches for an occurrence of x in L. It uses compare to compare x with the elements
`of L. If x occurs in L, the leftmost occurrence is returned and if x does not occur in L,
`nil is returned. The running time of search is proportional to the distance of the leftmost
`occurrence of x from the front of the list. We next show how to use search in a primitive
`but highly effective implementation of the set data type, the so-called self-organizing list
`implementation. We realize a set over type E (type so set<E >) as a list over E and use
`search to realize the member operation; the prefix “so” stands for self-organizing. We will
`make the member operation more effective by rearranging the list after each successful
`access. We use the operation move to front(it) that takes an item it of a list, removes it
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 010
`
`

`

`3.2 Lists
`
`11
`
`from its current position, and makes it the first element of the list. The effect of moving
`each accessed item to the front of the list is to collect the frequently accessed items near
`the front of the list. Since the access time in a list is linear in the distance from the front,
`this strategy keeps the expected access time small. We refer the reader to [Meh84, III.6.1.1]
`for the theory of self-organizing lists and turn to the implementation. We derive so set<E >
`from list<E > and accordingly define a so set item as a new name for a list item. We realize
`the membership test by search followed by move to front (if the search was successful), we
`realize insert by a membership test followed by append (if the membership test returned
`false). The other member functions are self-explanatory.
`
`hso set.hi(cid:17)
`
`#i de <EDA/i.h>
`
`yedef i_ie  _e_ie ;
`
`e ae < a E>
`
` a  _e: ivae i<E>{
`
` bi :
`
`b e be  E e
`
`{ i_ie i = ea he;
`
`if i { ve_ _f i; }
`
`e   i != i ;
`
`}
`
`v id ie  E e
`
`{ if ! e bee aede; }
`
` _e_ie fi 
`
`{ e  i<E>::fi; }
`
` _e_ie   _e_ie i  { e  i<E>:: i; }
`
`E e _e_ie i 
`
`{ e  i<E>:: ei; }
`
`};
`
`We give an application of our new data type. We read the file containing the source of this
`chapter, insert all its words into a so set, and finally print the first thirty words in the set.
`
`hso set demoi(cid:17)
`
` ai{
`
` _e<ig> S;
`
`fie_iea "daaye.w";
`
`ig ;
`
`f a T = ed_i e;
`
`whie  >>   S.ie;
`
`  << "i e e ied = " << ed_i eT;
`
` _e_ie i = S.fi;
`
`f  i i = 0; i < 30; i
`
`{  << i 5 == 0 ? "\" : " " << S. ei;
`
`i = S. i;
`
`}
`
`}
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 011
`
`

`

`12
`
`Basic Data Types
`
`The output of this program is:
`
`i e e ied = 13.58
`
`} \ed{exe ie} ee ivey. ad 
`
` f egh he ae
`
` whee   i e i
`
`   ga ha Sh w  big
`
`a i  if y
`
` e hi  ee .egh
`
`As expected, we see frequent English words, because the move-to-front-heuristic tends to
`keep them near the front of the list, and words that occurred near the end of the text, because
`they were accessed last.
`We turn to merging and sorting. If cmp defines a linear order on the element type of L
`then
`
`.  ; 1.  ;
`
`. ege1 
`
`sorts L and L1 according to the linear order and then merges the two sorted lists. If we call
`the functions without the cmp-argument
`
`. ; 1. ;
`
`. ege1;
`
`the default order on the element type is used. Merging two lists of length n and m, respec-
`tively, takes time O(n + m) and sorting a list of n elements takes expected time O(n log n).
`Let us verify this fact experimentally. We start with n equal to 128000 and repeatedly dou-
`ble n. For each value of n we generate a list of length n, make two copies of the list and
`merge them, and we permute the items of the list and then sort the list. For each value of
`n we output n, the measured running time for the merge and the sort, respectively, and the
`running time divided by n and n log n, respectively.
`
`hsort merge timesi(cid:17)
`
` ai
`
`{ i i ax;
`
`hsort merge times: read maxi
`
`f  i  = i;  <= ax;  = 2
`
`{ i<i> ;
`
`f  i j = 0; j < ; j .aedj;
`
`i<i> 1 = ;
`
`i<i> 2 = ;
`
`f a T1 = ed_i e;
`
`1. ege2;
`
`T1 = ed_i eT1;
`
`.e e;
`
`f a T2 = ed_i e;
`
`. ;
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 012
`
`

`

`3.2 Lists
`
`13
`
`Merging
`
`Sorting
`
`n
`
`time
`
`normalized
`
`time
`
`normalized
`
`128000
`
`0.07
`
`256000
`
`0.15
`
`512000
`
`0.3
`
`1024000
`
`0.58
`
`0.547
`
`0.586
`
`0.586
`
`0.566
`
`0.64
`
`1.35
`
`3.15
`
`6.31
`
`0.425
`
`0.423
`
`0.468
`
`0.445
`
`Table 3.1 The table produced by the experiment. All running times are in seconds. The
`normalized time is the 106T /n in the case of merging and 106T /(n log n) in the case of sorting.
`The normalized time of sorting grows slowly. This is due to the increased memory access time
`for larger inputs. You can produce your own table by running sort merge times.
`
`Figure 3.2 The list L before and after the call of permute.
`
`T2 = ed_i eT2;
`
`hsort merge times: produce tablei
`
`}
`
`} T
`
`able 3.1 shows the outcome of the experiment. Does it confirm our statement that the
`running time of merge is (n) and that the running time of sort is (n log n)? In the case of
`merging one may say yes, since the numbers in the third column of our table are essentially
`constant, however, in the case of sorting the answer is a definite no, since the numbers in
`the last column of our table certainly grow. Why is this so? The explanation lies in the
`influence of cache memory on the running time of algorithms.
`The internal memory of modern computers is organized hierarchically. There are at least
`two levels of internal memory, a small and very fast first-level memory (usually called
`cache) and a larger and slower second-level memory (usually called main memory). On
`many machines the hierarchy consists of more than two levels, see [HP90] for an excellent
`account of computer architecture. In the example above we first allocate a list of n items:
`this puts the items consecutively into storage. Then we change the order of the items in the
`list randomly. This leaves the items where they are and changes the links, i.e., after permute
`the links jump around widely in memory, see Figure 3.2. The job of sort is to untangle this
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 013
`
`

`

`14
`
`Basic Data Types
`
`Build
`
`Traverse
`
`Permute
`
`Traverse
`
`0.59
`
`0.16
`
`2.77
`
`0.44
`
`Table 3.2 Illustration of cache effects on running time: We built a list of 1000000 items,
`traversed it, permuted it, and traversed it again. You may perform your own experiments with the
`cache effects demo.
`
`mess. In doing so, it frequently has to access items that are not in the fastest memory. This
`explains the last column of our table, at least qualitatively.
`Next, we attempt a quantitative explanation. Consider the following program:
`
`i<i> ;
`
`f  i i = 0; i < 1000000; i .aedi;
`
`// .e e;
`
`f a T = ed i e;
`
`i ie i = .fi;
`
`whie i != i i = . i;
`
`  << ed i eT;
`
`We make the following assumptions (see [HP90] for a justification): It takes ten machine
`instructions to execute one iteration of the while-loop. Memory is organized in two levels
`and the first level can hold 10000 items. An access to an item that is in first level is serviced
`immediately and an access to an item that is not in the first level costs an additional twenty
`machine cycles. An access to an item in second level moves this item and the seven items
`following it in second-level memory from second-level memory to first-level memory. An
`access to an item that is not in first-level memory in called a cache miss.
`What behavior will we see? First assume that the list is permuted. Since the first level
`memory can hold only 10000 items it is unlikely that the successor of the current item is also
`in memory. We should therefore expect that each iteration of the loop takes thirty machine
`cycles, ten for the instructions executed in the loop and twenty for the transport of an item
`into fast memory. Next assume that the list is not permuted. Now we will incur the access
`time for slow memory only once in eight iterations and hence eight iterations will take a
`total of 100 machine cycles. In contrast, the eight iterations will take a total of 240 machine
`cycles on the permuted list. Thus, permuting the list will make the program about 2.4 times
`slower for large n. For n = 10000 we will see no slowdown yet, as the entire list fits in fast
`memory. For very large n we will see a slowdown of 2.4 and for intermediate n we will see
`a slowdown less than 2.4.
`Table 3.2 shows actual measurements.
`
`The Implementation of Lists
`3.2.3
`Lists are implemented as doubly linked lists. Each item corresponds to a structure (type
`dlink) with three fields, one for the contents of the item and one each for the predecessor
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 014
`
`

`

`3.2 Lists
`
`15
`
`and the successor item, and the list itself is realized by a structure (type dlist) containing
`pointers to the first and last item of the list and additional bookkeeping information. The
`space requirement of a list of n items is 16 + 12n bytes plus the space needed for the
`elements of the list. The contents of an item is either stored directly in the item (if it fits
`into four bytes) or is stored through a pointer, i.e., the e-field of a dlink either contains the
`contents of the item or a pointer to the contents of the item. In the former case there is no
`extra space needed for the elements of the list and in the latter case additional space for n
`objects of type E is needed (here E denotes the type of the objects stored in the list). All of
`this is discussed in detail in the chapter on implementation.
`
`hstorage layout for listsi(cid:17)
`
`yedef dik i_ie ;
`
` a dik {
`
`dik  ;
`
`dik ed;
`
`Ge e;
`
`// f  he e f he ie
`
`// a e: 3 w d = 12 bye
`
`};
`
` a di {
`
`dik h;
`
`// head
`
`dik ;
`
`// ai
`
`ik iea 
`
`// iea  hi i a
`
`i ;
`
`// egh f i
`
`// a e: f  w d = 16 bye
`
`hmember functions of class dlisti
`
`};
`
`There is no space to show the implementations of all member functions. We show only the
`implementation of bucket sort. The implementation is very low-level and therefore hard to
`understand. Bucket sort assumes that a function ord and integers i and j are given such
`that ord maps the elements of the list into the range [i .. j ]. It uses an array bucket of linear
`lists; bucket[i] points to the end of the i-th bucket list as shown in Figure 3.3. Initially,
`all bucket lists are empty. The algorithm runs through the items of the list to be sorted,
`computes for each item x the index k = ord(x → e) of the bucket into which the item
`(recall that x → e contains the object stored in item x) belongs, and appends the item to the
`appropriate bucket. Afterwards, it joins all bucket lists into a single list. This is done from
`right to left.
`
`hlist: bucket sorti(cid:17)
`
`v id di::b ke_ i i i j
`
`{
`
`if h == i e ; // e y i
`
`i  = j i1;
`
`egie i_ie  b ke = ew i_ie [1℄;
`
`egie i_ie    = b ke  ;
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 015
`
`

`

`16
`
`Basic Data Types
`
`Figure 3.3 Illustration of bucket sort. We have two non-empty buckets. The list items are shown
`as rectangular boxes, successor pointers go from left to right, and predecessor pointers go from
`right to left. The pointers from the bucket array to the rears of the bucket lists are shown
`vertically.
`
`egie i_ie  ;
`
`egie i_ie ;
`
`egie i_ie x;
`
`f  = b ke;  <=  ;   = 0;
`
`whie h
`
`{ x = h;
`
`h = h > ;
`
`i k = dx >e;
`
`if  k >= i  k <= j 
`
`{ // add x a ed f k h b ke
`
` = b ke  k i;
`
`x >ed = ;
`
`if   > = x;
`
` = x;
`
`}
`
`ee
`
`e _hade1"b ke_ : va e  f age" ;
`
`}
`
`f  =  ;  == 0;  ;
`
`//  w   i  he ed f he igh    e y b ke
`
`// ake i he ew ai f he i.
`
` = ;
`
` > = i;
`
`f  = ;  >ed;  =  >ed;
`
`//  w   i  he a f hi b ke
`
`// ik b ke  gehe f igh  ef:
`
`//   i  he a f he a b ke
`
`//   i  ed f he ex b ke
`
`whie  >= b ke 
`
`if 
`
`{  > = ;
`
` >ed = ;
`
`f  = ;  >ed;  =  >ed;
`
`}
`
`MOBILEIRON, INC. - EXHIBIT 1007
`Page 016
`
`

`

`3.3 Arrays
`
`17
`
`h = ;
`
`// head = a f ef    e y b ke
`
`deee[℄ b ke;
`
`}
`
`Aren’t you glad that one of us wrote this program?
`
`Singly Linked Lists
`3.2.4
`LEDA also offers singly linked lists (type slist) in which each item only knows its successor.
`They require space 16 + 8n bytes but offer a smaller repertoire of operations. Singly linked
`lists are used to implement stacks and queues.
`
`5
`
`Exercises for 3.2
`1
`Implement queues by singly linked lists.
`2
`Implement more operations on lists, e.g., conc or merge.
`3 Write a procedure that reverses the order of the items in a list.
`4
`Extend the data type so set to a dictionary. Realize a dictionary from