Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

As a grad student, I find it more and more common for prestigious companies (like Google, Facebook, Microsoft,...) to put algorithm questions in their test and interviews. A few startups I applied to also asked about algorithms. I wonder if algorithms fluency is the most important thing for software developer in those companies?

If the answer being yes, what are the best method or resources for one to learn & practice about algorithms effectively? I can't seem to get interested in solving seemingly too complicated problems found in most textbook or websites. Though easily understand basic algorithms (like quicksort, bubblesort,...), I find it immensely difficult to remember and reuse them later.

Thanks.

P/S: If you ask me what I like, it's building good softwares to solve users' problems innovatively. I suppose that does not necessarily mean the software has to be very complicated.

share|improve this question
24  
Any idea how complicated it is for Google to allow you to search the entire web with a textbox and a button? –  JeffO Feb 8 '12 at 18:41
20  
@JeffO I don't even use the button anymore ;-) –  maple_shaft Feb 8 '12 at 18:47
1  
If Google makes it any easier, all the other search sites won't need any code at all. –  JeffO Feb 8 '12 at 20:54
    
I thought the question would be about how computers work, like how does a CPU works, how RAM works, how wifi works, etc. Those are quite interesting question still subject to quite a lot of research. I still find hardware more awesome than all the geeks programming in java or php. –  jokoon Feb 8 '12 at 21:22
2  
It's not all about algorithms, but indeed they are at the core of CS. But there's a lot more to programming than just algorithms and logic (maintaining code, for instance, wouldn't require only knowledge of algorithms). –  haylem Jun 6 '12 at 2:44

14 Answers 14

up vote 41 down vote accepted

Algorithms are clear

Here's the beautiful thing about algorithms: The problem space they deal with is well-defined, i.e. your requirements are not only actually known, but usually even formalized much like the metrics for the solution's quality.

So if I tell you to come up with an algorithm, there isn't much potential for communication problems, and measuring your performance is a trivial task. At the same time your performance is a fairly good indicator for your ability to think logically.

Algorithms are an efficient filter

The current problem of the industry (and the education) is the poor average quality of graduates. This has been illustrated with the FizzBuzz test, which is:

Write a program, that will go through the numbers from 1 to 100 and will print "fizz" if the number is divisible by 3, "buzz" if it is divisible by 5 and the number itself if it is divisible by neither.

Apparently, the majority of all Comp Sci graduates fail to solve this problem. Please note that this is an algorithmic question, although of course an embarrassingly simple one. Given this, getting someone who can solve the kind of problems given in Google Code Jam or Project Euler, you're already enjoying the crème-de-la-crème.

Algorithms are a tiny part of software development

The truth is, as soon as you work in the industry, you will not be using your algorithm skills more than 1% of the time.

Before you even start writing code, you must first gather and analyze requirements. Then you must synthesize your design based on them. Then you must implement the design. Then you must evaluate the implementation against the original requirements, then iterate the requirements, then iterate the design, then iterate the implementation and so on.

One of the requirements is sensible performance. If that requirement is not met, you must profile your implementation to track down the bottlenecks and then you can optimize it, which sometimes is a matter of straight forward micro-optimization (which is rather easy to do), but sometimes is a matter of using better algorithms (which is not always easily done afterwards). Therefore:

Algorithms are critical

The better your grasp of algorithms, the bigger is the chance that you get it right the first time. Otherwise, you're not only likely to run into a problem that can only be solved by implementing a better algorithm, but also you will be unable to actually solve it.
So while you almost never need this skill, it presents a single point of failure in your development methodology and if you don't have the skill, you can only hope that the necessity never arises, or that someone else jumps in to fix it for you.

What is really important is to get a feeling for computational complexity and how to keep it low, as I also explained in response to a similar question. Or to specialize in things where this simply isn't important, such as GUI development, but then again almost everybody hates it ... for a reason!

share|improve this answer
5  
+1 for a very comprehensive and intelligent answer. Also, it is sad how effective of a filter FizzBuzz is. There is absolutely no excuse for not being able to do it. –  Adam Crossland Feb 8 '12 at 20:22
3  
I thought that you should be printing fizzbuzz if the number was divisible by both and that many slipped on that because you need to order to modulo checks carefully. –  Matthieu M. Feb 9 '12 at 10:25
1  
1% may be a bit too high –  hemp Feb 15 '12 at 8:08
1  
@MatthieuM.: printing both is inherent in how the requirement is phrased. Missing that, means you didn't check the requirements carefully; now, what I find interesting is that it does not say you have to print them in any particular order, or even consistently in the same order... –  jmoreno Mar 8 '12 at 9:43
1  
@back2dos: yeah, but doing it in a random order sounds like more fun...note that the requirement as given in this answer doesn't mention lines, just printing. If you're given a FizzBuzz test, it might be worthwhile to point out that there are a lot of unstated assumptions in it (then again, it might just get you painted as a wiseguy). –  jmoreno Jun 6 '12 at 15:11

In general, programming as a job is not about algorithms. You can spend years programming CRUD applications without requiring deep algorithmic skills.

Programming as a job is about:

  1. Communication:

    • Your source code is a mean of communicating your ideas to your pears. If nobody can read/understand your code, it's worthless.

    • A lone developer who doesn't speak to any other developer would probably start doing mistakes in code and believe that his own approach is the only acceptable one.

    • You must know how to communicate with stakeholders, QA department, users, visual designers, DBAs, etc.

    • As an experienced developer, you must teach less experienced colleagues who wish improving their skills.

  2. Knowledge of the right tools: version control, bug tracking system, IDEs, which language is better suited for a specific task and why, how to use code analysis, etc.

  3. Broad knowledge and culture: what are functional languages? How computers interpret code? Why LOC is a meaningless measure? etc.

  4. Deep knowledge of the language(s) you work with.

  5. Algorithms.

Computer Science, on the other hand, is more oriented to algorithms. If you work as a scientist, this may have nothing to do with a job of a developer, and you'll work more on how to optimize an algorithm, how to transform a data representation into another, etc.

share|improve this answer
12  
-1: "CRUD applications" are algorithms. They're just (generally) simple. There is no "noble meaning". –  S.Lott Feb 8 '12 at 18:04
2  
and source code is your only communication channel to the computer which does exactly what you tell it to do (and almost never what you want it to do) –  ratchet freak Feb 8 '12 at 18:35
4  
It's amazing how good the market is for cleaning up CRUDdy applications whose engineering teams ignored (or never learned) the basics of algorithms. –  JasonTrue Feb 8 '12 at 19:44
1  
@S.Lott: "CRUD applications are algorithms" is analogous to "I am America". ;) –  Jim G. Feb 8 '12 at 21:50
1  
@JimG: As Steven Colbert says "I am America and so can you". CRUD applications contain, are based on, include, are implementations of, are realizations of, embody, reflect algorithms. You only complained, without suggesting a specific preposition. Which would have made you happier? –  S.Lott Feb 8 '12 at 22:01

