20-CS-4003-001 Organization of Programming Languages Fall 2017
Data Structures

Lambda calculus, Type theory, Formal semantics, Program analysis

Big O, Hashing, Graphs, Priority Queues

Archive of entire page:
    datastructures.tar     Complete archive
 
Complexity:
    complexity.pdf     Average and worst case behavior, Big Oh
 
List:
Note: the code of this section is used by Stack, Hashing and Graphs below
    Makefile     Makefile for the following code
    funcs.h        Classes for display, value, compare, etc. on Lists
    a.h    a.cc     An object to be placed in a List
    node.h    node.cc     Nodes hold objects and pointers to next Nodes in the List
    list.h    list.cc     Operations on Lists
    listtest.cc        Test of the above code
 
Stack:
Note: the code of this section is used by Biconnected Components below
    Makefile     Makefile for the following code
    stacker.h    stacker.cc     Operations on Stacks
    stest.cc     Test if the above - compile with List code above
 
Hashing:
Note: the code of this section is used by Partition and Minimum Spanning Tree below
    hashing.pdf     Motivation for hashing, implementation of bucket hash
    Makefile     Makefile for the code of this section
    hashtable.h    hashtable.cc     Hashtable operations
    hash.cc     Test of the above code - compile with List code above
 
Partition:
Note: the code of this section is used by Minimum Spanning Tree below
    invtree.pdf     How to maintain a partition of vertices using inverted trees
    demo     How to maintain a partition of vertices separating connected components
    Makefile     Makefile for the code of this section
    partition.h    partition.cc     The Partition class
    parttest.cc     Test of the above code - compile with List and Hashtable code above
 
Priority Queue:
Note: the code of this section is used by Heapsort below
    heap.pdf     Description and example of a heap
    cell.h    cell.cc     Cell object used in binary tree implementation
    treeobject.h    treeobject.cc     Objects that go into the priority queue must have a value
    bintree.h    bintree.cc     Binary tree implementation
    heap.h    heap.cc     Priority queue implemented using above binary tree implementation
 
Graphs:
Note: the code of this section is used in the sections below
    graphs.pdf     What is a graph and what problems use a graph representation
    graphclass.pdf     What should a Graph class have to be most general
    edge.h    edge.cc     The Edge class
    vertex.h    vertex.cc     The Vertex class
    graph.h    graph.cc     The Graph class
 
Shortest Path:
    Makefile     Makefile for the code of this section
    path.h    path.cc     Path class
    short.h    short.cc     Short class - implements shortest path algorithm and contains problem description
    shortest.cc     Test of the above code - compile with List and Graph class code above
    short.006.dat     Sample data file
 
Biconnected Components:
    biconn.pdf     Description and example of finding biconnected components of a graph
    Makefile     Makefile for code of this section
    biconn.h    biconn.cc     Biconn class - implements biconnected components algorithm
    dfpair.h    dfpair.cc     DFPair class - vertex objects
    biconntest.cc     Test of the above code - compile with Stack, Graph, and List code above
    biconn.12.dat     Sample data file
 
3 color a graph:
    3color.pdf     Description and example of 3 coloring the vertices of a graph
    Makefile     Makefile for code of this section
    color.h    color.cc     Graph color algorithm
    colortest.cc     Test of the above code - compile with List and Graph code above
    3col005.dat     Data file
 
Minimum Spanning Tree:
    mst.pdf     Algorithm for the Minimum Spanning Tree problem
    demo     Minimum Spanning Tree problem
    Makefile     Makefile for the code in this section
    mst.h    mst.cc     Solution to minimum spanning tree problem
    msttest.cc     Test of above code - compile with List, Graph, Partition, and Hashtable code above
    mst.006.dat     Sample data file
 
Heapsort:
    Makefile     Makefile for code of this section
    bigint.h    bigint.cc     Operations on Big Integers
    heapsort.h    heapsort.cc     Heapsort implementation using above priority queue
    heaptest.h    heaptest.cc     Test of the above code - compile with Graph, List, and Priority Queue code above