Data structures and supporting libraries

Overview and motivation

• Data Structures: a mean to store and organize data.
• Pick an appropriate DS that support efficient insertions, searches/queries, deletions, and updates.
• Assumption: familiarity with the data structures discussed in the remainder of this episode.
• You only need to know enough so that you can select and use the correct data structures.
  • Understand the strengths, weaknesses, and time/space complexities.

Linear Data Structure: Array

• Many builtin support for Java/C++. We focus on Java for this class.
• Static Array: Builtin supports in Java
• Dynamic Array: ArrayList
• Sorting:
  • Java Array has builtin sort.
  • ArrayList: inherits sort from Java Collections
  • O(n^2): Bubble, Selection, Insertion
  • O(nlog(n)): Merge, Quick, Heap
  • O(n): Counting, Radix, Bucket
• Searching (on a sorted linear data structure):
  • O(n): linear search
  • O(log(n)): binary search (Java Collections)
• Array of Booleans: Java BitSet

Problem’s link

:::::{tab-set} ::::{tab-item} Descriptions

• Initial array: car number at each index.
• Subsequent array: car numbers and their relative displacement.

:::: ::::{tab-item} IO format

• First value is the N number of cars.
  • Next N pairs are the cars and their relative displacement.
  • Repeat with a new N until N == 0.
• N between 2 and 1000
• C between 1 and 10000
• P between -1000000 and 1000000

:::: ::::{tab-item} Thought Process

• Initial visualization:
  • 2-dimensional array, 1 column for car number and 1 column for relative positions.
  • Imagine the starting position, the entire second column would be 0s.
• Input data contain the cars at new index position (first column), and displacement from initital positions.
  • Current index plus (or minus?) displacement will provide initial position.
• Do we actually need a 2-dimensional array?
• What are the possible edge cases for invalid starting positions?

:::: ::::{tab-item} AC

:::: :::::

• Kattis: Baloni
• Kattis: Greedily Increasing Subsequence
• Kattis: Mastermind
• Kattis: Nine Knights
• LeetCode: Valid Sudoku
• LeetCode: Container With Most Water
• LeetCode: Jump Game
• Kattis: Epig Dance Off
• Kattis: Flowshop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 

## Special Sorting Problems


- Inversion Index: count the number of swap to make a list into a sorted order
  - `O(n^2)`: actual runs bubble sort. 
  - `O(nlog(n))`:
    - Modification of Merge Sort: increment count by one when the `front right` is selected in the merging process before the `front left`. 
- Sorting in linear time:
  - Depending on data type
  - `O(n + k)` Counting Sort
  - `O(d * (n + k))` Radix Sort





<figure
  
>
  <picture>
    <!-- Auto scaling with imagemagick -->
    <!--
      See https://www.debugbear.com/blog/responsive-images#w-descriptors-and-the-sizes-attribute and
      https://developer.mozilla.org/en-US/docs/Learn/HTML/Multimedia_and_embedding/Responsive_images for info on defining 'sizes' for responsive images
    -->
    
      
        <source
          class="responsive-img-srcset"
          
            srcset="/assets/img/courses/csc495/02-ds-algo/inversion_index-480.webp 480w,/assets/img/courses/csc495/02-ds-algo/inversion_index-800.webp 800w,/assets/img/courses/csc495/02-ds-algo/inversion_index-1400.webp 1400w,"
            type="image/webp"
          
          
            sizes="95vw"
          
        >
      
    
    <img
      src="/assets/img/courses/csc495/02-ds-algo/inversion_index.png"
      
      
        width="50%"
      
      
        height="auto"
      
      
      
        alt="Inversion Index Example"
      
      
      
        data-zoomable
      
      
        loading="lazy"
      
      onerror="this.onerror=null; $('.responsive-img-srcset').remove();"
    >
  </picture>

  
</figure>





