Overview

Metanautix now has Personal Quest online where individual users can download and do analytics on desktop. I have been working on a new systematic way to learn music theory and do musical analysis with mathematical matrix and vectors, and Quest is a critical tool in query on large dataset such as a pool of thousands of song scores. In this article, I will talk about my methodology in detail.

An overview for my system will be:
image

Read more »

BFS vs DFS

Overview

  • search algorithms for graphs and trees

  • used for unordered graph and tree

  • graph representation

    • adjacent list: space O(V+E)
    • adjacent matrix: space O(V^2)
  • BFS

    • start with root node
    • scan each node in the each level
    • while traversing each level, decide if target is found
  • DFS

    • start with root node
    • follow on branch as far as possible until target is found or hit a leaf node
    • if hit a leaf node, continue search at the nearest ancestor

Comparison

  • memory
    • BFS uses a large amount of memory because need to store pointers to a level(serious problem if the tree is very wide)
    • DFS uses less memory because no need to store all child pointers at a level
  • depend on the data you search for
    • look for people alive in family tree: DFS because targets are likely to be on the bottom of the tree
    • look for people who died: BFS

implementation

BFS: queue

  • recursive

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    BFS(Q)
    {
    if (|Q| > 0)
    v <- Dequeue(Q)
    Traverse(v)
    foreach w in children(v)
    Enqueue(Q, w)

    BFS(Q)
    }
  • iterative

1
2
3
4
5
6
7
8
9
10
11
procedure BFS(G,v)
initialize a queue Q
Q.push(v)
label v as visited
while Q is not empty
v <- Q.pop()
visit(v)
for all edges from v to w in adjacent(v)
if w is not visited
Q.push(w)
label w as visited

DFS: stack

  • recursive
1
2
3
4
5
procedure DFS(G,v)
label v as visited
for all edges from v to w in adjacent(v)
if w is not visited
DFS(G,w)
  • iterative
1
2
3
4
5
6
7
8
9
procedure DFS(G,v)
initialize stack S
S.push(v)
while S is not empty
v <- S.pop()
if v is not visited
label v as visited
for all edges from v to w in adjacent(v)
S.push(w)

Solution

  • BFS: complete algorithm, give optimal solution
  • DFS: suboptimal solution

Complexity

  • BFS: worst time O(V+E), worst space O(V)
  • DFS: worst time O(v+E), worst space O(V)

Electronic MIDI Control on SG

Here is a quick showcase of a project I have been playing around with recently. An Midi Control Pad installed on SG being synced with an arduino.

Read more »

Introduction for Noobs

During a software development, a team usually have different roles, each role is responsible at a certain stage of the development period. Summarizing them into a flowchart, it will show as follow:

Git vs SVN such as Perforce:

Reset Porblems

Read more »

List

List add remove get contains next Data Structure
ArrayList O(1) O(n) O(1) O(n) O(1) Array
LinkedList O(1) O(1) O(n) O(n) O(1) Linked List
CopyOnWriteArrayList O(n) O(n) O(1) O(n) O(1) Array

Set

Set add remove contains next size Data Structure
HashSet O(1) O(1) O(1) O(h/n) O(1) Hash Table
LinkedHashSet O(1) O(1) O(1) O(1) O(1) Hash Table + Linked List
EnumSet O(1) O(1) O(1) O(1) O(1) Bit Vector
TreeSet O(log n) O(log n) O(log n) O(log n) O(1) Red-black tree
CopyOnWriteArraySet O(n) O(n) O(n) O(1) O(1) Array
ConcurrentSkipListSet O(log n) O(log n) O(log n) O(1) O(n) Skip List

Queue

Queue offer peek poll remove size Data Structure
PriorityQueue O(log n) O(1) O(log n) O(n) O(1) Priority Heap
LinkedList O(1) O(1) O(1) O(1) O(1) Array
ArrayDequeue O(1) O(1) O(1) O(n) O(1) Linked List
ConcurrentLinkedQueue O(1) O(1) O(1) O(n) O(n) Linked List
ArrayBlockingQueue O(1) O(1) O(1) O(n) O(1) Array
PriorirityBlockingQueue O(log n) O(1) O(log n) O(n) O(1) Priority Heap
SynchronousQueue O(1) O(1) O(1) O(n) O(1) None!
DelayQueue O(log n) O(1) O(log n) O(n) O(1) Priority Heap
LinkedBlockingQueue O(1) O(1) O(1) O(n) O(1) Linked List

Deque

Deque offer/offerLast peek poll/pollLast remove/removeLast Size Data Structure
LinkedList O(1) O(1) O(1) O(1) O(1) Array
ArrayDequeue O(1) O(1) O(1) O(n) O(1) Linked List

Map

Map put get containsKey next Data Structure
HashMap O(1) ~ O(n) O(1) O(1) O(h / n) Hash Table
LinkedHashMap O(1) ~O(n) O(1) O(1) O(1) Hash Table + Linked List
IdentityHashMap O(1) ~O(n) O(1) O(1) O(h / n) Array
WeakHashMap O(1) ~O(n) O(1) O(1) O(h / n) Hash Table
EnumMap O(1) ~O(n) O(1) O(1) O(1) Array
TreeMap O(log n) O(log n) O(log n) O(log n) Red-black tree
ConcurrentHashMap O(1) ~O(n) O(1) O(1) O(h / n) Hash Tables
ConcurrentSkipListMap O(1) ~O(n) O(log n) O(log n) O(1) Skip List