Algorithms for Web Developers

August 21, 2009

Referring to my post below, I was thinking about the algorithms that actually have practical usage in the field of web developing. I would really appreciate any help for pointing me towards some of the algorithms.

To call yourself even a programmer, the most important structure in programming you should know is the “loop”. Yes, some even go further and say that those who can use loops effeciently have the rights to call themselves programmers. But I am going ahead. Here are the basic list of algorithms that you should know how to implement:

  1. Binary Search
  2. Any sorting algorithm (such as mergsort, quicksort, heapsort etc.)
  3. Union-Find (think about Social network and you will get the idea)
  4. Encryption algorithm (RSA, DES, Blowfish or whatever you know)
  5. Dijkstra’s algorithm (really useful in figuring out the shortest path)

Remember, master these basic algorithms and then step up to the advanced algorithms. Do you know why Google is famous? They are famous because they’ve invented a simple but elegant solution to searching. Clearly, the developers had to go through all the basic algorithms to create something so sophisticated.


The Most Important Algorithms

August 21, 2009

After a long time, I am posting a link to a collection of some of the most important algorithms for a Computer scientist. However, some of them are pretty advanced so don’t get upset if you don’t know how to implement them in the programming language you are dealing with. After all, some people just get famous because they can implement the appropriate algorithm in the correct way. So here they are:

  1. A* search algorithm
    Graph search algorithm that finds a path from a given initial node to a given goal node. It employs a heuristic estimate that ranks each node by an estimate of the best route that goes through that node. It visits the nodes in order of this heuristic estimate. The A* algorithm is therefore an example of best-first search.
  2. Beam Search
    Beam search is a search algorithm that is an optimization of best-first search. Like best-first search, it uses a heuristic function to evaluate the promise of each node it examines. Beam search, however, only unfolds the first m most promising nodes at each depth, where m is a fixed number, the beam width.
  3. Binary search
    Technique for finding a particular value in a linear array, by ruling out half of the data at each step.
  4. Branch and bound
    A general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization.
  5. Buchberger’s algorithm
    In computational algebraic geometry and computational commutative algebra, Buchberger’s algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. One can view it as a generalization of the Euclidean algorithm for univariate gcd computation and of Gaussian elimination for linear systems.
  6. Data compression
    Data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes.
  7. Diffie-Hellman key exchange
    Cryptographic protocol which allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.
  8. Dijkstra’s algorithm
    Algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights.
  9. Discrete differentiation
    I.e., the formula f'(x) = (f(x+h) – f(x-h)) / 2h.
  10. Dynamic programming
    Dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below.
  11. Euclidean algorithm
    Algorithm to determine the greatest common divisor (gcd) of two integers. It is one of the oldest algorithms known, since it appeared in Euclid’s Elements around 300 BC. The algorithm does not require factoring the two integers.
  12. Expectation-maximization algorithm (EM-Training)
    In statistical computing, an expectation-maximization (EM) algorithm is an algorithm for finding maximum likelihood estimates of parameters in probabilistic models, where the model depends on unobserved latent variables. EM alternates between performing an expectation step, which computes the expected value of the latent variables, and a maximization step, which computes the maximum likelihood estimates of the parameters given the data and setting the latent variables to their expectation.
  13. Fast Fourier transform (FFT)
    Efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. FFTs are of great importance to a wide variety of applications, from digital signal processing to solving partial differential equations to algorithms for quickly multiplying large integers.
  14. Gradient descent
    Gradient descent is an optimization algorithm that approaches a local minimum of a function by taking steps proportional to the negative of the gradient (or the approximate gradient) of the function at the current point. If instead one takes steps proportional to the gradient, one approaches a local maximum of that function; the procedure is then known as gradient ascent.
  15. Hashing
    A function for summarizing or probabilistically identifying data. Typically this means one applies a mathematical formula to the data, producing a string which is probably more or less unique to that data. The string is much shorter than the original data, but can be used to uniquely identify it.
  16. Heaps (heap sort)
    In computer science a heap is a specialized tree-based data structure. Heaps are favourite data structures for many applications: Heap sort, selection algorithms (finding the min, max or both of them, median or even any kth element in sublinear time), graph algorithms.
  17. Karatsuba multiplication
    For systems that need to multiply numbers in the range of several thousand digits, such as computer algebra systems and bignum libraries, long multiplication is too slow. These systems employ Karatsuba multiplication, which was discovered in 1962.
  18. LLL algorithm
    The Lenstra-Lenstra-Lovasz lattice reduction (LLL) algorithm is an algorithm which, given a lattice basis as input, outputs a basis with short, nearly orthogonal vectors. The LLL algorithm has found numerous applications in cryptanalysis of public-key encryption schemes: knapsack cryptosystems, RSA with particular settings, and so forth.
  19. Maximum flow
    The maximum flow problem is finding a legal flow through a flow network that is maximal. Sometimes it is defined as finding the value of such a flow. The maximum flow problem can be seen as special case of more complex network flow problems. The maximal flow is related to the cuts in a network by the Max-flow min-cut theorem. The Ford-Fulkerson algorithm computes the maximum flow in a flow network.
  20. Merge sort
    A sorting algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e.g. file streams) into a specified order.
  21. Newton’s method
    Efficient algorithm for finding approximations to the zeros (or roots) of a real-valued function. Newton’s method is also a well-known algorithm for finding roots of equations in one or more dimensions. It can also be used to find local maxima and local minima of functions.
  22. Q-learning
    Q-learning is a reinforcement learning technique that works by learning an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter. A strength with Q-learning is that it is able to compare the expected utility of the available actions without requiring a model of the environment.
  23. Quadratic sieve
    The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the number field sieve, NFS). It is still the fastest for integers under 110 decimal digits or so, and is considerably simpler than the number field sieve.
  24. RANSAC
    RANSAC is an abbreviation for “RANdom SAmple Consensus”. It is an algorithm to estimate parameters of a mathematical model from a set of observed data which contains “outliers”. A basic assumption is that the data consists of “inliers”, i. e., data points which can be explained by some set of model parameters, and “outliers” which are data points that do not fit the model.
  25. RSA
    Algorithm for public-key encryption. It was the first algorithm known to be suitable for signing as well as encryption. RSA is still widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys.
  26. Schönhage-Strassen algorithm
    In mathematics, the Schönhage-Strassen algorithm is an asymptotically fast method for multiplication of large integer numbers. The run-time is O(N log(N) log(log(N))). The algorithm uses Fast Fourier Transforms in rings.
  27. Simplex algorithm
    In mathematical optimization theory, the simplex algorithm a popular technique for numerical solution of the linear programming problem. A linear programming problem consists of a collection of linear inequalities on a number of real variables and a fixed linear functional which is to be maximized (or minimized).
  28. Singular value decomposition (SVD)
    In linear algebra, SVD is an important factorization of a rectangular real or complex matrix, with several applications in signal processing and statistics, e.g., computing the pseudoinverse of a matrix (to solve the least squares problem), solving overdetermined linear systems, matrix approximation, numerical weather prediction.
  29. Solving a system of linear equations
    Systems of linear equations belong to the oldest problems in mathematics and they have many applications, such as in digital signal processing, estimation, forecasting and generally in linear programming and in the approximation of non-linear problems in numerical analysis. An efficient way to solve systems of linear equations is given by the Gauss-Jordan elimination or by the Cholesky decomposition.
  30. Strukturtensor
    In pattern recognition: Computes a measure for every pixel which tells you if this pixel is located in a homogenous region, if it belongs to an edge, or if it is a vertex.
  31. Union-find
    Given a set of elements, it is often useful to partition them into a number of separate, nonoverlapping groups. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:
    Find: Determine which group a particular element is in.
    Union: Combine or merge two groups into a single group.
  32. Viterbi algorithm
    Dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models.

