Eclipse Shortcuts

CS+L : Open key assist for all combinations

C+k, CS+k  ( Goto next/prev location)

C+L (Goto Line)

C+M (min/max windows)

CA+Up/Down (duplicate/copy)

skip all break points, enable all break points — CS+B

CS+I comment lines in xml, jsp

Generate Delegate

Java > Editor > Save Actions (format on save) + Organize Imports

*S: Shift

*C: Ctrl

*A: Alt

Algorithm Complexity

Big O Notation: For simplifying understading and measuring of algortihm complexity.

Big O notation means algorithm cannot grow faster than another function. Also, there is Big Omega which means algorithm grows at least as fast as another function and the Big Theta which means algorithm grows exactly as fast as another function

Interpolation Search: Like searching for name in phone book or word in dictionary. Uniform distribution and indexed by key you are using to searh. Instead of starting at the middle (like in binary search) you can decide the starting point based on the key and the knowledge of starting/ending point & the idea of distribution.

BFS Traversal

Use a Queue or PriorityQueue for traversal.

Can be used to find the shortest paths in graphs.

If negative edges are present keep calling update  V-1 (V is the number of vertices) to get the shortest path. If on Vth iteration the distances still reduce that means there are -ve cycles.

Implementation Note:

Queue can be implemented using an array. children for j are 2j+1 & 2j+2 (0 based index) and parent of j is floor(j/2) if j is odd or floor(j/2) -1 if j is even. This is better for dense graphs.

Binary Heap based implementation. This is better for sparse graph’s. insert/decrease key is log(V) and deleteMin is log(V)

Java Priority Queue has no provision for decreasing the key and is based on array implementation.

one set of methods (peek, poll) return nul if no element and (remove, element) throw NoSuchElement if no element is present when operation is performed.

Stack Based (Non Recursive) explore Graph

explore(G,v)

if(v == null)

 return;

push(v)

while(!stack.empty) {

v =stack.pop()

pre(v)

visited(v) = true

visit(v)

for all edges u,v belongs to G 

   if(u not visited)

      push(u) // in reverse order; example if you want to explore nodes in lexicographical order push from z -> a

}

what about post(v) // insert a postOrder hook element to call post() after all the children are visited.

Alternatively, no need to push an element if it is already in stack

Graphs

Undirected Graphs

vertices, edges

adjacency matrix O(V^2), adjacency list  O(V+E)

explore(G,v):

i/p G = (V,E), v belongs to V

o/p visited(u) set to true for all nodes reachable from v

visited(v) = true;

previsit(v)

for all edges(v,u) in E

     if not visited(u): explore (u)

postvisit(v)

explore visits all nodes reachable from v. To explore all G we need to restart explore where v is not yet visited.

dfs(G):

for all v belongs to V

   visited(v) = false

for all v belongs to V

  if not visited(v): explore (G,v)

 

dfs can be used to check connectivity and assign ccnum for each connected component.

previsit & postvisit orderings:

previsit(v):

pre[v] = clock

clock = clock+1

postvisit(v):

post[v]= clock

clock = clock+1

for any 2 nodes u,v in undirected graphs either pre[u], post[u] & pre[v], post[v] are disjoint or contained with in one another.

for undirected graphs you have tree edges or back edges.

Directed Graphs

parent, child & ancestors, descendants.

forward edge, backward edges, cross edges, (and also the original tree edges).  How to determine the edges from th pre, post numbers? Applyingthe below ordering doesn’t seem to work – what am i missing?

[u   [v    ]v  ]u   Tree/fw edges

[v   [u    ]u  ]v  backward edges

[v   ]v    [u   ]u  cross edge

DAG (Drected Acyclic Gaph):  A DG has a cycle if and only if dfs reveals a backward edge.

If a graph is a DAG we can liniearize (topological sort) the vertices. there can be multiple linearizations. DAG can be linearized in the decreasing order of post numbers. sink has lowest post number, source has highest post number.

Every DAG has atleast one source and atleast one sink. to linearize find the source, delete it & repeat on the remaining graph.

For DG Connectivity is defined as “there is a path between any 2 vertices” of the connected component. A DG is a DAG of it’s connected components.

Kosaraju’s algorithm for determining the connected components of a DG:

1) Invert the Grapgh G -> GR

2) Run CC analysis on node based on the post order from 1

 

 

 

Desireable Qualities of a Software Developer

  1. Ability to learn and use new technologies on the fly.
  2. Understand, Clarify and Implement requirements in short time and with little waste or overhead.
  3. Ability to read other developers code and reuse them when needed.
  4. Ability to refactor code developed by self and by  other developers with out breaking it.
  5. Ability to follow the desciplice of writing unit tests as code is developed.
  6. Ability to document and name classes, methods & variables meaningfully.
  7. Ability to use basic design patterns.
  8. Ability to understand and code Concurrency.
  9. Good grasp of Algorithmic Complexity and Data Structures.
  10. Ability to design UI.
  11. Ability to listen, understand & emulate what others are saying.

Software Strategy

Why lots of project managers insist on ‘reusing’ existing software while developers seldom agree.

Single Worst Strategic Mistake: Rewrite from scratch.

  • Bugs have been found after lots of realworld-usage and are hard and costly to find.
  • giving away market lead.
  • next developer cannot necesarily write better than previous one.
  • 99% of the performance is improved by 1% change.
  • Code is hard to understand – proper refactoring techniques can help

http://www.joelonsoftware.com/articles/fog0000000069.html