CSUB Computer Science - Michael Sarr

What is an algorithm


Algorithms work by following a set of instructions or rules to complete a task or solve a problem. They can be expressed as natural languages, programming languages, pseudocode,  flowcharts and control tables. Natural language expressions are rare, as they are more ambiguous. Programming languages are normally used for expressing algorithms executed by a  computer.


some examples might be

search an array to find a particular value

search an array to find the number of occourances of a specific value

encrypt a set of data

decrypt a set of data







lets look at a very simple algorithm coded in C++ to find the position of a value within an array

File: search.cpp 

template<class T>
int Search(T* source,int source_size,T searching_for)
{
for(int loop=0;loop<size;loop++)
    if (source[loop] == searching_for)
        return loop; // we found it return the index where it was found
    return -1; // we didnt find it so return -1 to indicate it was not found
}








or lets say we have a graphics area of 320x240 pixels like so  and we want to draw a line from 12,12 to 110,156



to accomplish this we need to color in each individual pixel in the display to create a line

as you can see here it is not an exactly a staight line, but many distinct pixels


lets look at what pixels we need to fill in to create the line
File: pixels.txt 

setting the color in the pixel at 12,12 to 1 
setting the color in the pixel at 13,13 to 1 
setting the color in the pixel at 13,14 to 1 
setting the color in the pixel at 14,15 to 1 
setting the color in the pixel at 15,16 to 1 
setting the color in the pixel at 15,17 to 1 
setting the color in the pixel at 16,18 to 1 
setting the color in the pixel at 17,19 to 1 
setting the color in the pixel at 17,20 to 1 
setting the color in the pixel at 18,21 to 1 
setting the color in the pixel at 19,22 to 1 
setting the color in the pixel at 19,23 to 1 
setting the color in the pixel at 20,24 to 1 
setting the color in the pixel at 21,25 to 1 
setting the color in the pixel at 22,26 to 1 
setting the color in the pixel at 22,27 to 1 
setting the color in the pixel at 23,28 to 1 
setting the color in the pixel at 24,29 to 1 
setting the color in the pixel at 24,30 to 1 
setting the color in the pixel at 25,31 to 1 
setting the color in the pixel at 26,32 to 1 
setting the color in the pixel at 26,33 to 1 
setting the color in the pixel at 27,34 to 1 
setting the color in the pixel at 28,35 to 1 
setting the color in the pixel at 28,36 to 1 
setting the color in the pixel at 29,37 to 1 
setting the color in the pixel at 30,38 to 1 
setting the color in the pixel at 30,39 to 1 
setting the color in the pixel at 31,40 to 1 
setting the color in the pixel at 32,41 to 1 
setting the color in the pixel at 32,42 to 1 
setting the color in the pixel at 33,43 to 1 
setting the color in the pixel at 34,44 to 1 
setting the color in the pixel at 34,45 to 1 
setting the color in the pixel at 35,46 to 1 
setting the color in the pixel at 36,47 to 1 
setting the color in the pixel at 37,48 to 1 
setting the color in the pixel at 37,49 to 1 
setting the color in the pixel at 38,50 to 1 
setting the color in the pixel at 39,51 to 1 
setting the color in the pixel at 39,52 to 1 
setting the color in the pixel at 40,53 to 1 
setting the color in the pixel at 41,54 to 1 
setting the color in the pixel at 41,55 to 1 
setting the color in the pixel at 42,56 to 1 
setting the color in the pixel at 43,57 to 1 
setting the color in the pixel at 43,58 to 1 
setting the color in the pixel at 44,59 to 1 
setting the color in the pixel at 45,60 to 1 
setting the color in the pixel at 45,61 to 1 
setting the color in the pixel at 46,62 to 1 
setting the color in the pixel at 47,63 to 1 
setting the color in the pixel at 47,64 to 1 
setting the color in the pixel at 48,65 to 1 
setting the color in the pixel at 49,66 to 1 
setting the color in the pixel at 49,67 to 1 
setting the color in the pixel at 50,68 to 1 
setting the color in the pixel at 51,69 to 1 
setting the color in the pixel at 51,70 to 1 
setting the color in the pixel at 52,71 to 1 
setting the color in the pixel at 53,72 to 1 
setting the color in the pixel at 54,73 to 1 
setting the color in the pixel at 54,74 to 1 
setting the color in the pixel at 55,75 to 1 
setting the color in the pixel at 56,76 to 1 
setting the color in the pixel at 56,77 to 1 
setting the color in the pixel at 57,78 to 1 
setting the color in the pixel at 58,79 to 1 
setting the color in the pixel at 58,80 to 1 
setting the color in the pixel at 59,81 to 1 
setting the color in the pixel at 60,82 to 1 
setting the color in the pixel at 60,83 to 1 
setting the color in the pixel at 61,84 to 1 
setting the color in the pixel at 62,85 to 1 
setting the color in the pixel at 62,86 to 1 
setting the color in the pixel at 63,87 to 1 
setting the color in the pixel at 64,88 to 1 
setting the color in the pixel at 64,89 to 1 
setting the color in the pixel at 65,90 to 1 
setting the color in the pixel at 66,91 to 1 
setting the color in the pixel at 66,92 to 1 
setting the color in the pixel at 67,93 to 1 
setting the color in the pixel at 68,94 to 1 
setting the color in the pixel at 68,95 to 1 
setting the color in the pixel at 69,96 to 1 
setting the color in the pixel at 70,97 to 1 
setting the color in the pixel at 71,98 to 1 
setting the color in the pixel at 71,99 to 1 
setting the color in the pixel at 72,100 to 1 
setting the color in the pixel at 73,101 to 1 
setting the color in the pixel at 73,102 to 1 
setting the color in the pixel at 74,103 to 1 
setting the color in the pixel at 75,104 to 1 
setting the color in the pixel at 75,105 to 1 
setting the color in the pixel at 76,106 to 1 
setting the color in the pixel at 77,107 to 1 
setting the color in the pixel at 77,108 to 1 
setting the color in the pixel at 78,109 to 1 
setting the color in the pixel at 79,110 to 1 
setting the color in the pixel at 79,111 to 1 
setting the color in the pixel at 80,112 to 1 
setting the color in the pixel at 81,113 to 1 
setting the color in the pixel at 81,114 to 1 
setting the color in the pixel at 82,115 to 1 
setting the color in the pixel at 83,116 to 1 
setting the color in the pixel at 83,117 to 1 
setting the color in the pixel at 84,118 to 1 
setting the color in the pixel at 85,119 to 1 
setting the color in the pixel at 86,120 to 1 
setting the color in the pixel at 86,121 to 1 
setting the color in the pixel at 87,122 to 1 
setting the color in the pixel at 88,123 to 1 
setting the color in the pixel at 88,124 to 1 
setting the color in the pixel at 89,125 to 1 
setting the color in the pixel at 90,126 to 1 
setting the color in the pixel at 90,127 to 1 
setting the color in the pixel at 91,128 to 1 
setting the color in the pixel at 92,129 to 1 
setting the color in the pixel at 92,130 to 1 
setting the color in the pixel at 93,131 to 1 
setting the color in the pixel at 94,132 to 1 
setting the color in the pixel at 94,133 to 1 
setting the color in the pixel at 95,134 to 1 
setting the color in the pixel at 96,135 to 1 
setting the color in the pixel at 96,136 to 1 
setting the color in the pixel at 97,137 to 1 
setting the color in the pixel at 98,138 to 1 
setting the color in the pixel at 98,139 to 1 
setting the color in the pixel at 99,140 to 1 
setting the color in the pixel at 100,141 to 1 
setting the color in the pixel at 100,142 to 1 
setting the color in the pixel at 101,143 to 1 
setting the color in the pixel at 102,144 to 1 
setting the color in the pixel at 103,145 to 1 
setting the color in the pixel at 103,146 to 1 
setting the color in the pixel at 104,147 to 1 
setting the color in the pixel at 105,148 to 1 
setting the color in the pixel at 105,149 to 1 
setting the color in the pixel at 106,150 to 1 
setting the color in the pixel at 107,151 to 1 
setting the color in the pixel at 107,152 to 1 
setting the color in the pixel at 108,153 to 1 
setting the color in the pixel at 109,154 to 1 
setting the color in the pixel at 109,155 to 1 
setting the color in the pixel at 110,156 to 1 