Source: http://www.risc.uni-linz.ac.at/people/ckoutsch/stuff/e_algorithms.html


Bunch of OOP Tutorials

June 13, 2009

Lesson: Object-Oriented Programming Concepts by Java

Basically it’s an introduction to Object-Oriented Programming written by Java experts. It’s a delight for programmers though since the tutorials mainly focus on the concept of the OO Programming rather than specific language syntax. Covers most of the topics in OOP including interfaces.

The Object Oriented Programming Web

I guess the site can describe itself better than I can:

The Object Oriented Programming Web publishes FREE programming and computer science tutorials, lecture notes, course slides and e-books. OOPWeb.com is a great resource for all programmers and computer science students, but it’s especially popular among those who are interested in C++, Java and Object Oriented Programming.

And damn, it has some of the nicest collections of algorithms, ranging from graph theory to Sorting and Searching algorithms

Object Oriented Programming in JavaScript by Mike Koss

I know it’s not a language independent tutorial but it is really, really an excellent tutorial. And besides, most of the web designers and programmers need to know JavaScript, the so-called “behavioural” language of the web. HIGHLY RECOMMENDED.

JavaScript Object-Oriented Programming

This is an article from SitePoint, so we can expect it to be really good. And it is. I am not much of a hard-core programmer but I can say that it’s a bit technical and as the name suggests, the article is language specific. But then again, everybody developing the web needs to know JavaScript by heart.

