DOC PREVIEW
DREXEL CS 265 - Algorithms and Data Structures

This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Algorithms and Data Structures*• Objective: To review the fundamental algorithms and data structures that are commonly used in programs. To see how to use and implement these algorithms and data structures in different languages and to see what language and library support exists for them.– Sorting and Searching– Arrays and Vectors– Lists–Hash Tables– Generic programming*This material comes from chapter 2 ofBrian Kernighan and Rob Pike,The Practice of ProgrammingTopics• Binary Search•Quicksort•Big “Oh”• Vectors• Lists• Hash Tables• C, C++, Java, PerlLinear Searchtypdef struct Nameval Nameval;struct Nameval {char *name;int value;}/* HTML characters, e.g. AElig is a ligature of A and E. *//* values are Unicode/ISO10646 encoding. */Nameval htmlchars[] = {“Aelig”, 0x00c6,“Aacute”, 0x00c1,“Acirc”, 0x00c2,/* … */“zeta”, 0x03b6};Linear Search/* lookup: sequential search for name in tab; return index */int lookup(char *name, Nameval tab[], int ntab){int i;for (i = 0; i < ntab; i++)if (strcmp(name, tab[i].name) == 0)return i;return –1; /* no match */}Binary Search/* lookup: binary search for name in tab; return index or –1 if not found. */int lookup(char *name, Nameval tab[], int ntab){int low, high, mid, cmp;low = 0;high = ntab – 1;while (low <= hight) {mid = (low + high)/2;cmp = strcmp(name, tab[mid].name);if (cmp < 0)high = mid – 1;else if (cmp > 0)low = mid + 1;else /* found match */return mid;}return –1; /* no match */}Quicksort• pick one element of the array (pivot)• partition the other elements into two groups– those less than the pivot– those that are greater than or equal to the pivot• recursively sort each groupPartitionunexaminedplast i n-1unexamined< pp >= p0 1 last i n-1< p p >= p0last n-1Quicksort/* quicksort: sort v[0]..v[n-1] into increasing order. */void quicksort(int v[], int n){int i, last;if (n <= 1) /* nothing to do */return;swap(v, 0, rand()%n); /* move pivot element to v[0] */last = 0;for (i = 1; i < n; i++) /* partition */if (v[i] < v[0])swap(v, ++last, i);swap(v, 0, last); /* restore pivot */quicksort(v, last); /* recursively sort each part. */quicksort(v+last+1, n-last-1);}Swap/* swap: interchange v[i] and v[j]. */void swap(int v[], int i, int j){int temp;temp = v[i];v[i] = v[j];v[j] = temp;}Libraries• C: qsort• C++: sort (algorithm library from STL)• java.util.collections.sort• perl: sortqsort (strings)char *str[N];qsort(str, N, sizeof(str[0]), scmp);/* scmp: string compare of *p1 and *p2 */int scmp(const void *p1, const void *p2){char *v1, *v2;v1 = *((char**) p1);v2 = *((char**) p2);return strcmp(v1, v2);}qsort (int)int arr[N];qsort(arr, N, sizeof(arr[0]), icmp);/* icmp: integer compare of *p1 and *p2 */int icmp(const void *p1, const void *p2){int v1, v2;v1 = *((int*) p1);v2 = *((int*) p2);if (v1 < v2)return –1;else if (v1 == v2)return 0;elsereturn 1;}Big “Oh”set partitioningexponentialO(2n)matrix multiplicationcubicO(n3)insertion sortquadraticO(n2)quicksort/mergesortn log nO(nlog n)string comparisonlinearO(n)binary searchlogarithmicO(log n)array indexconstantO(1)ExampleNameNotation*It is more precise to use Θ for order classesTiming• Unix time command– [jjohnson@ws56 lec1]$ time sign < /usr/share/dict/words | sort | squash > temptime– 0.11user 0.01system 0:00.27elapsed 43%CPU (0avgtext+0avgdata 0maxresident)k– 0inputs+0outputs (91major+13minor)pagefaults 0swaps•clock()• counting cyclesnlog n vs. n2Growing Arrays• Arrays provide O(1) access and insertion time• Sorted arrays provide O(log n) search time and O(n) insertion time [have to move elements]• If the number of elements in an array is not known ahead of time it may be necessary to resize the array.• Involves dynamic memory allocation and copying• To minimize the cost it is best to resize in chunksGrowing Arrays in Ctypedef struct Nameval Nameval;struct Nameval {char *name;int value;};struct NVtab {int nval; /* current number of values */int max; /* allocated number of values */Nameval *nameval; /* array of name-value pairs */};enum { NVINIT = 1, NVGROW = 2 };Growing Arrays/* addname: add new name and value to nvtab */int addname(Nameval newname){Nameval *nvp;if (nvtab.nameval == NULL) { /* first time */nvtab.nameval = (Nameval *) malloc(NVINIT * sizeof(Nameval));if (nvtab.nameval == NULL)return –1;nvtab.max = NVINIT;nvtab.nval = 0;} else if (nvtab.nval >= nvtab.max) { /* grow */nvp = (Nameval *) realloc(nvtab.nameval, (NVGROW*nvtab.max)*sizeof(Nameval));if (nvp == NULL)return –1;nvtab.max *= NVGROW;nvtab.nameval = nvp;}nvtab.nameval[nvtab.nval] = newname;return nvtab.nval++;}Lists• A sequence of elements• Space is allocate for each new element and consecutive elements are linked together with a pointer.• O(1) time to insert at front, O(n) to append unless pointer to last element kept, O(n) traversal time.data 1 data 2 data 3NULLdata 4headLists in Ctypedef struct Nameval Nameval;struct Nameval {char *name;int value;Nameval *next; /* in list */};/* newitem: create new item from name and value */Nameval *newitem(char *name, int value){Nameval *newp;newp = (Nameval *) emalloc(sizeof(Nameval));newp->name = name;newp->value = value;newp->next = NULL;return newp;}Lists in C/* addfront: add newp to front of listp */Nameval *addfront(Nameval *listp, Nameval *newp){newp->next=listp;return newp;}nvlist = addfront(nvlist, newitem(“smiley”, 0x263A));Append Element to Back of List/* addend: add newp to end of listp */Nameval *addend(Nameval *listp, Nameval *newp){Nameval *p;if (listp == NULL)return newp;for (p = listp; p->next != NULL; p = p->next);p->next = newp;return listp;}Lookup Element in List/* lookup: sequential search for name in listp */Nameval *lookup(Nameval *listp, char *name){for ( ; listp != NULL; listp = listp->next)if strcmp(name, listp->name) == 0)return listp;return NULL; /* no match */}Apply Function to Elements in List/* apply: execute fn for each element of listp */void apply(Nameval *listp, void (*fn)(Nameval*, void*) , void *arg){for ( ; listp != NULL; listp = listp->next)(*fn)(listp, arg); /* call the function */}void (*fn)(Nameval*, void*) is a pointer to a void function of two arguments – the first argument is a pointer to a Nameval and the second is a generic pointer.Print Elements of a List/* printnv: print name and value using


View Full Document

DREXEL CS 265 - Algorithms and Data Structures

Download Algorithms and Data Structures
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Algorithms and Data Structures and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Algorithms and Data Structures 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?