[Problem's link](https://open.kattis.com/problems/height)

:::::{tab-set}
::::{tab-item} Descriptions

- Students placement: Insertion Sort. 
- Count number of displacements due to insertion. 
  
::::
::::{tab-item} IO format

- First value is the `P` number of cases
- Each subsequent `21` integers:
  - First integer is case number (to be used in output)
  - Next twenty integers are the students' heights. 

::::
::::{tab-item} Thought Process

- Read each line and place 20 integers into array
- Perform insertion sort
  - Increase count if a swap is done. 
  
::::
::::{tab-item} AC

<script src="https://gist.github.com/linhbngo/3529c879f8375d9e7eb29f355805bc0c.js?file=kattis_height.java"></script>

::::
:::::

 

Linear Data Structure: Bitmask

• Use an signed interger to represent a lightweight small set of Boolean values.
• This is faster than the BitSet class of Java.
• Limitation: up to 64 items only.
• Example: S = 34
  • Binary: 1 0 0 0 1 0
  • Index: 5 4 3 2 1 0
  • Power of 2: 32 16 8 4 2 1
  • Alphabet: F E D C B A.
  • S can represent {1, 5} or {F, B} or {32, 2}.
• To multiply/divide by 2, shift all bit left/right one:
  • << 1: multiply by 2/shift left 1
  • << 2: multiple by 4/shift left 2
  • >> 1: divide by 2/shift right 1.
• To set (turn on) the bit at position j, use bitwise OR: S = S | (1 << j)
  • 1 << j will shift 1 forward j position, every other bits remain 0.
  • A bitwise OR of the above result with S will set the bit value of S at position j to 1.
• To check if the bit at position j is on, use bitwise AND: T = S & (1 << j).
  • T == 0: j bit is 0
  • T != 0: j bit is 1
• To clear/turn off the bit at position j: S = S & ~(1 << j)
• To flip the bit at position j: S = S ^ (1 << j)
• To get the value of the least significant bit of S that is on: T = ((S) & -(S))
  • Negative S, not flipped bits of S.
• To turn on all bits in a set of size n: S = (1 << n) - 1

Problem’s link

:::::{tab-set} ::::{tab-item} Descriptions

• You will be given total number of cases: N <= 250000
• For each case:
  • You will be given number of bits: 1 <= n <= 30
  • You will be given the k position of the n-bit Reflected Gray Code: 0 <= k <= 2^n.
• Run time is most likely an issue to be considered here.

:::: ::::{tab-item} IO format

• Type 1: The number of cases is given in the first line
• Each case involves parsing two integers.
• Nothing special for output.

:::: ::::{tab-item} Thought Process

• Bit operations would be fastest.
  • Textbook suggestion: one-liner bit manipulation expression.
  • What is the pattern here?
    • Do not look at the value of the bits, it is the output, not the pattern.

• If an even bit is set, the flip the next bit?
  • Not good enough.
• XOR patterns, can you see it?

:::: ::::{tab-item} AC

:::: :::::

Problem’s link

:::::{tab-set} ::::{tab-item} Descriptions

• 3x3 grid, each cell containings 0 or 1
• Function f is the standard cell-based transformation that is similar to the Game of Life’s principle:
  • Each cell’s transformation depends on the adjacent cells.
    • Sum of adjacent cells modulo 2: resulting values will be 0 or 1.
    • Needs to pay attention to border cells.
  • The recursive function starts from the original grid, and there is a chance that over time, it will transform one of the subseqeuent grid back to the original grid.
  • The value i = k_g(h) such that h=f⁽ⁱ⁾(g)
    • Therefore: $k_{g}(f^{i}(g))$ means the number of steps i so that function f transforms g back to itself.

:::: ::::{tab-item} IO format

• First value is the N number of grids.
• Each group of subsequent four lines:
  • One empty line.
  • Three lines, each of which is a string of three characters, either 0 or 1.

:::: ::::{tab-item} Thought Process

• Should have a separate method for f.
  • To know when g is transformed back to itself, this means we need to keep track of the past data structures.
  • Identify the finiteness of i is easy: we only need to know when the current grid matches the original grid.
  • Identify the infinite case (ouptut of -1) is the question.
    • Going back to the finite case, if the grid is transformed back to itself after i steps, this means there is another circular tranformation back to itself after an additional i steps.
    • If there exists a circular transformation that does not contain the original grid, this means we have hit the infinite case.
  • Implication: we need to know if the current grid matches any of the previous grid arrangement.
  • The question: is the number of possible grid arrangement finite or infinite?
    • Recall: Bitmask and Array

• With 9 bits, maximum possible grid arrangements = $2^9$ = 512

:::: ::::{tab-item} AC

:::: :::::

• Kattis: Snapper Hard
• Kattis: Bits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 



## Big Integer


- Use [Java's BigInteger](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/math/BigInteger.html) for this purpose



- Kattis: [Simple Addition](https://open.kattis.com/problems/simpleaddition)
- Kattis: [Wizardsof Odds](https://open.kattis.com/problems/wizardofodds)

 

Linked Data Structures

• Java LinkedList
• Java Stack
• Java Queue

• Java Double-ended Queue

• Valid parentheses
• Check if a parentheses string can be valid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 


## Non-linear Data Structures: Binary Heap (Priority Queue)


- [Java PriorityQueue](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html).
  - From node `i`:
    - To parent: `floor(i)` or `i>>1`
    - To left child: `2 * i` or `i<<1`
    - To right child: `2 * i + 1` or `(i<<1) + 1`
- Heap property:
  - Items on left and right subtree of root `x` are always smaller than `x`. 
  - The root is always the max-value item. 
- Highest value-item can be dequeued in `log(n)` time. 
- New item can be enqueue in `log(n)` time. 
- Important components for:
  - Prim's and Kruskal's algorithms for minimum spanning tree. 
  - Dijkstra's Single Source Shortest Path. 




[Problem's link](https://open.kattis.com/problems/knigsoftheforest)


:::::{tab-set}
::::{tab-item} Descriptions



::::
::::{tab-item} Thought Process

- PriorityQueue
  - Two queues
  - Rewrite comparator to custom compare. 
  - [Writing custom comparator](https://www.callicoder.com/java-priority-queue/)
  - [More description on comparator - how do they compare?](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Comparator.html)

::::
::::{tab-item} AC

<script src="https://gist.github.com/linhbngo/3529c879f8375d9e7eb29f355805bc0c.js?file=kattis_knigsoftheforest.java"></script>

::::
:::::




- Kattis: [Stock Prices](https://open.kattis.com/problems/stockprices)

 

Hash Table

• Java HashMap
• Java HashSet
• What we did in JollyJumper, TreasureHunt, … could be considered a simple naive form of hashing called Direct Addressing Table.

Problem’s link

:::::{tab-set} ::::{tab-item} Descriptions

:::: ::::{tab-item} Thought Process

• Direct Access Table
  • 1 if 0, no action otherwise.
  • Check sum and reset.
• Accepted solution

:::: ::::{tab-item} AC

:::: :::::

• Kattis: What does the fox say?

```

Balanced Binary Search Tree (bBST)

• Binary Search Tree implemented using ADL (Adelson-Velskii Landis) or Red-Black implementation.
• Java TreeMap
• Java TreeSet
• Insertion/search/removal: log(n) time.
• use bBST as a PriorityQueue ADT: lastKey for max value, firstKey for smallest value.

Order Statistics Tree

• Selection: Find the k<sup>th</sup> smallest element of an array of n element.
• Ranking: If the k<sup>th</sup> smallest element is v, then ranking of v is k.
• Selection problem, static data:
  • k=1 and k=n: manual comparison, best run time is n.
  • For other cases: sort then compare, run time nlog(n).
  • Best n algorithm: Utilize RandPartition of QuickSort:
    • q = RandPartition(A, 0, n-1), all element <= A[q] will be placed before the pivot, so A[q] will be in its correct order statistics, which is q+1.
• Selection problem, dynamic data:
  • Construct a bBST
  • Preprocessing: nlog(n)
  • Actual answer: log(n) by traversing down the tree.