I think that questions about algorithms in interviews are one of the main ways that companies try to judge candidate's grasp of the computer science fundamentals. While this is not the only important area of skill for a professional programmer, it is one of the core competencies of a good programmer.

I think the reason a lot of big companies emphasize CS fundamentals in their interview process, is that it is the core skill that is is developed the least after having graduated and gone into the workforce. Practical programming ability, design skills, software engineering practices, and the like are all things that are primarily developed through experience, while your CS fundamentals are primarily developed in the course of your education.

As for how to practice algorithm design, Steve Yegge reccomends Skiena's The Algorithm Design Manual in his excellent guide to interviewing as a programmer.

share|improve this answer
3  
+1: It's about the fundamentals. –  S.Lott Feb 8 '12 at 18:19
3  
+1: programming languages, frameworks, operating system, editors, toolsets, they all come-and-go, but knowing how to solve problems effectively has everything to do with knowing the fundamentals of data structures and algorithms. These things stay with us always. –  Adam Crossland Feb 8 '12 at 20:20
    
"As for how to practice algorithm design, Steve Yegge reccomends Skiena's The Algorithm Design Manual in his excellent guide to interviewing as a programmer." Sorry, but this might not be applicable to the person who asked this question as he happens to be a grad student. Google/MS has moved on from Skiena (for grad students), to asking questions which have appeared in international collegiate programming competitions. (This I know for sure from anecdotal experience). Skiena's book is still used - but mainly for the undergrad level candidates. –  user396089 Jun 6 '12 at 3:27
    
