Most difficult subject/theory in Computer Science?

Question

Which is the most difficult CS subject/theory that you studied but important to the field? And the reason please?

I think this largely depends on the person learning the subject, and the person teaching it — Mahmoud Hossam, Feb 08 '11 at 08:19

score 37 · Answer 1 · answered Jan 31 '11 at 16:43

37

“There are 2 hard problems in computer science: caching, naming, and off-by-1 errors”

answered Jan 31 '11 at 16:43

Brian Carlton

1,079

4

I'd add threading... – Carra Feb 03 '11 at 13:44

score 35 · Answer 2 · answered Jan 31 '11 at 05:19

35

Honestly, compiler construction!

answered Jan 31 '11 at 05:19

Pemdas

5,385

13

+1 Compilers was the most difficult and the most rewarding. – snakehiss Jan 31 '11 at 05:40
3

It was up there with the most over all work, and good prep for grunt coding, but I don't think it was all that difficult. Maybe harder without the using YACC or whatever tools we used, I dunno. – Peter Turner Jan 31 '11 at 15:09
When I took it, we were required to understand the use of DFAs and the theory of LALR(1) parsing (including how to generate a parser state table from a small grammar), which is theory about as hard as it comes (except possibly the class where we covered the theory of computation and Turing machines). The class assignments were about as much coding as I ever had in a class. The combination was highly educational but not easy. – David Thornley Jan 31 '11 at 18:12
4

Compilers are really only difficult because most of the theory dates to times of insanely severe hardware constraints and a lot of the formal instruction hasn't advanced too far beyond that. Take a look at Let's Build A Compiler to see how easy compiler-writing can be if you approach it from a different angle. – Mason Wheeler Feb 01 '11 at 17:04
@Mason Wheeler: As a compiler writer I think that link is quite amusing. Please feel free to try. Come back in a year a let us know how much you actually managed to accomplish in building a real language. Ask the guys that have been working on D for a couple of years what they think. – Martin York Feb 01 '11 at 19:18
@Martin: Well, considering that D is supposed to be a more evolved version of a language with formally undecidable grammar, I'm not surprised that writing a compiler for it would be difficult. The first step to writing a compiler easily is defining a sane language. :P – Mason Wheeler Feb 01 '11 at 19:34
1

@Martin York, as a compiler writer I think that complexity of implementing compilers is overestimated severely. In general, a compiler is much simpler than an interpreter. I suspect it's a Dragon Book and its kind are to blame, they're proposing the most complicated ways of doing simple things and paying too much attention to the least important step, namely parsing. – SK-logic Feb 01 '11 at 20:13
I agree that parsing is the easiest part to implement. But it is also the hardest part to design correctly for a (non trivial) language (unlike DSL which are generally all trivial by definition). Any mistake hear cascades through the language making it more and more complex to build later stages. – Martin York Feb 01 '11 at 20:52
1

@Martin York, there are techniques of keeping an AST as simple and maintainable as possible, no matter how complicated the source language is. Also there is a number of very simple but powerful techniques for keeping each stage of compilation trivial and isolated. – SK-logic Feb 01 '11 at 21:23
Gotta agree with the Dragon Book criticism. It particularly bugs me the way Dragon Book does parsing and semantic analysis in three phases when they can be done much more simply in two. – Mason Wheeler Feb 01 '11 at 21:47
1

@Martin York, the "Let's Build a compiler" is very low level and simple, but still manages to do Real Work (TM), so I think your mocking is unreasonable. – Feb 03 '11 at 12:40

Oscar Mederos · Answer 3 · 2011-01-31T05:52:53.297

22

Design & Analysis of Algorithms

I think that question depends on the teacher you had, and how that subject was organized in your career.

Analyzing algorithms can be as hard as someone wants. Take in count that there are unsolved problems, and not only that: problems that can't be solved.

The thing is that you can have a problem, and if you know it can't be solved, that's perfect. But what if you don't? You can spend a lot of time trying to demonstrate it's NP-Complete, or trying to find a polynomial time solution to solve it.

Demonstrating NP-Completness is not easy. Yes, lots of problems are known, but the thing is to find the reductions to demonstrate that it's NP-Complete. And what if you spend lots of hours/days/months trying to demonstrate it, and it can be solved in polynomial time? :)

There are also other subjects, like Compilers, Group theory and Primitive Recursive Functions that can be as hard as the subject plan or the teacher wants ;)

edited Jan 31 '11 at 05:52

answered Jan 31 '11 at 05:40

Oscar Mederos

1,006

1

