3
$\begingroup$

I am graduated from computer science. I need some advice in Combinatorics material related to master fields of computer science. I already know that discrete mathematics have a key role in some concepts which I need a little more elaboration. In which fields could I trace combinatorics concepts and theorems and techniques?

$\endgroup$
5
  • 3
    $\begingroup$ Combinatorial optimization. $\endgroup$
    – Phicar
    Commented Feb 15, 2017 at 19:54
  • 2
    $\begingroup$ If you never heard about complexity theory, read about it, it is quite pleasant. $\endgroup$
    – Vincent
    Commented Feb 15, 2017 at 20:24
  • 3
    $\begingroup$ Analysis of algorithms. For example, see "Analysis of Algorithms" by Sedgewick and Flajolet, or "Concrete Mathematics" by Graham, Knuth, and Patashnik. $\endgroup$
    – awkward
    Commented Feb 16, 2017 at 1:04
  • 1
    $\begingroup$ Honestly this question surprises me. Combinatorics is used pretty much everywhere in CS. You have a degree in computer science, what did you specialize in? I'm certain that no matter what you specialized in, combinatorics is used there. $\endgroup$ Commented Feb 16, 2017 at 3:58
  • 1
    $\begingroup$ @StellaBiderman I know It's surprising But combinatorics topics and methods aren't recognized since they are very vast; from inclusion–exclusion principle to well-known theorems like Ramsey theorem Hall theorem or even Regularity lemma) I was interested in some(including setsystems properties for example vc dimension or epsilon net theorem) and I find the other type of problems very hard to work with(like VC density and other topics in complexity) this post was for some clarifying purposes to finding the next step of combinatorics methods in cs. $\endgroup$
    – Niloo
    Commented Feb 17, 2017 at 14:25

1 Answer 1

2
$\begingroup$

Graph Theory is a part of Combinatorics that is extremely important in computer science. Roughly, it is the study of objects and connections between them.

Algorithms and Data Structures uses combinatorial techniques for analysis and design extensively. Several Data Structures use graph theoretic ideas to efficiently store and retrieve data. Randomized Algorithms and Approximation Algorithms require combinatorial methods for analysis. They are often faster or more "useful" than deterministic ones.

Complexity Theory, the study of the complexity of resources used by computational procedures, use combinatorial problems and ideas as examples of several sorts of complexity classes. Discrete Optimization, in particular, is a class of problems which are of relevance to both theoreticians and practical purpooses. Some of them represent problems which are too hard for detereministic procedures and give way to randomized and approximate algorithms.

Other interesting Computer Science fields where combinatorics is important include Coding Theory(Error Correcting Codes over Communication Channels), Computational Geometry, etc.


Also see: Why is it important to study combinatorics?

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .