Algorithm Introduce1-Basic Data Structure

Algorithm Introduce

What is a good Algorithm? (Cite from: Brian C. Dean )

  • Always terminates and produces correct output.
  • Make efficient use of computational resources. Minimizes running time, memory usage, processors, bandwidth, power consumed, heat produced.
  • Is simple to describe, understand, analyze, implement, and debug

For example: Linear search:

for (int i = 0; i<N; i++) {
	if (target == A[i]) {found it!}
}

Binary search:

low = 0; high = N-1;
while (low <= high) {
	mid = (low + high) / 2;
	if (target == A[mid]) { found it! }
	if (target > A[mid]) low = mid+1;
	else high = mid-1;
}

Linear search: O(N) time. Binary search: O(log N) time.


Running time

What is the Linear search: O(N) time. meaning in the above? We usually use asymptotic notation to describe how running time scales with input size.

O(f(N)) means “upper-bounded by a constant times f(N) as N grows large”. Just like, if the input of size is N, then the take about nN machine instructions, then we can say it runs in O(N) time.

There are other two symbol which are used for discribe the running time scales with input size.

  • Ω() provides an asymptotic lower bound.
  • Θ() means both a lower and upper bound.

Arrays, Listed lists

Arrays

After you define the size of the arrays, you can change the size of the array at the running time. You just can allocate for a new arrays at the running time and copy the old one to the new one.

/* Statically defined (size known at compile time) */
int A[100];
int B[100] = {1, 2, 3};
/* Dynamically allocated at run time */
int *C = (int *)malloc(100 * sizeof(int));
int *D = new int[100];
/* A[], C[], and D[] filled with garbage until initialized */
/* Remember pointers can be used as arrays -- e.g., C[7] */
/* Don’t forget to free memory for C and D... */
free (C);
delete [] D;

Analyze:

  • Retrieve or modify any element in O(1) time.
  • Insert or delete in middle of list: O(N) time.
  • Insert or delete from ends: O(1) time

Linked Lists

/* In C, typically
use “typedef struct...” */
struct Node {
    int payload;
    Node *next;
}
int list_length(Node *n)
{
    int count = 0;
    while (n != NULL) {
    count++;
    n = n->next;
}
    return count;
}

TODO:

  • Task1:Write the doubly linked lists.
  • Write a list which maintain a pointer to the first and last element.

Analyze:

  • Seek to any position in list: O(N) time.
  • Then insert or delete element: O(1) time.
  • Insert or delete from ends: O(1) time.

Circular Arrays, Queues

void enqueue(int x)
{
  A[front] = x;
  front = (front+1) % N;
}
int dequeue(void)
{
  int result = A[back];
  back = (back+1) % N;
  return result;
}

Stacks

void push(int x)
{
  A[top++] = x;
}
int pop(void)
{
  return A[--top];
}

void what_does_this_do(int n)
{
  if (n==0) return;
  printf (“%d\n”, n);
  what_does_this_do(n-1);
  printf (“%d\n”, n);
}

Arrays Vs Lists Example

We can use a example(From Brian. Dean) to introduce the running time abou the Arrays and Lists.

In the file studens.txt have a lot of students information about their name. Like this follow:

Sebastian Valentin
Jeffrey Wang
Jacob William
***

Question:

Write for me a program in C++ that takes as input a list of names, and prints out each name that appears in the list multiple times.

Arrays Solution:

#include <iostream>
#include <fstream>
using namespace std;

string *name;
int N; // how many elements we've actually read from the file
int allocated; // how much memory we've allocated

int num_occurences(string s)
{
  int count = 0;
  for (int i=0; i<N; i++) if (name[i] == s) count++;
  return count;
}

int main (void)
{
  string fname, lname;
  ifstream fin("students.txt");

  name = new string[4];
  allocated = 4;  // start with array of size 4
  // (this is somewhat arbitrary; any small constant would be fine)
  
  while (fin >> fname >> lname) {

    if (num_occurences(fname) == 1)  // O(n) time
      cout << fname << "\n";

    // Check if we need to transfer our array into a new larger array
    if (N == allocated) {
      string *newarray = new string[allocated * 2];
      for (int i=0; i<N; i++) newarray[i] = name[i];
      delete [] name; // old array not needed any more; free it...
      name = newarray;
      allocated = allocated * 2;
      // now name points to the new array, which is twice as big and
      // contains all the N elements we've read so far...
    }
    name[N++] = fname;
  }
  return 0;
}

List Solution

#include <iostream>
#include <fstream>
using namespace std;

struct Node {
  string name;
  Node *next;
  Node (string s, Node *n) { name = s; next = n; }
};

int num_occurences(Node *head, string s)
{
  int count = 0;
  Node *n = head;
  while (n != NULL) {
    if (n->name == s) count++;
    n = n->next;
  }
  return count;
}

int main (void)
{
  string fname, lname;
  ifstream fin("students.txt");
  Node *head = NULL;
  
  while (fin >> fname >> lname) {
    if (num_occurences(head, fname) == 1)  // O(n)
      cout << fname << "\n";
    head = new Node(fname, head);
  }
  return 0;
}
Terry Tang
Terry Tang
Software Development Engineer

My research interests include distributed robotics, mobile computing and programmable matter.

comments powered by Disqus