s/Analisis/Analysis ... otherwise exactly what I think ... primitive recursive functions, uargh!! – Felix Dombek Jan 31 '11 at 05:52
Agreed, I muddled through my bachelors degree never being confident that I ever successfully 'proved' anything (although my Algorithms class was way too simple, due to the professor) – Peter Turner Jan 31 '11 at 14:26
I will show you in these days, how hard algorithms can be :) – Oscar Mederos Feb 01 '11 at 06:07

score 18 · Answer 4 · edited Feb 01 '11 at 03:26

18

Pattern Recognition i.e. Artificial Intelligence. This refers to smart computing along with other pattern recognition tools like, Optical Character Recognition, Voice to text, facial identification, etc.

Many of the "cool" things you can do or wish you could do with computers rely on these algorithms, and we have been attempting to perfect them for decades without a whole lot of success.

edited Feb 01 '11 at 03:26

Chris

5,653

answered Jan 31 '11 at 18:00

Malfist

3,671

It's hard because it's not something that's deterministic. Developing a good AI pattern recognition requires experimentation for every application you want to use it for, to ensure you pick the right algorithm, the right features, etc... – Ken Bloom Feb 01 '11 at 03:06
1

I am just beginning to climb this particular mountain (pattern recognition). It's hard. LOTS of math. Great, huge, intimidating piles of math, staring back at me, daring me to enter. – David Poole Feb 01 '11 at 23:31
well ... pattern recog can also be seen as applied statistics, it's not just a problem within the range of CS – aggietech Mar 25 '11 at 15:18

Maglob · Answer 5 · 2011-01-31T09:27:01.817

12

My pick is computability theory

(Hmm... maybe it's not that important, but it sure was difficult)

edited Jan 31 '11 at 09:27

answered Jan 31 '11 at 08:37

Maglob

3,839

2

I agree, and I would personally generalize it as http://en.wikipedia.org/wiki/Theory_of_computation. – Matt H Jan 31 '11 at 17:16
I'll agree that the Theory of computation was hard, but it was also one of my favorite subjects. Granted, I was double-majoring in Mathematics... – Poindexter Jan 31 '11 at 17:41
+1 I double-majored too. I could handle an intro to this stuff, but the graduate version ... glad that I dropped it! – Job Feb 01 '11 at 03:01
it was hard, not we know so much about it that it doesn't matter much. – Display Name Feb 06 '11 at 09:42

score 10 · Answer 6 · answered Jan 31 '11 at 05:53

10

There are only two hard problems in Computer Science: cache invalidation and naming things. - Phil Karlton

answered Jan 31 '11 at 05:53

Gareth

5,122

score 7 · Answer 7 · answered Jan 31 '11 at 06:06

7

category theory (discrete mathematics), but worth it

answered Jan 31 '11 at 06:06

Steven A. Lowe

33,818

What specific benefits did you get from learning category theory? – zvrba Feb 01 '11 at 10:39
@zvrba: a deeper understanding of abstraction techniques and problem mapping – Steven A. Lowe Feb 01 '11 at 16:03
Where did you learn it from? – zvrba Feb 01 '11 at 16:15
@zvrba: I don't see the book on my bookshelf, it's probably still in storage (remodeling) but i think it was this book http://www.amazon.com/Category-Computer-Scientists-Foundations-Computing/dp/0262660717/ – Steven A. Lowe Feb 01 '11 at 18:12

score 6 · Answer 8 · answered Mar 25 '11 at 12:56

6

Cryptography

If you do it just slightly wrong, it could cost a company millions.

answered Mar 25 '11 at 12:56

davidhaskins

2,168

Although increasingly popular, Crypto isn't unique to software. – JBRWilkinson Mar 25 '11 at 18:01
Crypto isn't that hard. The problem is that security can't be tested easily, so you only notice your mistakes when somebody hacks you. But lack of testability applies to most forms of IT security, not just crypto. – CodesInChaos Feb 24 '13 at 09:07

score 4 · Answer 9 · answered Jan 31 '11 at 14:30

4

Operating Systems, especially the part that has anything to do with threading.

And the reason isn't because it was that hard to make 5 philosophers eat pizza with a fork. The reason is because writing multithreaded code is in and of itself difficult and not necessarily easy for the human (at least male - according to my wife) mind to compute.

answered Jan 31 '11 at 14:30

Peter Turner

6,897
1
34
58

9

Let your wife write the multithreaded code then :) – Jan 31 '11 at 23:05
3

Remember, when it comes to shared-memory multithreading, the computer is a sneaky swine that is out to get you. Doubly so when dealing with a multicore processor; one core can be distracting you in front of your eyes where you're watching, and the other can then go behind you and stab you in the back. – Donal Fellows Feb 08 '11 at 09:38

Yuva · Answer 10 · 2011-01-31T06:45:12.923

3

I too vote for Compiler Design. Especially where the DFA and NFA part comes in. I am also not so clear about NP problems and stuff.

