Research Approach

Approach

  1. Start one project or take one unsolved problem
  2. Define breadth & depth to solve this problem
  3. Divide the problem; Write on the challenges, motivation, survey, state of the art;
  4. Experiment on intuitions; write on experiments
  5. Combine all the work into a thesis. There still could be open yet-to-be solved problems.

Create your own projects (simple/small is fine) . Examples:

  • Js for data visualization over R.
  • Identify facts from internet
  • Summarize from books

Good to have it hosted / uploaded for visibility

Advertisements

Graph Theory – My Mindmap

This is my mindmap of what an introduction to graph theory constitutes of. Will explore some of these topics in near future.

Graph Theory

  • Concepts
    • Vertex, Path, Connectivity, Trees, Forests, Cycles
    • Matching & Coloring
    • Chromatic Number
  • Types
    • Based on connectivity: Isomorphic, Null, Bipartite Graphs, Planar (Dual, Infinite) Graphs, k-partite & k-colorable, Directed (Digraph)
    • Based on Walks: Eulerian, Hamiltonian (walks cover all edges and end at initial vertex)
    • Based on shapes: Stars, Platonic, etc…
  • Walks
    • Euler Tour & Hamilton Cycles
  • Theorems
    • Hall’s, Euler’s Formula, Brook’s, matroid theory
  • Well-known problems
    • four-color, marriage

Asymptotic Notations – Beyond the Oh Notation!

Big O is not the only notation used to describe algorithm complexity. There are theta and omega as well. In each (O, theta, omega), there are big and little notations.

As I read from online sources:

f(x) = O(g(x)) (big-oh) means that the growth rate of f(x) is asymptotically less than or equal to to the growth rate of g(x).

f(x) = Ω(g(x)) (big-omega) means that the growth rate of f(x) is asymptotically greater than or equal to the growth rate of g(x)

f(x) = o(g(x)) (small-oh) means that the growth rate of f(x) is asymptotically less than the growth rate of g(x).

f(x) = ω(g(x)) (small-omega) means that the growth rate of f(x) is asymptotically greater than the growth rate of g(x)

f(x) = Θ(g(x)) (theta) means that the growth rate of f(x) is asymptotically equal to the growth rate of g(x)

P, NP, NP Complete and NP Hard

What are P, NP, NP Hard and NP Complete problems?

P = Problems solvable in polynomial time. At least they have polynomial upper and lower bounds (worst and best cases). Polynomial time: O(n2), O(n3), O(1), O(n lg n), O(n^k)
NP (Non-Deterministic Polynomial time) = Verifyable in polynomial time. For example, finding a path may be difficult. However, given a path, verifying if it has at most k nodes is easy.
NP Complete = Can be reduced to another problem x (x is NP Hard) in polynomial time such that if x is solved, this problem can be solved.
NP Hard = There are million dollar awards on such x problems that when solved will help computer science solve several hard problems.

Turing’s “Halting Problem” is not solvable by any computer, no matter how much time is given! Another example: Given any boolean expression (3 sat example), can there exists valid values such that the expression evaluates to true? Apparantly, these can be solved by brute force or guessing the values and not through any polytime algorithm.

Research Methods

Key takeaways from my study of research methods:

What are the key takeaways from my study on research methods?

  • Focus on idea. Write as soon as you have an idea.
  • Decide on a thesis. Thesis is an argument (may be right/wrong. Its ok if someone may not agree with this thesis.)
  • Visual structure should be clear.
  • Use Examples.

What can act as a seed for a new research paper?

  • New ideas,
  • New facts or data,
  • intelligent reviews of old facts or data,
  • Opening up a field or area that is not well explored.