What computer science concepts should I know?

Question

What computer science concepts did you think made you the best programmer?

My degree was in the field of mechanical engineering, therefore, having become a programmer, I do not understand the basics a bit. There are a few standard CS concepts that I recently learned that gave me a much deeper understanding of what I am doing, in particular:

Language Features

• Pointers and recursion (thanks Joel!)

Data structures

• Related Lists
• Hashtables

Algorithms

• Bubble Sort

Obviously, the list is a bit short at the moment, so I was hoping for suggestions regarding:

• What concepts should I understand
• Any good resources for understanding them correctly (since Wikipedia can be a little tight and academic sometimes).

Answer 1

Take a look at this Steve Yegge blog post (formerly Amazon, now at Google):

• Five key phone screen issues

It describes in detail the five most important concepts that developers should know:

• Basic programming (including recursion, file input / output, formatted output, loops, etc.)
• Object-oriented design (including design patterns, etc.). You should be able to create smart OO projects as well as understand the concepts.
• Scripting and regexes.
• Data structures - lists, sets, hash tables, trees, graphs, etc. - as well as the Big O designation and algorithmic complexity.
• Bits, bytes and binary numbers - how numbers are represented on a computer and how to manipulate them.

Answer 2

You definitely need to understand Big-O notation and estimates of Big-O algorithms - what it is, how it is used, why it is important, how you compare two algorithms based on their Big-O estimates, how you build Big-O estimates for simple algorithms .

Answer 3

I'm a little funny that you are looking for subjects in computer science, but Wikipedia is too academic: D

Anyway, here it goes, in random order:

• Relational Model: An Introduction to Database Systems
• Object Orientation: Object Thinking
• Complexity and computational theory (e.g., Turing machines and automata): an introduction to computational theory
• Small compiler design: Dragon Book , although it may be too deep for your needs.
• Operating System Concepts: Modern Operating Systems
• People Skills: Making Friends and Influencing People
• Teamwork: Peopleware
• User Interface Design: Prisoners Receive Asylum

Answer 4

Some concepts that have helped my development (intelligence and code):

• Lexing, analysis, string matching, regular expression
• Memoization
  • encapsulation / overview / closure
  • caching
• Recursion
• iterators / generators
• Functional programming - an amazing article made me "why"

These are entire areas of discrete mathematics, but CS requires a serious introduction:

• Matrix / Linear Algebra
• Graph theory

Although Mark Jason-Domin's lectures and articles often go to Perl hackers, I think that any programmer will benefit from his clear presentation and real code, especially in the Higher Perl order .

Answer 5

I would say that an understanding of Object Orientated Programming is now mandatory, even if you do not need to use it day by day.

From this, I would also say that understanding the most common patterns can also help.

Answer 6

I see some good CS concepts, but they say little about math.

I suggest you study discrete mathematics . It has many useful problems, starting with logical proofs that help you write conditions in code. Graph theory and combinatorics also help in solving complex problems and optimizing algorithms.

While we are on the subject of mathematics, linear algebra, as a rule, is a prerequisite for advanced classes of computer graphics.

Answer 7

I find graphs and some applied algorithms, such as depth first, preliminary search for the first breath, shortest paths, etc. very helpful. Orientation of objects is also a really general concept.

Answer 8

The programmer’s competency matrix described this in detail, but I’ll highlight a couple:

• Data structures
  • Advanced data structures such as B-trees, binomial and Fibonacci heaps, AVL / Red Black trees, Splay trees, skip lists, attempts, etc.
• Algorithms
  • Tree, Graph, simple greedy and divide and conquer algorithms are able to understand the relevance of the levels of this matrix.
• System Programming
  • It understands the entire software stack, hardware (processor + memory + cache + interrupt + microcode), binary code, assembly, static and dynamic linking, compilation, interpretation, JIT compilation, garbage collection, heap, stack, memory addressing ...
• Source Control
  • Knowledge of distributed VCS systems. Tried Bzr / Mercury / Darks / Geet
• Build automation
  • Can set up a script for building the system, as well as documentation, installers, generate release notes and tag the code in the version control system
• Automated Testing
  • Understands and knows how to configure automatic functional, load / operational and user tests
• Decomposition Problem
  • Using appropriate data structures and algorithms and developing a general / object-oriented code that encapsulates aspects of the problem that can be changed.
• Decomposition systems
  • Able to visualize and design complex systems with multiple production lines and integration with external systems. He should also be able to design operations support systems, such as monitoring, reporting, failover, etc.

Answer 9

Rule 1: Software is a collection of knowledge . Software means something. If you are unclear in the sense, spend more time communicating with users to understand what they are doing.

Algorithms and data structures are two sides of the same coin. The algorithm depends on the data structure, the data structure depends on the algorithm.

Cancel the sorting of bubbles as quickly as possible. Jokes aside. All modern languages ​​(Java, Python, etc.) have collection classes that implement better sorting than bubble sorting. There are absolutely no circumstances in which you should ever use bubble sorting for anything. You should look for a collection class that includes a sorting method. Better, you should look for an algorithm that completely avoids sorting.

