CScD 300 — Data Structures
Term Overview

Quick overview of software engineering
Linked Lists  Linked list code from 2010 March 11 class
   Review / FAST introduction
   dummy head node
   doubly-linked list
   circular list
   sorting:  addOrdered/insertSort, selectionSort, mergeSort
Algorithm Analysis and Recursion   AdditiveSquares.java  [txt]  Simple recursion for review
   Use list insert sort and merge sort
   Array binary search
   Optimization of array insert sort through use of
   binary search and arraycopy
Simple binary trees
   Expression trees
   Recursive traversal (pre-, in-, post-fix)
Exam I
Stacks
   Postfix expression evaluation
   RPNdrill.exe   Drill on evaluation of an RPN expression (operators and integers)
   Infix expression parsing
   DemoXlate.jar  Executable jar to demonstrate parsing of parenthesized infix expression.
   DemoXlate.exe  Above jar in an exe wrapper 
   DemoXlate.exe  Alternate version (in C) that allows keyboard input
   Possible input expression:  4.2 - ( 100 - ( Exam1 * 0.15 + Exam2 * 0.15 + Final * 0.30 + Pgms * 0.4 ) ) / 12 
Queues  focus on the circular array implementation
   DemoQueue.jar  Executable jar to demonstrate Sahni's circular array queue.
   DemoQueue.exe  Above jar in an exe wrapper
Advanced Array Sorting
   Merge sort, building on the linked list implementation
   DemoMerge.exe  Program for tracing Merge Sort
   Shell's sort
   DemoShell.exe  Program for tracing Shell's Sort
   Quick sort
   DemoQuick.exe  Program for tracing Quick Sort
Hash tables and hash functions
   HashDrill.jar Executable jar file for hash table drill.
   HashDrill.exe Above jar in an exe wrapper
Exam II
General tree introduction
Binary Search Tree introduction
   BSTsmp.jar  Executable jar file for the simple Binary Search Tree
   BSTsmp.exe  Above jar in an exe wrapper