As for the questions that appear in the programming competitions - you are pretty much hosed if you have not seen the question before (unless your IQ also happens to be 3 SD away from the normal) –  user396089 Jun 6 '12 at 3:29

I personally see "standard" algorithms and datastructures as part of a programmer's vocabulary. And many of the practical problems you face as a programmer often have a solution which is (at least partially) expressible in this vocabulary.

Having this vocabulary as your disposal prevents you from having to come up with your "own" solutions (reinventing the wheel so to say), allowing you to work smarter and often faster.

"I can't seem to get interested in solving seemingly too complicated problems found in most textbook or websites"

"I find it immensely difficult to remember and reuse them later"

Force yourself to complete them. You will thank yourself later on. Even if you don't remember them in full detail (although with enough practice you certainly will), to be able to say "I remember solving something similar using algorithm X or datastructure Y" will help you tremendously. Even if it does require you to look up the details and refresh your memory.

share|improve this answer
    
+1 for data structures. They are the other half of the algorithmic coin. –  Spencer Rathbun Feb 9 '12 at 13:56

As a successful software developer who is self taught and only took a few computer science courses in college, I will say that the largest problems facing business today are not the ability for all of their programmers to write a bubble sort algorithm in the most efficient manner possible. The true problems that businesses face:

  • Developers who cannot quickly learn and adapt to new domains

  • Developers who cannot socially interact with clients or stakeholders in a meaningful way

  • Developers who cannot second guess and question incorrect or poorly thought out business requirements

  • Developers who do not understand how to thoroughly test their code and features

  • Developers who cannot provide meaningful estimates in a timely fashion

  • Developers who cannot create clear and concise documentation

  • Developers who cannot be self starting or take charge of a situation

Nine times out of ten I will wager that nearly all circumstances where a developer flounders in a company is because they hopelessly fail in one of the qualities above. Forget Google and Facebook, they are exception cases and have legitimate need for people who deeply understand computer science.

Real businesses though don't struggle with the complexities of computer science, they struggle with the complexities of humanity. The problem is that it is REALLY hard to test for the above mentioned qualities. Most of the time you have to judge people on these qualities based on your gut reaction. That is hard if you do not have good people skills and intuition, it is much easier to test for algorithm knowledge.

share|improve this answer
    
+1 Regular and non-google-like-freakish companies need people with good business skills, and primarily in understanding how to invent/apply/manage/modify processes. It's no mistake that Google-like companies did not hatch the Agile movement, because computer science isn't about solving business problems. –  S.Robins Feb 9 '12 at 1:11

Although you cannot be a good programmer without knowing your algorithms, it is unfair to keep other aspects of the programming profession out of the picture. For example, strict discipline and good command of your native tongue are at least as significant to being a good programmer as your knowledge of algorithms is. One should also not underestimate the importance of understanding your basic tools, such as programming languages, source control systems, testing environments, et cetera.

However, when it comes to interviews, measuring your understanding of algorithms is a lot simpler than measuring your other abilities related to working as a programmer. That is why interviewers often concentrate on asking about algorithms, and pay close attention to the way you explain them during the interview. It is not because other things are less important, but because it is hard to assess these other things in the 30 minutes allocated for the interview.