You must learn several languages.

• Programming language (Java, Python, etc.)

• Shell language.

• Database Language (SQL)

• Presentation Languages ​​(HTML and CSS)

• Other data presentation languages ​​(XML, JSON)

You should study several data structures.

• Sequences (lists, tuples, files)

• Hierarchical (e.g. XML and HTML documents, as well as the underlying file system)

• Relational (e.g. databases and file systems with hard and hidden links)

• Maps (or indexes or associative arrays), including hash maps and tree maps

• Many

Plus some algorithmic complexity analysis. Sometimes called "Big O". Why the bad bubble type is O (n ^ 2), where quicksort is O (n log n).

Answer 10

For me, I got a lot from my next year at university.

• Project management
• Interaction with a personal computer (helps us geeks to create more user-friendly screens).
• Database design (including working with databases, transaction logs, locking, etc.)
• Data store
• Graphics (OpenGL)
• Advanced Algorithms
• Data structures

Things I would like to do at the university

• Compiler design
• Design Patterns
• Theory of Automata

Answer 11

LOGIC . I am simply exaggerating the importance of logic in programming. You said you did mechanical engineering, so you need to know how much mathematics can make your life easier.

Propositional logic , First-order logic, Second-order logic : these are very powerful tools. Probably the most (and only) important things that I studied at the university. The logic is similar to the programmer’s heavy artillery - a lot of very complex problems (as well as less complex) become much easier if you include them in an organized, logical form. This is similar to what linear algebra is for mechanical engineers.

Answer 12

I think a good understanding of how the compiler works is good to know. Aho has a classic book on concepts used to create a compiler. The name is Compilers: Principles, Methods and Tools. His nickname is Dragon Book. To truly understand this book, you must understand formal languages. Hopcroft has a good book about this - An Introduction to Automata Theory, Languages, and Computing.

Answer 13

Some of the OS concepts

( memory, IO, Scheduling, process\Threads, multithreading ) 

[good book, Modern Operating Systems , 2nd Edition, Andrew S. Tanenbaum]]

Basic knowledge of computer networks

[good book by Tanenbaum

OOP concept

Final car

Programming language (first I learned C, then C ++)

Algorithms (time / space complexity, sorting, searching, trees, linked list, stack, queue)

[good book Introduction to Algorithms ]

Answer 14

Encapsulation

In computer science, encapsulation is the concealment of internal mechanisms and data structures of a software component behind a specific interface, so that users of the component (other parts of the software) need to know only what the component does and cannot depend on the details of how it does it

Answer 15

Good answers have already been mentioned here, but I wanted to add a subset of what is important, but not yet covered.

After 15 years of post-professional software development professionalism, I found that at school I regularly use some of the following concepts:

• General concepts of OO and modern features of a programming language (classes, data hiding, etc.).
• Algorithm Performance Indicators (Big O Notation). When developing an algorithm, performing Big O analysis to determine the cost of the algorithm and consider more effective alternatives in bottlenecks.
• Linked lists and other complex data structures.
• Quick sorting and various sorting concepts.
• Trees and quick manipulation of trees.

If your language / platform does not support garbage collection, memory allocation and cleanup are critical and will be added to the list.

Answer 16

I put forward discrete math. Computer science is an abstraction. Learning to think like a mathematician is very helpful.

I also wanted to add what S. Lott said about languages. Learning the types of languages ​​is also important. Not just a compiled script. But a functional (ML, Lisp, Haskell) logical (Prolog) object-oriented (C ++, Java, Smalltalk) imperative (C, Pascal, FORTRAN even).

The more software paradigms you know, the easier it is to assemble new languages ​​when a hot new language arrives!

Answer 17

Well, the worm is now open! :)
I started to do electrical engineering.

Relational database structure: Tracking data like Arnold in Kindergarden Cop.
It could be complete chaos. It needs to be controlled.
How to save your data in the smallest places with the least amount of duplication of information. How to keep your data light and easily accessible. How to control the growth and integrity of data.

User Interface Design (UI) . This is how the user should access the data that we are tracking.
Most user interfaces are developed by developers. Thus, most user interfaces, unfortunately, are parallel to the design of the database. Users do not need data design at all. They just want what they want. They want to get it easy. This usually requires a significant branch from data design and user interface. Learn to separate engineering from you from southern hospitality.

Object Oriented Programming: Many languages ​​come down to this format.

Parallel Processing - Multithreading:. Many processors work fast!
Parallel computers have been around for decades. They have long been working on our desktop computers. In the case of "cloud computing" massive parallel processing is not only mandatory, but also preferred. It is incredibly powerful! There are many opportunities for working with concurrent developers.

General Business Rules:. This will help you do a lot of your table based logic.
Many IFblock conditions can be found in business rule tables. To change the logic, just change the information in the table. Small / No recoding. Small / No recompilation.

