Project Assignments

1: Percolation

• Model a percolation system by using UNION FIND data structure.
• Perform a series of Monte Carlo simulation.
• Please check instruction and checklist for more details.

Implementation and Optimization:

• version 1: Virtual top/ bottom blocks are created to avoid redundant search in top/bottom row.
  • Problem: Virtual bottom, once it was percolated, would cause "back wash" bug as below:

• version 2: Use two separate UNION FIND objects - one same as version 1 to determine percolation, and another without virtual bottom to determine if a block is filled.
• version 3: Virtual blocks are no longer used. Only one UNION FIND object is used to record the root of each block.
  • For each block, check itself and any of its neighbors are connected to top/bottom
  • Two additional boolean arrays are used to record its top/ bottom connection status.
  • If there's a block have TRUE status in both array, the whole system is percolated.

2: Deque and Randomized Queues

• Create a double-ended queue or deque that supports adding and removing items from either the front or back of the data structure.
• Create a randomized queue that item removed is chosen uniformly at random.
• Create a Permutation client which takes a command-line integer k and prints out exactly k of them.
  • Result is uniformly at random, and prints each item from the sequence at most once. Example output is shown as following:

• Please check instruction and checklist for more details.

Implementation and Optimization:

• version 1: a doubly linked list is used to implement Deque, and array is used for Randomized Queue. Array size will be doubled when full.
• version 2:
  • use a sentinel node that connects both head and tail of Deque to simplify code.
  • Array size will be halved if array is less than quarterly-full.
  • Minimum size of array is set to 8 to avoid unnecessary size-shirking.
  • For Permutaion.java, in order to use only one Deque or RandomizedQueue object of maximum size at most k, input string is shuffled first, then put only first k items into Deque.

3: Pattern Recognition - Collinear Points

• Write BruteCollinearPoints that examines 4 points at a time and checks whether they all lie on the same line segment. O(N^4)

• Write FastCollinearPoints which does the same as above and return all such line segments. O(NLogN * N)
  • To check whether the 4 points p, q, r, and s are collinear, just check whether three slopes p-q, p-r, and p-s are all equal.

• Please check instruction and checklist for more details.

Implementation and Optimization:

• Version 1: FastCollinearPoints:
  • sort points based on x-y, go through each point p
  • For each other point q, determine the slope it makes with p, and sort again based on its slope with p.
  • Since Merge Sort is stable, points will grouped by slopes and in each slop still sorted by x-y.
  • Sweeping two pointers through, check if any 3 (or more) adjacent points have equal slopes with p.
• Version 2: Fix bug
  • To include only maximal segment, segment need to fulfill p.compareTo(pFirst) < 0.
  • i.e. p itself need to be the smallest point in the same slope group.

4: 8-puzzle

• Write a Board to represent status of game board status.
• Write a Solver to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.

• Please check instruction and checklist for more details.

Implementation and Optimization:

• a Minimum Priority Queue is the data structure, and its priority is based on board's Manhattan distance.

• Version 1:
  • To detect unsolvable board and avoid TLE (never reaches goal board and exits while-loop), a SearchNode of twin board is also inserted into MinPQ. If a target board is reached by a Twin node, original board is not solvable.
  • SearchNode uses variable prevNode to avoid unnecessary search (i.e. going back and forth between 2 neighboring boards).
• Version 2:
  • Use two individual MinPQ for original board and twin board. So instead searching alternatively between type of Nodes, now the best-first searching is simultaneous. The searching ends whichever reached the goal board.

5: Kd Trees

• Write a data type to represent a set of points in the unit square. It supports range search and nearest-neighbor search.

• Please check instruction and checklist for more details.

Implementation and Optimization:

• Brute-force Implementation: Red-black Binary Search Tree is used. Either "range search" or "nearest neighbor", all the points in the red-black BST are checked.
• 2D-Tree Implementation:
• When build the 2D-Tree:
  1. in root level, divided node's rectangle in x-coordinate: point with smaller x goes to left sub-tree, otherwise go to right.
  2. in next level, divided node's rectangle in y-coordinate: point with smaller y goes to left sub-tree, otherwise go to right.
  3. repeating this pattern for all the sub-levels.

• Unlike brute-force, pruning are used in this implementation:
  • Range Search: a subtree is searched only if it might contain a point contained in the query rectangle.
    • No need to explore node whose rectangle has no intersection with query rectangle.
  • Nearest Point: search a node only if it might contain a point that is closer than the best one found so far.
    • Search subtree that is on the same side of the splitting line as the query point first.