Algorithms

Impress your job interviewer during whiteboarding exams! Learn the proper way of solving problems and algorithms implementation.


Singly Linked List Using Arrays

My Singly Linked List Article is a direct implementation of Singly Linked List, where the memory allocation of more Nodes is done only when necessary. However, in reality, the computer memory is a contiguous array of memory locations. We can emulate the memory management of a Singly Linked List using Arrays.

Linked List

Linked List is a set of Nodes where a Node is a data and a reference to the next node. The reference to the next node is an item required in the structure of a Linked List because it's not organized sequentially in memory like the Array, although it can also be represented using Arrays as you will see in our implementation of Singly List.

Accessing an element:

Singly Linked List

Singly Linked List is the most basic of Linked List implementations. It's a one-way list of Nodes from Head to Tail! 

To implement a Singly Linked List, we must first create a Node structure (or a class) that will hold the data and the node reference to the next Node.

In C++ we do this by declaring the following SL_Node structure. We will be using templates so we can handle different kinds of data in one single program.

How to Draw a Circle (Midpoint and Bresenham's Algorithm)

With trigonometry functions such as sine and cosine, it is very easy to compute for the value of x and y for any given radius and teta.

We've all learned this from highschool and college class and it will not be tacked in this article. However, drawing a circle using these functions requires the usage of floating-point numbers which is slow, not to mention the typecasting from floating-point to integers as plotting a pixel requires such datatype.

How to Draw a Line (Bresenham's Algorithm)

The line equation represented by y = mx + b, is one of the most basic formulas in plotting a line. Where m represents the slope, x represents the value in horizontal coordinate and b represents the offset from y.

Suppose we have a line segment (x1, y1) to (x2, y2), the slope can be easily computed as (y2 - y1) / (x2 - x1) or to understand it better, we can read it as an increment in y for every step in x.

How to Represent Float Increments as Integer

If you've always hated incrementing (or decrementing) float variables by some constant float within the range of -1 0 1, and increment 0, and wanted to implement a better approach by using integral data types (such as char, short, int, and long), then this article best describes the solution to your ordeal. Applications of this optimization vary from different fields of computer programming. One of which is Bersenham's Algorithm for drawing a line.

How to Implement the Paint Fill

Emulating paint fill is easy and can be done either iteratively or thru stacks. This demonstration is done using plain text, but the same idea could be implemented using your favorite graphics framework.

First, we're given a two-dimensional array of canvass of type char with size [N][M], where N is the number of rows and M is the number of columns.

Let's suppose N = 11 and M = 15, but of course, the values of these two may vary.

How to Find the Sum of 1 to 100, and Its Variants

Legend has it that the German Mathematician, Carl Friedrich Gauss, who was an elementary student during the late 1700s, showed his teacher how quickly he summed up the numbers 1 to 100 by using a simple mathematical trick.

Centuries later, most programmers are still doing it the long way!

What is Brute Force Modeling?

Brute Force Modeling is a technique used to solve problems by tabulating results in hopes of finding a pattern by induction. The pattern or formula is then normally used as the basis for solving the problem thru iteration or recursion.

Let's take the Josephus Problem, where he (Josephus) and 40 other soldiers decided to choose mass suicide over capture by arranging themselves in a circle and killing the kth person in the circle. The problem of Josephus is where to sit in the circle such that he is the last to die (or escape).

Lattice Paths Part 3 (Combinations)

Starting in the top left corner of a 2 x 2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20 x 20 grid, or any N x N grid?

--

This is the last of the three-part series article about explaining how you could have arrived at the solution yourself in solving the Lattice Paths Problem. If you haven't tried it yet, do it first. I do not intend to deny you of your epiphany moment!

Note: All implementations are written in C/C++.

--

Pages