Observing events ... Methods do the work:. Keep things in your code. This makes it easier for others to make future updates. It is also somewhat parallel to the Model / View / Controller (MVC) structure.

Pj

Answer 18

Strive for low adhesion, high cohesion .

(I stole this image from the site above)

Answer 19

Try to understand all levels of programming. From the lowest level (assembly) to the highest level.

Take recursion, for example, which is an easy function. Try to study the assembly and create a program that will use recursion in the assembly.

Answer 20

This is undoubtedly a good understanding of object-oriented programming, good guidelines such as SOLID principles , and adherence to established patterns and practices.

If you look at SOA or DDD, they all end up resorting to some form of OOP concept.

I would recommend you buy some good OOP books, and also choose a rich language, such as C # or Java, for starters.

OOP by Grady Butch

(PHP guys, please don’t vote against me, I’ll just give some examples for it, you can provide your own answers and suggestions here)

Answer 21

Algorithms

Learning how to use a programming language in a walkable way is something you can learn when you go, but it's almost impossible to invent all the widely used Algorithms yourself. In fact, at least you need to know what can and can’t be with some problems.

For example, it is simply not possible to write some bubble sorting software and expect it to be considered good, no matter how good the code is.

To summarize - take a look at Introduction to Algorithms

No need to master it, just know what is happening ...

Answer 22

As a recent graduate in computer science, I would recommend the following:

• As mentioned in various Big O notation posts

  OO Design

  Data structures and algorithms (I can’t remember the exact name of the book that I used, I will update it if I remember)

  Operating Systems http://www.amazon.com/Modern-Operating-Systems-2nd-GOAL/dp/0130313580

  NP Problems

Answer 23

The structure and interpretation of computer programs . If you understand this book, everything else can be easily built on this foundation. If you have problems with concepts in the book, you can be a software developer, but not a software scientist.

Answer 24

I am not going to tell you any specific concepts for study, but instead recommend that you do a lot of easy reading on a wide range of topics. Don’t worry about getting a deep understanding of each subject you are reading about - at the moment it’s important that you can recognize what problem you are looking at, so that you can do something when you are actually faced with it. In other words, this is normal if you do not know how to solve the problem of combinatorics, if you know enough to find “combinatorics”, when you need to see how many ways to organize a set of objects or select a subset.

Wikipedia is a pretty good resource for this kind of large-scale viewing, especially if you just combine to get started. Even better, especially if you think Wikipedia is too academic or inaccessible, is the C2 wiki . (This is interesting, the original wiki invented by Ward Cunningham).

Answer 25

It seems to me that it is important to understand the basic theory of multithreading, without it it can be difficult to even see that there can be a problem until you are debugged on a real server at 4 p.m. on Sunday morning.

Semaphores, critical sections and events.

Answer 26

No, don't sort the bubble, quicksort. These are average values ​​of the type of O-bubbles with large values ​​of O (n ^ 2), quicksort - O (n * log (n)).

Answer 27

I would say that this is the most important material

• Object oriented programming
• Operating system concepts
  • Process and thread
  • Scheduling algorithms
• Data structure
  • Type of data storage and collection, types (linked list, hash, array, etc.).
  • Sort Algorithms
  • Algorithm Complexity

Then go to the specific language. Hope this is helpful!

Answer 28

I would start with a quote:

"if the only tool you have is a hammer, you treat everything like a nail" (Abraham Maslow)

The most important principle, IMO, is the knowledge of many different programming paradigms, languages ​​and knowledge of the tools at your disposal. Any problem can be solved in almost any language you choose, be it a full-blown main language with its huge default library or a small specialized language such as AutoHotKey. The first task of the programmer is to determine what to use in accordance with the specification of the problem. Some concepts provide a better approach to the topic, whatever your main goal: complexity, obfuscation, performance, portability, maintenance, small code size ...

Otherwise, you end up as some programmers who are desperate to do something in the same language that they specialized, while the problem may be trivial to solve in different programming contexts.

This tip is consistent with the current trend towards multilingual projects (e.g. for web applications that can include multiple languages ​​in one application, such as C #, JS, CSS, XPath, SQL, XML, HMTL, RegExp ... and even various programming paradigms (for example, C # recently introduced some concepts from functional programming paradigms, lambda).

So, the main thing is continuous learning, forever :)

Answer 29

I think 3D graphics are what everyone should learn. Or at least how to use homogeneous vectors and matrix transformations correctly.

This can be useful not only for creating 3D applications, but also for mechanical fields , such as inverse kinematics on robots, moment calculation, and much more.

I did not fully understand linear algebra until I read 3D graphics, one of the best courses I have ever taken, although our teacher was bad.

Answer 30

Since machines with multiple cores (both CPU and GPU) are becoming the standard, I would say that includes Distributed Algorithms (from multiple threads to multiple machines). It is imperative to understand multi-threaded and distributed processing. Sorry, the link really doesn't give much help.