share|improve this answer
1  
+1 Perfect answer! It is easier to test for algorithm knowledge. –  maple_shaft Feb 8 '12 at 18:51
    
"your algorithms" -- I am self taught. Is there a source or list somewhere that states what these common algorithms are that every programmer should know? I would like to read through them. Thanks! –  Ominus Feb 8 '12 at 19:10
2  
@Ominus Although there is no general consensus on the "gentleman's list" of algorithms, in most instances it would include searching, sorting, traversing data structures that lack spacial continuity (linked lists, binary trees, etc.), and rudimentary (mis)applications of recursion (recursive factorial, Fibonacci sequence, etc.) –  dasblinkenlight Feb 8 '12 at 19:24
    
@Ominus - I too am self-taught but I think "Introduction To Algorithms" - CLRS is a good way to get familiar with the field. Skiena's book "The Algorithm Design Manual" is also good. –  Tod Mar 8 '12 at 6:46

The answer is entirely dependent on the work you are pursuing. Some fields are particularly more algorithm focused than others. Speaking to that note though I had the pleasure to interview with Amazon multiple times. Even though the position would have little to do with these complex algorithms I was grilled on how to make a task amortized constant time.

What proving a strong understanding of algorithms provides is proof to your potential employer that you are an apt problem solver. It isn't really a good indicator (IMO) of a good employee but some employers use this for screening. If you are applying for a position that requires a graduate degree you are going to be expected to have a more rigorous foundation in algorithms.

What (IMO) is immensely helpful in practice isn't to memorize specific algorithms but through understanding how some algorithms work there is this small nugget in the back of your mind where you will say "I have seen this before" or "I know I can do this better" which will spawn a bit of research on the solution to your problem.

share|improve this answer
    
+1 for talking about the hiring bar for grad students. Some companies are much fussier when hiring grad students than undergrads. But to be fair to them, grad students are also better paid, and typically recruited at a higher level internally. –  user396089 Jun 6 '12 at 3:34

Yes, programming is mostly about algorithms.

But maybe not in the sense that you're thinking.

I get the impression we're all using different definitions of algorithm. To be honest, this question is hard to answer because algorithm is a vague term. I'll use Wikipedia's definition to answer this question:

A set of rules that precisely defines a sequence of operations.

This is the heart and soul of programming. When you write any code, you are just implementing an algorithm. If you're writing some CRUD applications, you're implementing a simple algorithm. Being able to come up with an algorithm to solve a problem is what programming is. The rest are just details.

I disagree with the previous poster that said having a deep understanding of a language is more important than understanding algorithms. Any good programmer should be able to deeply learn a language, but without algorithms, you can't come up with any code on your own.

share|improve this answer
    
From another perspective, in Mathematics the heart and soul may be algorithms, however for Programming it is something else. You can write software without needing algorithms per se (not good software perhaps), but you can't write software without logic, and abstract thinking. At it's heart however, it's about solving problems. Finding the solution is an algorithmic process, yet the solution itself isn't necessarily an algorithm. –  S.Robins Feb 9 '12 at 1:06

I always think programming is more data-driven than algorithms.. but then, what use is data if you don't do things to it... all those manipulations are algorithms. So actually, yes, programming is pretty much entirely algorithm based.

It may not look like maths, and a lot of algorithmic work you'd do day-to-day is very simply stuff like sending data between a GUI and a program, but that counts as an algorithm too. Inserting an element in a listbox is a standard insert algorithm that comes with its own issues like performance and list structure manipulations.

share|improve this answer

Only programmers that work for those companies can really answer you question. The kinds of algorithms dealt with in say "Introduction to Algorithms" have probably played a part in 0.01% of my programming life over the past 25 years. When I need a data structure or a sort usually the supplied libraries or frameworks have what I need. When I need a super fast FFT I find something like the Intel Math lib rather than write one myself. However, I can how what they do at Google is way different than what I've done in my career. Skiena's book "The Algorithm Design Manual" was eye-opening because of the War stories he tells. You can tell he uses Algorithms in his job A LOT.