edited Jan 31 '11 at 06:45

answered Jan 31 '11 at 05:41

Yuva

319

Yeah, I'd have had a harder time with Compilers if I hadn't taken Theory of Computation first. – Peter Turner Jan 31 '11 at 15:07
DFAs and NFAs are chicken feed. Wait until you have to do LALR(1) parsing. – David Thornley Jan 31 '11 at 18:08

score 3 · Answer 11 · edited Jun 16 '20 at 10:01

3

Queuing Theory

Well technically this is a branch of mathematics, but is highly relevant in CS.

Nearly everything in CS is based on queues (visible (obvious) and invisible (not so obvious or implied)).

In the early days of CS the queues were obvious.
A queue of programs (each program a deck of cards).

Nowadays the queues are not so obvious. The internet for example: a packet switched network, but the packets form queues and routing the packets is a form of queue minimization.

edited Jun 16 '20 at 10:01

Community

1

answered Jan 31 '11 at 09:50

Martin York

11,190
2
43
70

Hey! (? Are you a (Lisp programmer) – Mark C Feb 01 '11 at 17:01
Not (As much as (One could (see), But (It has (been known)). To Happen)). – Martin York Feb 01 '11 at 18:40

score 3 · Answer 12 · answered Feb 01 '11 at 16:59

3

Numerical analysis

It's not too hard on the toy problems you're given in the course, but once you start considering real problems it turns into serious drudgery.

answered Feb 01 '11 at 16:59

Peter Taylor

4,032
1
25
29

score 2 · Answer 13 · answered Jan 31 '11 at 18:07

2

Interpreting client requirements when the client doesn't really know what they want. This is not taught in college, and is one of the the most essential skills to have.

answered Jan 31 '11 at 18:07

Steven Striga

438

1

I'm not sure I agree with this one as being a Computer Science concept. I also don't see how it can be solved using the scientific method. – jmort253 Feb 01 '11 at 06:09
@jmort253 - This is true, but computer science tries (unsuccessfully in my opinion) to investigate this field with formal methods of design and validation. – mouviciel Feb 02 '11 at 08:46
I agree is not a "computer science" concept - but when I started my career I was unaware/oblivious to the fact that clients don't know what they want. I thought ALL software projects came with some kind of a formal requirements doc. Maybe a lecture topic for a software engineering course (maybe my college didn't cover it)? – Steven Striga Feb 03 '11 at 13:52

score 1 · Answer 14 · answered Jan 31 '11 at 05:27

1

Personally, mine was Formal Logic. It was tough to start with, but once you get the rules down and manage to play with it enough, your brain goes Logic++;, which in development is a very good thing.

As a side-note, I am answering the question directly - this was definitely not the hardest subject when I did my degree, but it was probably the hardest "real-life applicable" subject.

answered Jan 31 '11 at 05:27

Kyle Rosendo

416

Formal Logic is something that I had a love/hate relationship with. I liked thinking through the concepts, but I could never understand how it was helping me until later when I encountered real-world problems that required logical thinking. – jmort253 Feb 01 '11 at 06:11
@jmort253 - It was the same for me really. I even struggled to the point of thinking I'd fail it, studied so long and hard until it finally clicked in my head. After that, the benefits have been amazing. – Kyle Rosendo Feb 03 '11 at 12:10

score 1 · Answer 15 · answered Jan 31 '11 at 14:56

1

Compiler Constructions. Hard but must to understand the concepts behind

answered Jan 31 '11 at 14:56

Nipuna

1,306

5

You should give an up-vote for the same answer which was provided before you, rather than giving the same answer again. – Abimaran Kugathasan Feb 01 '11 at 16:39

score 1 · Answer 16 · answered Feb 03 '11 at 11:53

Kernel Design anyone ? Well I don't really know how it's done and what is the targeted features for an OS, but for me thinking about designing a kernel must be a daunting task.

I also think about computer security; I don't really know what makes a system unsafe except of course, obvious buffer overflows, XSS and SQL injections.

I'm not sure, but there seems that some algorithms are also unsafe; look at the MetaSploit project, it lists all type and kinds of security breaches: you can see there are a lot of ways a program can be flawed.

score 1 · Answer 17 · answered Feb 08 '11 at 09:46

There are many awkward topics in the field, but my picks for sheer persistent difficulty are those involving Global System Properties. Examples of this general topic include:

Safe and deadlock-free multi-threading
Security

These are hard because you're after something that only exists when everything is correct; you need a global system property and yet virtually all the tools available (and all the ones that scale to real problems in my experience) only really do local reasoning. It's the process of going from reasoning about the pieces of the program to the whole shebang that's hard, particularly because it's entirely possible to have pieces that are all correct in themselves but where there still are subtle bugs because the components are incorrectly arranged; the bugs can be undesirable emergent characteristics…

