Programming concepts

CLEANUP CANDIDATE

Relevant discussion may be found on the talk page. Reason: No reason specified.

You can learn to program, but without a good foundation of theory behind you to help you make smart decisions with your code, you're going to be a shitty programmer. Go take a look at the Computer Science page for some info.

There's something to be said about optimising your algorithm before optimising your code.

Crucial programmer skills

There are some skills that are considered vital to being a valuable programmer, and that if you wish to be one, you should definitely get to grips with. These consist of:

• Version control systems:
  • Git (recommended, especially for open source stuff) and/or Mercurial
• Repositories
  • Gitorious
  • GitHub
  • BitBucket
• Document typesetting/preparation
  • LaTeX typesetting system
  • Markdown
• Console text editors
  • Vim and/or Emacs
• Command line skill
  • GNU/Linux/Unix shell
  • Windows cmd
• Compiler use
  • GNU Compiler Collection (gcc)

Guides to get you on your way

• Git tutorial and Git branching model
• LaTeX tutorial and LaTeX IDE
• Online vim tutorial
• GCC manpage

Programming Basics

Terminology

There is a hell of a lot of terminology in programming. Here we'll try to clear it up.

Data types

Numeric

Note: For a far more comprehensive listing of the numeric data sizes, see here. Also, sometimes KiB is used instead of KB. Consult this page for more info.

• bit (b) - The smallest computer unit.
• nybble - 4 bits.
• octet - 8 bits.
• byte (B) - Usually 8 bits, however, a byte isn't always 8 bits. It depends on the architecture of the CPU. Some bytes can be 16 bits, for example.
• word - 4 bytes.
• kilobyte (KB) - 1024 bytes.
• megabyte (MB) - 1024 KB
• gigabyte (GB) - 1024 MB
• terabyte (TB) - 1024 GB

Primitive data types

Note: The size of most of these data types are implementation specific. For example, in C, on a 32 bit machine, ints are 4 bytes. They're 8 bytes on a 64 bit linux machine. See here for more info.

• short/short int - Half the size of an int.
• int - A positive or negative integer.
• long/long int - Twice the size of an int.
• float - Floating point number. This is what computers use to represent decimal numbers.
• double - Double-precision floating point. This is a decimal number that is usually twice as big as a float.
• boolean - True or False
• char - A single character. On essentially all devices, these are one byte.
• string - A sequence of characters. In C, these are represented as a char array and must be ended with a null byte, '\0'.

Abstract data types

• Tree - An ordered structure that starts with a root node, and has child nodes, which have their own child nodes, etc.
• Array/List - A sequence of data types
• Tuple - An array, but unmutable (cannot be changed after creation).
• Map / dictionary - A mapping of key -> value pairs. These are usually represented by a hash table.
• Linked List - See below
• Set - An immutable, unordered list.

Keywords

• import/include
• void
• const vs final
• abstract
• OOP static vs C static
• class
• interface
• register
• inline

Programming Paradigms

Different languages are sometimes written in completely different ways. By becoming familiar with multiple languages that use different paradigms, you become a more effective programmer as the mindset used behind one paradigm can usually improve your way of thinking in another. Note that most languages can be used to program in more than one paradigms. C for example, normally categorized as an imperative language, can be used to write functional and even object oriented code (you can even mix all of them).

Imperative

• C
• Python

Functions and modularity

Think of a function as a box which takes data in, modifies it, and returns it.

Functional

Functional programming languages are so named because everything is defined in terms of functions, as opposed to a sequence of actions like in imperative programming, or objects, like in OOP.

• Lisp dialects (Common Lisp, Scheme, Clojure)
• Haskell

First class and higher order functions

A function which takes simple data (i.e. a string, or an int) and returns simple data is called a first class function. A function which takes a first class function as an argument is called a second class function, and a function which takes a second class function is called a third class function, and so on. A second class function or higher is called a higher order function.

Functional reactive

Functional reactive programming (FRP) is a subset of reactive programming built on the foundation of functional programming.

• Elm

Object Oriented

Defining Object Oriented Programming (OOP) appears to be difficult for people to ellaborate on and even more difficult for beginners to grasp. The best way I was explained was to envision real life objects such as a fork, a knife, a plate and a piece of chicken. Each object has methods and attributes. You would stab with a fork, cut with a knife, and these are it's basic methods. The chicken can be raw, or cooked, which would be its attributes. You can use the knife and fork together to stabalize and cut the chicken, but only if its cooked.

Most OOP languages have incredible documentation that is recommended to have handy for references while developing software with these languages.

OOP is not necessarily GUI programming.

• Java
• C#
• C++

Declarative

• SQL
• Prolog

Aspect Oriented

• ?

Concepts

Dynamic vs Static

Typing

A dynamically-typed language is one where you don't have to specify data types or function return types. Instead, the language will infer which type based on what is stored in the variable or returned by the function. A statically-typed language is where types must be declared.

Linking

Dynamic linking vs static linking

Competitive Programming

You are in the jungle. You have a pocket-knife. Someone asks you to kill a mountain lion.

Anyone but a programmer would be asking "WTF is a MOUNTAIN lion doing in a JUNGLE?!", but that's not what you have been trained to do as a programmer. You are here to solve problems, not to question them.

Years of training has taught you well. You use your knife to sharpen a stick. You cut vines to lash sharp stones on one end. Maybe you're from a top university, and you've learned to extract essential ingredients from plant and insect life around you to fashion a poison to tip your weapon with.

Convinced that you have an effective and efficient way to kill the lion, you set forth to accomplish your task. Maybe your stick is too short, or your poisons don't work. It's okay - you live to refine your method and try again another day.

Then someone figures out a way to fashion a low-grade explosive from harvesting chemicals in the jungle. Your method of fashioning a spear to kill the lion is now far from the best way to accomplish your task. Nevertheless, it's still a simple way, and will continue to be taught in schools. Every lion-killer will be taught how to build his tools from scratch.

That's "real-life" programming.

In competitive programming, you start out with the same resources (a pocket-knife), except you have 2 minutes to kill the lion.

As a beginner, you will stare at the lion and do nothing.

Soon, you learn that if you kill a squirrel, sometimes the judge thinks it's a lion and you're good to go.

A more experienced programmer just keeps stabbing the lion and hopes that the lion dies in time. Soon, you learn that there are certain spots on a lion that are damage immune. You learn to not even bother stabbing those spots. Sometimes, the lion doesn't expose those spots, so you get really good at killing squirrels.

And then, to be a great competitive programmer, you need to be able to do two things.

First, you must learn how to find the lion's critical point and kill it in one swift stroke.

Second, you must learn how to be so handy with your knife that you can fashion a sharp stick in 1 minute, and spend the next minute stabbing the lion to death.

But never ever will you be able to have enough time to fashion an explosive to take the lion out.

Material

Books

There are books that teach programming competition. They are a very good resource to learn computer Science

• http://www.comp.nus.edu.sg/~stevenha/myteaching/competitive_programming/cp1.pdf
  • https://sites.google.com/site/stevenhalim/
• (A less good one)
  • http://acm.cs.buap.mx/downloads/Programming_Challenges.pdf

Compete

There are many pages to compete in online programming competitions. They often offer tutorials and many other more:

• TopCoder
• Codeforces
• Codechef
• Google CodeJam
• Facebook HackerCup (I do not reccomend this one)
• ICPC (Might be available in your college)
• IOI If you are underage and autistic, look for the local version in your country of this one.

Training sites

If you want to train:

• UVA
• USACO
• Ahmed Aly's Webpage
• Project Euler
• Regex golf
• Interactive Regex for beginners