20-ECES-228-001

Data Structures

Stacks, Queues, Dequeues, Trees (RedBlack, AVL, B, Heaps, more...), Graphs, Efficiency

News
    Welcome    21 Sep 07
    Sample Makefile    27 Sep 07
    SAT Solver Output Interpreter    27 Sep 07
    Hiding bad software    30 Sep 07
    Alternative Mergesort - subclass the BinTree class    11 Oct 07

Quote(s) of the Week

    red node,
    black node,
    sittin in a tree,
    it's arranged in
    bi - nar - y

    insert a node,
    rotate the tree,
    nothing beats
    log(N) complexity!

    ---submitted by Jon Nafziger (from Google)

Extras:  Pi    Roman Number Adder    Folds    E-less numbers    Lemmings    Lock    Word Puzzle    Encryption

2007 Syllabus:  HTML        Bloom's Taxonomy:  Aim of program

C++ Tutorial:  HTML        Unix Tutorial:  HTML

Past Midterm Exams
   
2006-002     2006-001     2005     2004

2007 Midterm Exam Results
   Section 001:    results     solutions

Homework Assignments
    Homework Number 1 (C++) - Sudoku Solver
    Homework Number 2 (C++) - Positive Integer Powers and Stacks
    Homework Number 3 (C++) - MergeSort Can Be Faster With Linked Lists!
    Homework Number 4 (C++) - Hamming's Problem and Priority Queues     demonstration
    Homework Number 5 (C++) - HashTable Class
    Homework Number 6 (C++) - Union-Find and the Partition Class
    Homework Number 7 (C++) - Using the Partition Class
    or
    Homework Number 7 (C++) - Minimum Cost Network with Graph and Partition Classes
       Check this demo out: demo

Homework Grades
    HW 1 - Sent individually - 4@10, 1@9.5, 1@9, 3@8.5, 2@8, 1@7.5, 2@6, 2@4, 3@3, 1@1
    HW 2 - Sent individually - 6@10, 4@9.5, 3@9, 1@8.5, 1@7.5, 1@7, 1@6.5, 1@3
    HW 3 - Sent individually - 8@10, 1@9, 1@8, 1@6, 3@4, 1@3 (still waiting for some)
    HW 4 - Sent individually - 11@10, 2@9, 1@8, 1@5 (maybe another will come?)
    HW 5 - Sent individually - 12@10, 1@9.5, 1@9, 1@7, (expecting one more)
    HW 6
    HW 7

Homework Hints
    Homework Number One
    Homework Number Two

Solutions to the Homework
   
Homework Number 1:
          C++:     Makefile.1a     hw1a.cc
          Java:     hw1a.java
          C++:     Makefile.1b     hw1b.cc
          Java:     hw1b.java
   
Homework Number 2:
          C++:     Makefile.2a     hw2a.cc     pqueue.h     pqueue.cc     pqext.h     pqext.cc     funcs.h
          Java:     hw2a.java     pqueue.java     pqext.java     funcs.java     intobject.java
          C++:     Makefile.2b     hw2b.cc     stacker.h     stacker.cc     node.h     node.cc     bigint.h     bigint.cc     power.h     power.cc     funcs.h
          Java:     hw2b.java     cell.java     stack.java     funcs.java     power.java     intobject.java
   
Homework Number 3:
          C++:     Makefile.3     hw3.cc     mcell.h     mcell.cc     mrgsrt.h     mrgsrt.cc     funcs.h
              uses bintree class:    Makefile     mergesort.cc     cell.h     cell.cc     bintree.h     bintree.cc     mrgsrt.h     mrgsrt.cc
          Java:     hw3.java     mcell.java     funcs.java     mrgsrt.java
   
Homework Number 4:
          C++:     Makefile.4     hw4.cc     pqueue.h     pqueue.cc     funcs.h
          Java:     hw4.java     pqueue.java     funcs.java
   
Homework Number 5:
          C++:     Makefile.5     hw5.cc     node.h     node.cc     list.h     list.cc     hashtable.h     hashtable.cc     funcs.h     a.h     a.cc
          Java:     hw5.java     cell.java     funcs.java     list.java     hashtable.java     a.java
   