score 0 · Answer 18 · answered Jan 31 '11 at 05:32

0

Management Information Services During my college period i used to have one management subject each semester which totally made me mad.
Tough! well subjects like Compiler Design, OS Design etc are tough but they are really Interesting and challenging. I really messed in subjects like Management Information System / Services etc as they are full of boredom and you have to go through lots of theory.

answered Jan 31 '11 at 05:32

Ranger

1,003

2

Full of boredom because they're talking about the conceptual intricacies of each system, whilst half the people never wrote any system themselves (but they surely did use a variety of). Also, the seminals use so many loaded words yet fail to provide a real life example in plain English. Like decision support systems... couldn't you just drop a few screenshots of Google Analytics reports, FML, just to get the students on the same page before you run off having an intellectual orgasm in front of the audience. – Filip Dupanović Jan 31 '11 at 14:14

score 0 · Answer 19 · answered Jan 31 '11 at 05:54

0

If you are working in C/C++ pointers are the most important concept to know. But somehow I never understood it fully in college.

answered Jan 31 '11 at 05:54

Manoj R

4,076

12

really? I mean, each person is different, but I think there are lots (I mean, lots) of topics harder than just pointers. For example, Computer's Architecture, Assambler that in some way are related to pointers ;) – Oscar Mederos Jan 31 '11 at 06:03
True, but you'll find understanding memory referencing through assemblers way easier, because you actually work with raw pointers, whilst in C/C++ your working with references to pointers, which just confuses the hell out of people because the abstraction is never outspokenly talked about. – Filip Dupanović Jan 31 '11 at 14:17
2

Ah assambler, the best programmer's tea – Matt Ellen Feb 03 '11 at 12:52
The guy asked the topics which are difficult but important, hence pointers. – Manoj R Feb 03 '11 at 14:18
@Matt: You just made my day :D @Manoj R: Pointers are trivial if you just think of them as array access. Or is array access difficult? – back2dos Feb 08 '11 at 10:06
Pointers... I cast my mind waaaaaay back to when I was first introduced the the concept of indirection and linked lists and it took me a while to really understand what was happening. Ok, now I understand the concepts I can't see what the fuss was about... but that doesn't mean they're still not confusing to today's newbies. They're pretty important too :) – gbjbaanb Jul 01 '11 at 09:30

score 0 · Answer 20 · answered Feb 01 '11 at 06:46

Design and Analysis of Algorithms. It isn't so much that it's hard to understand and analyze known algorithms, it's that designing and analyzing new algorithms for hard problems is difficult, and requires a broad understanding of many areas and practice in applying many different techniques.

score 0 · Answer 21 · answered Feb 01 '11 at 14:53

0

Constraint Programming. which deals with combinatorial problems, NP-complete problems.

answered Feb 01 '11 at 14:53

Sorantis

2,730

score 0 · Answer 22 · answered Feb 01 '11 at 19:04

0

Optimization of Algorithm is challenging Topic.

answered Feb 01 '11 at 19:04

Rachel

765
5
18

score 0 · Answer 23 · answered Feb 01 '11 at 21:13

Which is the most difficult CS subject/theory that you studied but important to the field?

Discrete math.

It was difficult because the theories are very loosely related to each other but they're used in CS. Too much memorization I guess...

Proof by Induction, Big O, recursion, divide and conqure, Graph Theory, blah blah.. argh!

Compiler for me was easy, because we had to take Theory of Automata. ^^

score 0 · Answer 24 · answered Feb 03 '11 at 12:50

0

Z notation/formal methods used to hurt my brain at college. Mainly because I hated it. Hard is a lot easier when you enjoy what you're doing and much harder when you don't.

answered Feb 03 '11 at 12:50

Ian

5,452

score 0 · Answer 25 · answered Feb 08 '11 at 09:16

I like your answers (and I didn't forget upvoting them), like compiler, kernel, etc., but most of programmers never met these problems. There is a bit easier, but more common issue: concurrency - threads, locking. It's very easy to write a program which produces magical errors, if we make even a small bug in the concurrency architecture.

So, I say, it's not the hardest issue in computing, but because it's commonly used, it is a dangerous one.

score 0 · Answer 26 · answered Mar 25 '11 at 13:59

Object Oriented Programming

It's probably because I cut my teeth on FORTRAN and APL, but the shift from strictly procedural languages to objects has been something I've struggled with for years. It doesn't help that so-called 'experts' write conflicting articles and tutorials on what it means to be object oriented and the best/proper ways of constructing object oriented programs.

Most difficult subject/theory in Computer Science?

26 Answers26

Queuing Theory

Numerical analysis