Thread: Computer Programming: General Concepts

  1. #1
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55

    Computer Programming: General Concepts

    Having delved into quite a few of the threads on here relative to what I am studying, I've encountered quite a few very interesting programming concepts that seem to be standard. My background is not comp sci and i'm mostly self taught, so I've only really studied language specific (learn to code in this language) literature. What I'm missing out on is the more general programming concepts which apply to all languages. Ex: I saw a post yesterday where someone brought up finite state machines as a design methodology for a particular problem. Very interesting but it was the first time I had ever heard of it!

    It would be great if you guys could recommend me some reading that would enlighten me on things like this (standard algorithmic approaches, sorting algorithms, design strategies, data structures etc.) I code in Java and more recently learning C so if the book had examples in either of these languages that would be great.

    Cheers!

    BIOS

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Data structures:
    Use arrays - There is nothing simpler, or faster, for most programs to use for data.
    Hardware loves integers, use them whenever you can. Use indexes (indices), not pointers, for array element accessing. Just as fast, twice as easy.

    Design:
    For trivial exercises, it isn't important. Try different approaches - go explore a bit.
    For bigger programs:
    I like Top Down methods: put off all the details you can, and get your functions decided according to what they do: input, output, computation, etc.

    Get the "backbone" of the program working, the logic flow the way you want it. Then go back, and fill in all the parts you left off, (Bottom Up), testing each block of code and function for general (not full) accuracy in results and syntax.

    Keep the final display for the user, until last (use just a primitive one until then). I've found I always have a better design for the user interface, if I design it last.

    Then final testing.

    Sorting:

    Small sets (less than 200 items): If run-time might be a concern, Insertion sort. It's faster than Quicksort for small sets of data, and KO's nearly all other algorithm's, easily.

    If run-time is not a concern, anything you like will be fine.

    Medium sized sets (200 to 10,000): I really like Shell sort - it's Insertion sort, with an extra loop to allow values that are out of order, to be moved a greater distance. Unfortunately, some "Shell sort's" on the web, are horrid re-works of Bubble sort.


    Large size sets (10,000 and up): Quicksort! Quicksort has so many ways it can be optimized, and although it uses some additional memory for it's recursive calls, it uses WAY less than Heap or (the faster) Merge sorts. One of the best ways is to let smaller sub arrays be passed over to Insertion sort, and get finished, there.

    Quicksort can be tripped up if you send it already sorted data, but it's like the patient who tells his doctor "it hurts when I move like this". Doc says "so don't move like that". If you know your data, this isn't a problem. If you don't, then that's your problem, in my opinion. You can optimize away a huge amount of this problem with handling sorted data, anyway.

    Absolutely the fastest integer "sorter" on the planet, is Counting sort, because it doesn't make any comparisons, or do any actual sorting - but it can produce a sorted list of data, if the data range of integers, is small. I see Wikipedia has a more complex version, which does move the data around. The version I learned did not move any data, just doing the first for loop in Wiki's version of Counting sort:

    Counting sort - Wikipedia, the free encyclopedia

    Special sorts:
    Long strings: Radix sort rocks on these, however Windows! is the string sorting champ, because it has dedicated resources that optimize it HUGELY. You can't believe how quick Windows is at sorting strings!

    Undisturbed:
    When you need to sort data, but also want to keep it in it's original order:
    Index or Pointer sort

    Multiple Sequential Data Sources:
    If you have multiple files already in sorted order, that need to be merged, Merge sort is unbeatable, naturally. (Except for using the aforementioned Windows)

    Minimal Swaps:
    Not good for anything else, but Selection sort guarantees the sorting will be done with the minimum number of swaps.

    Wikipedia has a HUGE number of programming topics you can read up on. YouTube has several on-line programming courses from well known universities. Lots of colleges also have websites devoted to a programming class. Lots of info out there!

    Finite state machines, etc., are all on Wiki. Here's a few of the sorting algorithms I mentioned above. The Bubble sort is an optimized version from our forum's iMalc, I believe:

    This is a program I'm re-doing from Turbo C. It has not been polished or tested much.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <limits.h>
    
    #define SIZE 50000
    #define InsertNum 50
    #define TestNum 10
    
    
    void bubbleSort(int a[], int);    
    int checkIt(int a[], int);
    void insertionSort(int a[], int lo, int hi);
    int loadData(int a[], int);
    void print(int [], int, int);
    void quickSort(int a[], int, int);
    void quickSortOpt(int a[], int, int);
    void shellSort(int a[], int);
    void substitutionSort(int a[], int);
    
    int main(void) {
       int *a, hi=0, OK, type=0;
       clock_t start, stop;
    
       a = malloc(SIZE * sizeof(int));
         
       printf("Array[SIZE] is %d, and INT_MAX is %d\n", SIZE, INT_MAX);
       hi = loadData(a, type);
       
       if(!hi) {
          printf("No data was loaded from the file\n");
          return 0;
       }
       OK = checkIt(a, hi);
       //getchar();
    
       printf("\n\t\tStart Sorting Test Run\n\t\t======================\n");
       printf(" Bubble Sort:             ");
       start = clock();
       bubbleSort(a, hi);
       stop = clock();
       printf("%7.3lf\n", (double) (stop-start)/CLOCKS_PER_SEC);
       if((OK = checkIt(a, hi)) == 0) {
          printf(" Sorting Error!\n");
          getchar();
          return 0;
       }
       hi = loadData(a, type);
       if(!hi)
         return 0;
       printf(" Insertion Sort:          ");
       start = clock();
       insertionSort(a, 0, hi);
       stop = clock();
       printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
       if((OK = checkIt(a, hi)) == 0) {
          printf(" Sorting Error!\n");
          getchar();
          return 0;
       }
    
       hi = loadData(a, type);
       if(!hi)
         return 0;
       printf(" Quicksort, Unoptimized:  ");
       start = clock();
       quickSort(a, 0, hi);
       stop = clock();
       printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
       if((OK = checkIt(a, hi)) == 0) {
          printf(" Sorting Error!\n");
          getchar(); 
          return 0;
       }
    
       hi = loadData(a, type);
       if(!hi)
         return 0;
       printf(" Quicksort, Optimized:    ");
       start = clock();
       quickSortOpt(a, 0, hi);
       stop = clock();
       printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
       if((OK = checkIt(a, hi)) == 0) {
          printf(" Sorting Error!\n");
          return 0;
       }
    
       hi = loadData(a, type);
       if(!hi)
         return 0;
       printf(" Shell Sort, Unoptimized: "); 
       start = clock();
       shellSort(a, hi);
       stop = clock();
       printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
       if((OK = checkIt(a, hi)) == 0) {
          printf(" Sorting Error!\n");
          return 0;
       }
    
       hi = loadData(a, type);
       if(!hi)
         return 0;
       printf(" Substitution Sort:       ");
       start = clock();
       substitutionSort(a, hi);
       stop = clock();
       printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
       if((OK = checkIt(a, hi)) == 0) {
          printf(" Sorting Error!\n");
          return 0;
       }
       free(a);
       putchar('\n'); 
       return 0;
    }
    void bubbleSort(int a[], int hi) {   
       int i, n, temp, swapped;
       n = hi;
       do {
          swapped = 0;
          for(i =0; i < n-1; i++) {  
             if(a[i] > a[i + 1 ]) {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp; 
                swapped = 1;
             }
          } //end for
          --n;
       }while(swapped);
    }
    int checkIt(int a[], int hi) {
    
       int i, count = 0, OK=1;
       static int first = 1;
       for(i=0;i<hi-1;i++) {
          if(a[i] > a[i+1]) {
             ++count;
             OK=0;
          }   
             
       }
       if(first) {
          printf(" %d numbers are out of order\n", count);
          first = 0;
          //getchar();
       }
       return OK;
    }
    
    void insertionSort(int a[], int lo, int hi) {
       int i, j, val; 
       
       for(i=lo+1;i<hi;i++) {  
          val = a[i];
          j = i-1;
          while(a[j] > val) {
             a[j + 1] = a[j];
             --j;
             if(j<0) break;
          }   
          a[j+1] = val;
       }  
       
       /*
       puts("\nAfter Insertion Sort:\n");
       for(i=lo;i<lo + 10;i++)
          printf(" %5d  ", a[i]);
       getchar();
       exit(0);
       */
    }
    int loadData(int a[], int type) {
       int i, OK;
       char buffer[100];
       if(type) {
          ;
       }else {
          srand(1);
          for(i=0;i<SIZE;i++) {
             a[i] = rand() % SIZE;
          }
       }
       return i;
    }
    void print(int a[], int lo, int hi) {
       int i;
       for(i=0;i<TestNum;i++) {
          printf(" %5d  ",a[i]);
       }
    }
     //Quicksort w/o a separate compare function :)
    void quickSort(int a[], int lo, int hi) {
       int i, j, pivot, temp;
    
       if(lo == hi) return; 
       i=lo; 
       j=hi;
       pivot= a[(lo+hi)/2]; 
    
       /* Split the array into two parts */
       do {    
          while (a[i] < pivot) i++; 
          while (a[j] > pivot) j--;
          if (i<=j) { //without the = in there, it's an endless loop
             temp= a[i];
             a[i]= a[j];
             a[j]=temp;
             i++;
             j--;
          }
       }while (i<=j);
        
       if (lo < j) quickSort(a, lo, j);
       if (i < hi) quickSort(a, i, hi);
    }
    //Optimzed Quicksort
    void quickSortOpt(int a[], int lo, int hi) {
      int i, j, pivot, temp;
      if(lo == hi) return; 
    
      if((hi - lo) < InsertNum) {
        insertionSort(a, lo, hi+1); 
        return;
      }
    
      i=lo; 
      j=hi;
      pivot= a[(lo+hi)/2]; 
    
      /* Split the array into two parts */
      do {    
        while (a[i] < pivot) i++; 
        while (a[j] > pivot) j--;
        if (i<=j) {  
            //swap(A, i, j);  
          temp= a[i];
          a[i]= a[j];
          a[j]=temp;
          ++i;
          --j;
        }
      } while(i<=j);
      
      if (lo < j) quickSortOpt(a, lo, j);
      if (i < hi) quickSortOpt(a, i, hi);
    }
    
    //Shell sort Brand new, not optimized
    void shellSort(int a[], int hi) {
      int i, j, gap, temp;
    
       for(gap = hi/2; gap > 0; gap /= 2) { //original Shell divisor
          for(i = gap; i < hi; i++) {
             temp = a[i];
             j = i;
             while(j>= gap && a[j-gap] > temp) {
                a[j] = a[j - gap];
                j = j - gap;
             }
             a[j] = temp;
          }
       }
    }
    
    //Substitution Sort:
    void substitutionSort(int a[], int hi) {
      int i, j, temp;
    
      for(i = 0; i < hi-1; i++)  {
        for(j = i + 1; j < hi; j++)  {
          if(a[i] > a[j]) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
          }
        }
      }
    }

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If you have the math for it, you could look at Robert Segewick's Algorythms book(s). The old versions are dirt cheap on Amazon (or wherever) now. Even if you find one of the ones that uses Pascal or something, the concepts should be the same. If you don't have the math for it, you'll just throw it in a corner. Or so I hear.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    @Adak wow thanks for the lengthy reply and sharing your wisdom. Much appreciated! Can you recommend some of your favourite comp sci books or particular ones you found useful in your learning? Also thanks for sharing code!

    @Quzah checked it out in the uni library today! There was an edition for both C and Java. They looked great though as you say they are quite technical. Alot of useful stuff in there though. I work on my maths on a weekly basis as I enjoy it, but could always do with some improvement! Please keep the recommendations coming. Any comp sci books you have found particularly helpful and which have improved you as a programmer.

    Thanks as always

    BIOS
    Last edited by BIOS; 09-14-2011 at 07:11 AM.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Segewick's books and The C Programming Language by Kernighan and Ritchie, are the only one's I've used lately. The others are obsolete or out of print by now.

    You can learn a ton of stuff from forum's like this and taking on programming projects that interest you, also. Some of the students assignments and programmers with real life problems are quite challenging and fun, too.

    Web sites like Project Euler, are terrific teasers, along with all the little puzzle and game sites. There's something for everyone: from Tic-Tac-Toe and Mastermind, to Chess and Rubik's Cube. Heck with playing or solving them yourself - make a program smart enough to do it! That was my firm conviction, after being introduced to Sudoku, for sure! You wouldn't believe the esoteric subtleties that human Sudoku players have to engage in to solve that "simple" one rule, game - unreal.

    You'll learn a ton, and if you like programming and problem solving challenges, have a lot of fun, as well.

  6. #6
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    Must agree about this forum! It's great! People are very knowledgeable and helpful. I've learned alot in the short time since I joined. + 1 on the programming projects. That's why i'm keen to learn more on design strategies because I don't really have any formal method or standard ways of dealing with certain types of computations. I just analyse the problem myself and code. I've picked up a few tricks but I'd like a more solid approach. That thread which featured finite state machines really opened my eyes in this respect.

  7. #7
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Yes there are a lot of really good and educational tutorials and examples floating around...

    But, don't underestimate the power of your own analytical thinking. You need to keep sharp on that since probably a third of your time on any given project is spent figuring out ways to get stuff done. Another third is spent looking stuff up... the rest is time at the keyboard.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. General Computer Question
    By maththeorylvr in forum Tech Board
    Replies: 3
    Last Post: 04-29-2005, 03:38 PM
  2. General question about C++ Programming/Computer Science
    By learning C++ in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-05-2004, 10:18 PM
  3. Programming concepts
    By lyx in forum C++ Programming
    Replies: 2
    Last Post: 12-03-2003, 12:37 AM
  4. Independent & Effeciency :: Programming Concepts
    By kuphryn in forum C++ Programming
    Replies: 5
    Last Post: 06-08-2002, 05:08 AM
  5. Basic 2d Programming Concepts
    By JoshG in forum Game Programming
    Replies: 4
    Last Post: 05-17-2002, 05:54 AM