Homework Number 6:
          C++:     Makefile.6     hw6.cc     node.h     node.cc     list.h     list.cc     hashtable.h     hashtable.cc     paritition.h     partition.cc     funcs.h
          Java:     hw6.java     cell.java     funcs.java     list.java     hashtable.java     node.java     partition.java     a.java
   
Homework Number 7:
          C++:     Makefile.7     hw7.cc     node.h     node.cc     list.h     list.cc     pqueue.h     pqueue.cc     hashtable.h     hashtable.cc     partition.h     partition.cc     supervisor.h     supervisor.cc     cable.h     cable.cc     city.h     city.cc     funcs.h
          Java:     hw7.java     cell.java     funcs.java     list.java     hashtable.java     node.java     partition.java     valuecity.java
city.java     cable.java     queue.java     mst.java
   
Homework Number 7 - Solution using the Graph, Edge, Vertex classes:
          C++:     Makefile.7a     hw7a.cc     node.h     node.cc     list.h     list.cc     hashtable.h     hashtable.cc     partition.h     partition.cc     graph.h     graph.cc     edge.h     edge.cc     vertex.h     vertex.cc     mst.cc     funcs.h

What's Wrong With This Code?
    Must dereference a pointer to an array before indexing the array
    Dereference pointers to objects which do not exist?

Questions
    Any topic