In my experience as an independent programming consultant, success has come from three things 1. Communicating effectively with clients 2. Writing code that works. 3. Managing Complexity

Doing just numbers 1 and 2 isn't enough. If code isn't maintainable (by someone other than the programmer(s) who wrote it, it's doomed.

Number 3 is the hardest programming skill to master. It requires thought be put into architecture, design and coding. It requires mastering refactoring. It requires an understanding of SOLID/DRY principles. If I had to hire a programmer who had read Intro to Algorithms and dedicated himself to mastering it or one that read The Pragmatic Programmer and dedicated himself to being one, I would hire the latter every time. (Not that they have to mutually exclusive).

share|improve this answer

Yes.

Computer Science is mostly algorithms (by percentage).

No.

But that is the "Science" of computers. The most common application of Computer Science is Software Engineering. Software Engineering is not mainly algorithms. It's mainly about the art of creating, the pursuit of perfection, and is centered around positively affecting the lives of real people who exist today. While Computer Science may share some of the same motivation, it is a far cry from Software Engineering.

Ask a tenured professor at a major Computer Science University what the most critical thing to understand about programming is, and they will likely tell you "algorithms and data structures"

Ask a senior developer at a major software company what the most critical thing to understand about programming is, and they will likely tell you, "learning to delight customers" (implied in that is understanding agile, thinking like a customer, shipping on time and continuously, making things that work, etc)

Might seem like semantics, but from my understanding the two are remarkably different both in practice and theory.

share|improve this answer

If I had to pick one thing in computer science as being the most important part of it, I would pick abstractions, not algorithms.

share|improve this answer

You've asked two questions in the question header, so I'll answer both of them.

Yes, Computer Science is all about algorithms. Well... actually that's a little misleading because there are many aspects to computer science, so I'll rephrase. Computer science as it is applied in the working world is predominantly about algorithms. Companies like Google, Facebook, and all those crazy places in Wall Street hiring Physicists and Developers want highly complex problems reduced to a simple form, which in itself requires a deep understanding of mathematics, and algorithm design.

No, Programming is not all about algorithms. Programming is about taking specifications and converting them into code which can be compiled for execution.

The extra part of the answer: Software Development is not programming, and yet many seem to confuse the terms and use them interchangeably. Programming is merely a function or a technique perhaps of the larger process of Software Development. Software Development is certainly not all about algorithms, it's about solving problems with software, and applying sound business compatible processes to allow problems to be solved efficiently. While software development processes - and even programming itself - might be algorithmic processes in their nature, this is not the same as being about algorithms.

share|improve this answer

In Computer Science what concepts you learn will be of no use until you show it.The problem is of main concern that needs to be solved so algorithm is a brief planning of how the problem will be solved in general. Therefore it is of major concern in the Computer Science world.

I think almost every aspect of Computer Science need Algorithm Let me show you this The following list would include various Computer Science areas and which algorithms they use.

Automata

Powerset construction. Algorithm to convert nondeterministic automaton to deterministic automaton. Todd-Coxeter algorithm. Procedure for generating cosets.

Artificial intelligence

Alpha-beta. Alpha max plus beta min. Widely used in board games. Ant-algorithms. The ant colony optimisation is a set of algorithms inspired by ant behavior to solve a problem, find the best path between two locations. DE (Differential evolution). Solve the Chebyshev polynomial fitting problem. Semi-Supervised Recognition of Sarcastic Sentences in Online Product Reviews. Algortithm that recognize sacarsms or irony in a tweet or an online document. A such algorithm will be essential for humanoid robots programming too.

Computer vision

Epitome. Represent an image or video by a smaller one. Counting objects in an image. Uses the connected-component labeling algorithm to first label each object, and count then the objects. O'Carroll algorithm. From a mathematical conversion of insect vision, this algorithm evaluates how to get around avoiding objects.

Genetic algorithms

They uses three operator. selection (choose solution), reproduction (use choosen solutions to construct other ones), replacement (replace solution if better).

Fitness proportionate selection. Also known as roulette-wheel selection, is a function used for selecting solutions. Truncation selection. Another method for selecting solutions, ordered by fitness. Tournament selection. Select the best solution by a kind of tournament. Stochastic universal sampling. The individuals are mapped to contiguous segments of a line, such that each individual's segment is equal in size to its fitness exactly as in roulette-wheel selection.

Neural networks

Hopfield net. Recurrent artificial neural network that serve as content-addressable memory systems with binary threshold units. They converge to a stable state. Backpropagation. Supervised learning technique used for training artificial neural networks. Self-organizing map (Kohonen map). Neural networks trained using unsupervised learning to produce low dimensional (2D, 3D) representation of the training samples. Good for visualizing high-dimensional data.

Bioinformatics

Needleman-Wunsch. Performs a global alignment on two sequences, for protein or nucleotide sequences. Smith-Waterman. Variation of the Needleman-Wunsch.

Compression

Lossless compression algorithms

Burrows-Wheeler transform. Preprocessing useful for improving lossless compression. Deflate. Data compression used by ZIP. Delta encoding. Aid to compression of data in which sequential data occurs frequently. Incremental encoding. Delta encoding applied to sequences of strings. LZW. (Lempel-Ziv-Welch). Successor of LZ78. Builds a translation table from the data to compress. Is used by the GIF graphical format. LZ77 and 78. The basis of further LZ variations (LZW, LZSS, ...). They are both dictionary coders. LZMA. Short for Lempel-Ziv-Markov chain-Algorithm. LZO. Data compression algorithm that is focused on speed. PPM (Prediction by Partial Matching). Adaptive statistical data compression technique based on context modeling and prediction. Shannon-Fano coding. Constructs prefix codes based on a set of symbols and their probabilities. Truncated binary. An entropy encoding typically used for uniform probability distributions with a finite alphabet. Improve binary encoding. Run-length encoding. Primary compression that replaces a sequence of same code by the number of occurences. Sequitur. Incremental grammar inference on a string. EZW (Embedded Zerotree Wavelet). Progressive encoding to compress an image into a bit stream with increasing accuracy. May be lossy compression also with better results.

Entropy encoding Coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols .

Huffman coding. Simple lossless compression taking advantage of relative character frequencies. Adaptive Huffman coding. Adaptive coding technique based on Huffman coding. Arithmetic coding. Advanced entropy coding. Range encoding. Same as arithmetic coding, but looked at in a slightly different way. Unary coding. Code that represents a number n with n ones followed by a zero. Elias delta, gamma, omega coding. Universal code encoding the positive integers. Fibonacci coding. Universal code which encodes positive integers into binary code words. Golomb coding. Form of entropy coding that is optimal for alphabets following geometric distributions. Rice coding. Form of entropy coding that is optimal for alphabets following geometric distributions.

Lossy compression algorithms

Linear predictive coding. Lossy compression by representing the spectral envelope of a digital signal of speech in compressed form. A-law algorithm. Standard companding algorithm. Mu-law algorithm. Standard analog signal compression or companding algorithm. Fractal compression. Method used to compress images using fractals. Transform coding. Type of data compression for data like audio signals or photographic images. Vector quantization. Technique often used in lossy data compression. Wavelet compression. Form of data compression well suited for image and audio compression.

Cryptography

Secret key (symmetric encryption)

Use a secret key (or a pair of directly related keys) for both decryption and encryption.

Advanced Encryption Standard (AES), also known as Rijndael. Blowfish. Designed by Schneier as a general-purpose algorithm, intended as a replacement for the aging DE. Data Encryption Standard (DES), formerly DE Algorithm. IDEA (International Data Encryption Algorithm). Formerly IPES (Improved PES), another replacement for DES. Is used by PGP (Pretty Good Privacy). Performs transformations on data splitted in blocks, using a key. RC4 or ARC4. Stream cipher widely-used in protocols such as SSL for Internet traffic and WEP for wireless networks. Tiny Encryption Algorithm. Easy to implement block cipher algorithme using some formulas. PES (Proposed Encryption Standard). Older name for IDEA.

Public key (asymmetric encryption)

Use a pair of keys, designated as public key and private key. The public key encrypt the message, only the private key permits to decrypt it.

DSA (Digital Signature Algorithm). Generate keys with prime and random numbers. Was used by US agencies, and now public domain. ElGamal. Based on Diffie-Hellman, used by GNU Privacy Guard software, PGP, and other cryptographic systems. RSA (Rivest, Shamir, Adleman). Widely used in electronic commerce protocols. Use prime numbers. Diffie-Hellman (Merkle) key exchange (or exponential key exchange). Method and algorithm to share secret over an unprotected communications channel. Used by RSA. NTRUEncrypt. Make use of rings of polynomials with convolution multiplications.

Message digest functions

A message digest is a code resulting of the encryption of a string or data of any length, processed by a hash function.

MD5. Used for checking ISO images of CDs or DVDs. RIPEMD (RACE Integrity Primitives Evaluation Message Digest). Based upon the principles of MD4 and similar to SHA-1. SHA-1 (Secure Hash Algorithm 1). Most commonly used of the SHA set of related cryptographic hash functions. Was designed by the NSA agency. HMAC. keyed-hash message authentication. Tiger (TTH). Usually used in Tiger tree hashes.

Cryptographic using pseudo-random numbers See. Random Number Generators

Techniques in cryptography

Secret sharing, Secret Splitting, Key Splitting, M of N algorithms.

Shamir's secret sharing scheme. This is a formula based on polynomial interpolation. Blakley's secret sharing scheme. Is geometric in nature, the secret is a point in an m-dimensional space.

Other techniques and decryption

Subset sum. Given a set of integers, does any subset sum equal zero? Used in cryptography. Shor's algorithm. Quantum algorithm able to decrypt a code based on asymetric functions such as RSA.

Geometry

Gift wrapping. Determining the convex hull of a set of points. Gilbert-Johnson-Keerthi distance. Determining the smallest distance between two convex shapes. Graham scan. Determining the convex hull of a set of points in the plane. Line segment intersection. Finding whether lines intersect with a sweep line algorithm. Point in polygon. Tests whether a given point lies within a given. Ray/Plane intersection. *Line/Triangle intersection.* Particular case of Ray/Plane intersection. Polygonization of implicit surfaces. Approximate an implicit surface with a polygonal representation. Triangulation. Method to evaluate the distance to a point from angles to other points, whose distance is known.

Graphs 3D Surface Tracker Technology. Process to add images on walls in a video while hidden surfaces are taken into account. Bellman-Ford. Computes shortest paths in a weighted graph (where some of the edge weights may be negative). Dijkstra's algorithm. Computes shortest paths in a graph with non-negative edge weights. Perturbation methods. An algorithm that computes a locally shortest paths in a graph. Floyd-Warshall. Solves the all pairs shortest path problem in a weighted, directed graph. Floyd's cycle-finding. Finds cycles in iterations. Johnson. All pairs shortest path algorithm in sparse weighted directed graph. Kruskal. Finds a minimum spanning tree for a graph. Prim's. Finds a minimum spanning tree for a graph. Also called DJP , Jarník or Prim–Jarník algorithm. *Boruvka.* Finds a minimum spanning tree for a graph. Ford-Fulkerson. Computes the maximum flow in a graph. Edmonds-Karp. Implementation of Ford-Fulkerson. Nonblocking Minimal Spanning Switch. For a telephone exchange. Woodhouse-Sharp. Finds a minimum spanning tree for a graph. Spring based. Algorithm for graph drawing. Hungarian. Algorithm for finding a perfect matching. Coloring algorithm. Graph coloring algorithm. Nearest neighbour. Find nearest neighbour. Topological sort. Sort a directed acyclic graph in such a manner that each node comes before all nodes to which it has edges (according to directions). Tarjan's off-line least common ancestors algorithm. Compute lowest common ancestors for pairs of nodes in a tree.

Graphics

Bresenham's line algorithm. Uses decision variables to plots a straight line between 2 specified points. Landscape Draw a 3D scenery. *DDA line algorithm.* Uses floating-point math to plots a straight line between 2 specified points. Flood fill. Fills a connected region with a color. Image Restoring. Restore photo, improve images. Xiaolin Wu's line algorithm. Line antialiasing. Painter's algorithm. Detects visible parts of a 3-dimensional scenery. Ray tracing. Realistic image rendering. Phong shading. An illumination model and an interpolation method in 3D computer graphics. Gouraud shading. Simulate the differing effects of light and colour across the surface of a 3D object. Scanline rendering. Constructs an image by moving an imaginary line. Global illumination. Considers direct illumination and reflection from other objects. Interpolation. Constructing new data points such as in digital zoom. Resynthesizer. Remove an object on a photo and rebuild the background Used by Photoshop and The Gimp. Resynthesizer tutorial . Slope-intercept algorithm. It is an implementation of the slope-intercept formula for drawing a line. Spline interpolation. Reduces error with Runge's phenomenon. 3D Surface Tracker Technology. Adding images or vidéo on walls in a vidéo, hidden surfaces being taken into account.

Lists, arrays and trees

Searching

Dictionary search. See predictive search. Selection algorithm. Finds the kth largest item in a list. Binary search algorithm. Locates an item in a sorted list. Breadth-first search. Traverses a graph level by level. Depth-first search. Traverses a graph branch by branch. Best-first search. Traverses a graph in the order of likely importance using a priority queue. A tree search.* Special case of best-first search that uses heuristics to improve speed. Uniform-cost search. A tree search that finds the lowest cost route where costs vary. Predictive search. Binary like search which factors in magnitude of search term versus the high and low values in the search. Hash table. Associate keys to items in an unsorted collection, to retrieve them in a linear time. Interpolated search. See predictive search.

Sorting

Binary tree sort. Sort of a binary tree, incremental, similar to insertion sort. Bogosort. Inefficient random sort of a desk card. Bubble sort. For each pair of indices, swap the items if out of order. Bucket sort. Split a list in buckets and sort them individually. Generalizes pigeonhole sort. Cocktail sort (or bidirectional bubble, shaker, ripple, shuttle, happy hour sort). Variation of bubble sort that sorts in both directions each pass through the list. Comb sort. Efficient variation of bubble sort that eliminates "turtles", the small values near the end of the list and makes use of gaps bewteen values. Counting sort. It uses the range of numbers in the list A to create an array B of this length. Indexes in B are used to count how many elements in A have a value less than i. Gnome sort. Similar to insertion sort except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. Heapsort. Convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list. Insertion sort. Determine where the current item belongs in the list of sorted ones, and insert it there. Introsort. Or introspective sort. It begins in quicksort and switches to heapsort at certain recursion level. Merge sort. Sort the first and second half of the list separately, then merge the sorted lists. Pancake sort. Reverse elements of some prefix of a sequence. Pigeonhole sort. Fill an empty array with all elements of an array to be sorted, in order. Postman sort. Hierarchical variant of bucket sort, used by post offices. Quicksort. Divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice. Radix sort. Sorts keys associated to items, or integer by processing digits. Selection sort. Pick the smallest of the remaining elements, add it to the end of the sorted list. Shell sort. Improves insertion sort with use of gaps between values. Smoothsort. See heapsort. Stochastic sort. See bogosort.

and many more...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.