thats a lot of points 

how do we figure them out... use an algorithm

Bresenham Line Algorithm

File: bresenham.cpp 


#include "cmpslib19.h"  // general purpose functions for use in this class










void setPixel(int16_t x, int16_t y, uint8_t color) 
{
printf("setting the color in the pixel at %d,%d to %d \n",x,y, color);

/*
we are not acutally going to plot a point but here is an example
STARTING_ADDRESS is pointer to the start of screen memory
WIDTH  the number of pixels of the screen
this is for a 16 color (4 bit) 320x240 screen


   ADDR = STARTING_ADDRESS + (x / 2) + (y * (WIDTH / 2));
    if (x%2)
      {
      ADDR &= (15);
      ADDR |= (color << 4);
      }
    else
      {
      ADDR &= 240;
      ADDR |= (color);
      }  
*/
}





void plot_line(int16_t x0, int16_t y0, int16_t  x1, int16_t y1,uint8_t color)
{
  int16_t dx =  abs (x1 - x0);
  int16_t sx = x0 < x1 ? 1 : -1;
  int16_t dy = -abs (y1 - y0);
  int16_t sy = y0 < y1 ? 1 : -1; 
  int16_t err = dx + dy;
 
  while (true)
	{
    setPixel(x0,y0,color);
    if (x0 == x1 && y0 == y1) 
		break;
    int16_t  e2 = 2 * err;
    if (e2 >= dy) 
		{
		if (x0 == x1)
			break;
		err += dy; 
		x0 += sx; 
		}
    if (e2 <= dx) 
		{ 

		if (y0 == y1)
			break;
		err += dx; 
		y0 += sy; 
		} 
	}
}// end plot_line



int main()
  {
plot_line(12,12,110,156,1);



  return 0;
  }