Lecture Notes
    Topic Section 001
    Modelling Sudoku in logic       25 Sep
    Commandline Input   
         sudoku.cc     For backtracking Sudoku solver 25 Sep
         simple.cc     Convert argument to number ?? Sep
         interp.cc      Argument as switch ?? Sep
         xlate.cc        Convert bit pattern to character ?? Sep
    Reading Files   
         sudoku.cc     For Sudoku solvers 25 Sep
         openfile.cc     Open a file, test for existence ?? Sep
         readfile.cc      Sample use of seekg, tellg, read, write ?? Sep
         readcities.cc   Read cities from file ?? Sep
         readcables.cc  Read cables from file and store internally ?? Sep
    Linked Lists and Stacks    ?? Sep
    Exponentiation    02 Oct
    Queue   
         queue.1.cc     queue.1.h     Use of Queue class     Makefile ?? Oct
         Demonstration     ?? Oct
    Complexity (Big O)    02 Oct
    Priority Queue    
         C++ Source Code    09 Oct
         Demonstration 09 Oct
    Sorting   
        Insertion Sort    
             insertsort.cc     04 Oct
        QuickSort    
             quicksort.cc     04 Oct
             Demonstration 1 04 Oct
             Demonstration 2 04 Oct
             Alternative partition 04 Oct
        MergeSort    
             mergesort.cc    09 Oct
             Demonstration 09 Oct
        RadixSort    
             radix.cc     queue.cc     queue.h     Makefile     09 Oct
             Demonstration 09 Oct
        ShellSort    
             shellsort.cc     pqueue.cc     pqueue.h     Makefile     18 Oct
             Demonstration 18 Oct
        Topological Sort    
             topo.cc    (simple implementation) 09 Oct
             topo.cc     solver.cc     solver.h     Makefile     node.h    (no ifs)    09 Oct
                visit.cc     visit.h     cycle.h     topo.h     node.cc     09 Oct
                cell.h     neighbor.cc     neighbor.h     exec.h     09 Oct
                Explain if-less topological sort
             topo.10000.dat    (10000 object data file) 09 Oct
             Demonstration 09 Oct
             How to build a topological sort ?? Oct
    Trees        
        Binary Trees    
             create.cc     bintree.cc     bintree.h     11 Oct
             Search Demonstration 11 Oct
        Inverted Trees    
             unionfind.cc     ?? Oct
             Demonstration     ?? Oct
        General Trees    
             gtree.cc     generaltree.cc     generaltree.h     list.cc     list.h     ?? Oct
             cell.cc     cell.h     Makefile     ?? Oct
             Demonstration ?? Oct
        Binary Search Trees    
             create.cc     bintree.cc     bintree.h     cell.cc     cell.h     ?? Oct
             bigint.cc     bigint.h     Makefile     ?? Oct
             Demonstration ?? Oct
    Hashing   
        Hash Functions and Sizing    
             Demonstration     ?? Nov
    Graphs   
        Definitions and Examples    
             Starting Point     ?? Nov
             Building Code     ?? Nov
                edge.h     edge.cc     vertex.h     vertex.cc     graph.h     graph.cc     ?? Nov
                node.h     node.cc     list.h     list.cc     funcs.h ?? Nov
             3 Colorability     ?? Nov
                colortest.cc     color.h     color.cc     Makefile ?? Nov
                3color.005.dat     example graph     ?? Nov
             Biconnected Components     ?? Nov
                biconntest.cc     biconn.h     biconn.cc     Makefile ?? Nov
                dfpair.h     dfpair.cc     stacker.h     stacker.cc ?? Nov
                biconn.12.dat     example graph     Algorithm     ?? Nov
             Minimum Cost Network     ?? Nov
                msttest.cc     mst.h     mst.cc     list_funcs_mst.cc ?? Nov
                hashtable.h     hashtable.cc     partition.h     partition.cc ?? Nov
                hash_funcs.h     hash_funcs_mst.cc ?? Nov
                mst006.dat     example graph     ?? Nov
             Shortest Path     ?? Nov
                shortest.cc     short.h     short.cc     Makefile     ?? Nov
                cell.h     cell.cc     heap.h     heap.cc     bintree.h     bintree.cc     ?? Nov
                path.h     path.cc     treeobject.h     treeobject.cc     ?? Nov
                short.006.dat     ?? Nov
    BTrees   
        Insertion/Deletion Examples    
             Demonstration     ?? Nov
             Makefile     btreetest.cc     btree.h     btree.cc     node.h     node.cc     ?? Nov
    Ficonacci Heaps   
        Insertion/Deletion Examples    
             Demonstration     Applet ?? Nov
    Balanced Binary Trees   
        Tree Rotation Demonstration  - the fundamental operation ?? Nov
        Red-Black Trees    
             Insert/Remove Graphical Demonstration     ?? Nov
        AVL Trees    
             Insert/Remove Demonstration     ?? Nov
        Splay Trees   (non-balancing)
             Insert/Remove Demonstration     ?? Nov
    Matroids and Greedy Methods ?? Nov
         Demonstration    
         Example: Integer Deadline Scheduling    
         Integer Deadline Scheduling Implementation    
    Sudoku Puzzle Solution Using Logic Constraints ?? Nov
        Variable setup    
        Constraint setup    
        Sample resulting CNF file    
        interp.cc - interpret output of SAT solver    
        input.cc - translate input to standard CNF format    
        sudoku.cnf - needed by above    
        sudoku.4.inp - sample Sudoku problem input    
        solve - unix script for running all of above - needs sbsat SAT solver    
    Integer Array and Stack, Find Redundancy in a Network       ?? Sep

Secure Shell for Helios
    You can log into helios using ssh only. Set it up like
this
    Get files for freeware DOS/Windows version here (get putty.exe and psftp.exe).

C++ to Java
    Slides (postscript only - use ghostview to see it)
    LaTeX source for the above slides - compile with LaTeX

Red Black Trees
    Java demonstration
    Source code

Example Java Code
    Radix Sort using circular queue
    QuickSort
    Hamming's problem extended
    Redundancy Check in a network
    Binary Trees, Heaps, and Heapsort
    Insurance Company Payroll (no muss, no fuss)

Example C++ code
    A string class
    A date class
    Stacks using arrays
    Stacks using linked lists
    Finding redundancy in a network
    Finding redundancy in a network (a better solution)
    Finding redundancy in a network: recursive solution
    Finding redundancy in a network: using circular queue
    Merge two queues
    Radix Sort using circular queue
    Binary Tree and HeapSort (fixed 11/1/96)
    Bucket Hashing - (non-adjusting table size)

Example C code
    Stacks using arrays
    Stacks using linked lists
    Sorting elements of a nxn array using qsort
    Another array sort using qsort - not for the timid