Linear-DS.md

Linear DS

---

Outline

1. Static Arrays

   1. Creating 1D, 2D, ND Static Arrays.
   2. Accessing Time.
   3. Traversing a static array with N dimensions.
   4. 1D Array Manipulation.
   5. 2D Array Manipulation.
      • Example: Rotating a matrix.
   6. Tricks and Pitfalls.

2. Dynamically-Resizable Arrays

   1. Creating ArrayLists.
   2. Important functions and their complexities:
      • add, get, set, set, indexOf, size
   3. How resizing is done internally + resizing complexity.
   4. Using Static Arrays with Dynamically-Resizable Arrays.
      • ArrayList<Integer> a[]

3. Bitmasks

   1. Bits as a data structure.
   2. Bit Manipulation.

4. BitSets

   1. Important functions and their complexities:
      • reset, set, cardinality, flip, nextSetBit, xor
   2. Core idea behind BitSets.

5. LinkedLists

   1. Important functions and their complexities:
      • get, add, remove

6. Stacks

   1. Important functions and their complexities.
      • pop, push, peek, isEmpty
   2. Applications on Stacks.

7. Queues

   1. Important functions and their complexities.
   2. Applications on Queues.

8. Dequeues

---

Material Resources

Resource	Points Covered
CP section: 2.2	Most of the outline points
G4G Apps on Arrays	1-iv 1D Array Manipulation
G4G Apps on Stacks	6-ii Applications on Stacks
G4G Apps on Queues	7-ii Applications on Queues
Supp Material	1-ii, 1-vi, 4-ii

---

Problem Sets

Problem Set #1

Problem	Tags	Notes	Solution
Boy or Girl	1D Array manipulation	use a boolean array to keep track whether a character is found or not.	Link
Splitting Numbers	Bit Manipulation	basic bit manipulation but could be solved with strings + binary decimal conversion.	Link
Error Correction	2D Array Manipulation	count the number of '1's for each row/col, all of them must be even , if there is an error then check if it is on the same row and col	Link
Rails	Stacks	use a stack to simulate the process	Link
Throwing cards away I	Queues	simulate the process using a queue	Link
Broken Keyboard	Dequeues , Linked lists	think of a data structure that allow insertion from both sides	Link

Problem Set #2

Problem	Tags	Notes	Solution
Machined Surfaces	1D Array Manipulation	count the number of 'X's in each row + keep track of their max	Link
Transform the Expression	Stacks	tricky way to use a stack , not direct	Link
The Most Potent Corner	Bitmasks	Try to assign a number to every corner such that it is easy to find neighbours of a corner using bit manipulation	Link
Free Spots	2D Array Manipulation	use 2D boolean array of size 500 × 500	Link
Raising Bacteria	Bit Manipulation	number of ones in binary form	Link