Object-Oriented Programming Concept

The tutorial is relatively short and can be skimmed pretty quickly (hey! that’s a plus point for us lazy coders). Mainly deals with the different types of relations between objects, their lifestyles and soap operas (okay, cancel the last one). Has some neat and easy-to-understand examples (cars and pizzas).

OOPS Concepts

This article from Exforsys Inc. is what you really want. It’s language independent and although sometimes it bends towards technical terms, it is relatively easy to understand. P.S. I first thought the site name was Exorcist (dyslexic? hmm).

What is Object Oriented Programming (OOP)? by Tony Marston

I don’t know about you but I really liked Tony’s series of articles about Object-Oriented Programming. It’s really meant to be Newbie-Object-Oriented-Programming (NOOP? I thought it would be noob). The author puts some really neat examples to make sure that everyone can understand the basic concept of Object-Oriented Programming.

Object Oriented Programming with PHP by Kevin Waterson

I know some guys get upset seeing the wealth of information scattered around the web but none of them giving suitable explanations. Well, Kevin is one of them then. This guy probably packed a whole book into one complete page explaining all the important concepts of OOP and also for us lucky web developers, he has written the article using PHP! He discusses advanced topics like Autoload, Overloading, and Class Constants. MUST READ.

OO PHP Part 1: OOP in Full Effect

And boy didn’t we see the effect in full or what? This article is a whopping huge post of detailed information about the PHP OOP features. Yes sirree it is not language dependent article but WTH (notice: I didn’t use WTF…I think I just did). So get some cups of 100% caffeinated coffee and start gaining vital knowledge about OOP.


12 Excellent Free Tools for Monitoring Your Site’s Uptime

June 13, 2009

Source: http://sixrevisions.com/tools/12-excellent-free-tools-for-monitoring-your-sites-uptime/#more-1051

Site24×7

Sites24×7 is a simple website-monitoring tool for keeping track of your website or web application’s availability. It tests your uptime in several global locations such as Singapore, the Netherlands, and New Jersey so that you can be assured that your website is being served in major regions of the world at optimal page load times.

Are My Sites Up?

Are My Sites Up? is a straightforward free web tool for being alerted when your websites are down. With Are My Sites Up?, you can monitor up to five different websites, receive email and text message alerts so that you have constant awareness of your sites’ uptime, and checks performed 25 times a day.

mon.itor.us

mon.itor.us is a free site monitoring tool with loads of useful features that will help you maintain a high uptime. By providing you with a ton of information about your site and web server, you can quickly spot potential issues that relate with your site’s availability. mon.itor.us has an intuitive dashboard GUI, the ability to send you downtime alerts via email, text message, and RSS, monitoring from multiple geographical locations, and real-time visitor monitoring. It’s a simple-to-use tool boasting a low setup time (sign-up and installation) of only five minutes.

Montastic

Montastic is a free, quick, and easy-to-use tool for keeping constant knowledge of your websites’ availability. Developed by Metadot, Montastic sends you warnings whenever your site crashes (and when it comes back up) through email, RSS, or their Windows and Mac widget. Montastic lets you monitor up to 100 sites per account, supports monitoring for HTTP and HTTP Secure connections, and a simple and elegant end-user interface.

ServerMojo

ServerMojo is a simple-to-use service for supervising your web server’s uptime. It alerts you via IM, Twitter, and email when your site is unavailable. ServerMojo permits you to monitor one site at one-hour intervals.

HostTracker

HostTracker is a free web tool for monitoring site availability. You can monitor up to two websites at a time and get free weekly, monthly, quarterly, and yearly reports on your web server’s performance. HostTracker provides distributed monitoring, tracking of useful data on site availability for diagnostics, and alerts of issues via email, IM, and/or SMS. HostTracker’s front page features a nice utility widget for instantly checking your website’s availability: you simply enter your URL and it will ping your server.

Observu

