Monday, February 15, 2010

Thing to Study for Theoretical Computer Science

I am making a list of the subjects that I need to study. Most of these subjects are related to mathematics and theoretical computer science.

1. Approximation Algorithms:
Specially usage of LP-Duality and local search in different problems.
Vijay Vazirani's book(a preliminary version is available on net) is a good reference for this.

2. Randomized Algorithms:
Use of Probabilistic Methods, Lovasz local lemma and Markov Model.
Raghavan-Motwani is a good source for this.

3. Algebraic Topology:
Munkres is a good source for General Topology. Allen Hatcher is a good reference for point-set and Algebraic topology.

4. Algebra/Group Theory/Linear Algebra:
Herstein is a good source.

5. Convex Optimization/Linear Programming:

6. Information theory:

7. Game Theory:

8. Theory of Computation and Complexity.

9. Analysis:
For measure theory etc. -- more like a maths background.

10. Quantum Computation:
A new field. May need help of a Physicist friend.

11. Probability and Statistics:
Have a brush with UG textbook. :)

12. Combinatorics and Combinatorial Algorithms:

-- Will add more later.

No comments: