This is my mindmap of what an introduction to graph theory constitutes of. Will explore some of these topics in near future.
- Vertex, Path, Connectivity, Trees, Forests, Cycles
- Matching & Coloring
- Chromatic Number
- 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…
- Euler Tour & Hamilton Cycles
- Hall’s, Euler’s Formula, Brook’s, matroid theory
- Well-known problems
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)
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.
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.