Observu is a very simple tool intentionally designed for rapid set-up and ease of use. With Observu, you can monitor an unlimited amount of websites/web servers, which is great for multi-site owners who want a hassle-free way of keeping track of what’s going on with their web properties.

InternetSeer

InternetSeer has a free standard service that offers 60-minute intervals for monitoring your site’s uptime and performance. It gives you site availability and page response time reports, real-time error notifications, and a weekly report on your server’s performance for diagnostics.

FreeSiteStatus

FreeSiteStatus is a web-based application that provides email alerts of your site’s downtime, a monitoring interval of 60 minutes, and a distributed monitoring network of 13 global locations. FreeSiteStatus also has a nifty tool on the site called “Quick Test” for instantly checking your site services’ performance and availability (i.e. HTTP, POP3, MySQL, FTP, and more).

SiteUptime

SiteUptime is a free tool that lets you monitor one site at 30 or 60-minute intervals from four geographical locations. You can monitor your HTTP (web server), POP3 (email server), FTP server, and more using SiteUptime. It also gives you the option to display your availability statistics publicly, which you can use as a site widget to show off your site or web application’s high-availability. Check out the live demo of SiteUptime.

Basic State

Basic State is a free monitoring tool for uptime, server, and network failures of your site. Basic State checks your website at 15-minute intervals and sends you notifications via email or text message when something goes kaboom. With a simple sign-up process that will get you set up in no time and the ability to keep tabs on any number of sites, Basic State is a solid option to consider when looking into site monitoring tools.

Livewatch

Livewatch allows you to get alerts when your site is unavailable via email, SMS, phone, IM, and even Twitter. It can record and create PDF reports for site failures so that you can keep track of downtime events for documentation and troubleshooting. They also have a nice and simple web tool for instantly checking your site availability called Free HTTP Check that quickly checks your web server’s availability.


How to Add an API to your Web Service

June 3, 2009

Source: http://particletree.com/features/how-to-add-an-api-to-your-web-service/

This article explains clearly what is an API and how you can implement one for your own website. Discusses SOAP and REST web services and also provides the codes for implementation.

APIs are a great way to extend your application, build a community, excite your users and get in on the Mashup Mania spreading across the web. While there’s plenty out there wanting in on the action, there’s a lot of questions about how to actually go about creating an API for a web application. Like everything else technical on the web these days, there are tons of complicated and scary documents out there ready to intimidate the unprepared. In an attempt to get everyone on the bus in one piece, we’ve tried to filter through the hard stuff and give an easy to understand starting point for anyone on a quest to API’ify their web service.


30 HTML Best Practices for Beginners

June 2, 2009

Source: http://net.tutsplus.com/tutorials/html-css-techniques/30-html-best-practices-for-beginners/

Just for your curiosity, I am naming the main 30 practices:

  1. Always Close Your Tags
  2. Declare the Correct DocType
  3. Never Use Inline Styles
  4. Place all External CSS Files Within the Head Tag
  5. Consider Placing Javascript Files at the Bottom
  6. Never Use Inline Javascript. It’s not 1996!
  7. Validate Continuously
  8. Download Firebug
  9. Use Firebug! (duh!)
  10. Keep Your Tag Names Lowercase
  11. Use H1 – H6 Tags
  12. If Building a Blog, Save the H1 for the Article Title
  13. Download ySlow
  14. Wrap Navigation with an Unordered List
  15. Learn How to Target IE
  16. Choose a Great Code Editor
  17. Once the Website is Complete, Compress!
  18. Cut, Cut, Cut
  19. All Images Require “Alt” Attributes
  20. Stay up Late
  21. View Source
  22. Style ALL Elements
  23. Use Twitter
  24. Learn Photoshop
  25. Learn Each HTML Tag
  26. Participate in the Community
  27. Use a CSS Reset
  28. Line ’em Up!
  29. Slice a PSD
  30. Don’t Use a Framework…Yet

Are URL Shorteners A Necessary Evil, Or Just Evil?

May 31, 2009

One of the most viral activities on the Web is sharing links. It is fast and easy, and a good way to communicate ideas. What started out as something people did via e-mail and bookmark-sharing services like Delicious, is now moving to Facebook, Twitter, and other social broadcasting services. It is just so much more efficient to share a link once with all your friends and followers than to send it to each one individually.

Source: http://www.techcrunch.com/2009/04/06/are-url-shorteners-a-necessary-evil-or-just-evil/