Midterm Topic Outline

1. lists
   • processing
   • Specializations:
     • stacks
     • queues
     • deque
   • implementation -
     • array
     • linked list
     • doubly linked list
     • circular list
     • circular queue
   • strings and sharing
   • internal vs. external lists (structures)
   • advantages of linked vs. sequential storage
   • xor 2 links for one.
   • partial order algorithm
2. trees
   • binary vs. regular
   • traversal (preorder, postorder,inorder)
   • father pointers
   • predecessors and successors
   • tree as binary tree
   • equivalence relations
3. Graphs
   • vertex based vs. edged based
   • free trees
   • spanning tree algorithm
   • elementary chain algorithm
   • distance/diameter
   • Eulerian and Hamiltonian cycles and chains
   • isomorphism
4. lisp:
   • s-expressions, lists, and storage allocation
   • cons, car, cdr
   • recursive routines
   • helper functions
   • what does function do?
   • write a function
5. 5) Garbage collection:
   • mark nodes, identify accesible vs, inaccessible
   • marking algorithms
   • stop & copy, generational scavanging
6. 6) storage allocation
   • first fit, best fit allocation
   • when to coalesce
   • buddy system
   • lru, nur paging
7. 7) sorting: different algorithms, complexity
   • selection sort
   • bubble sort
   • insertion sort
   • distribution counting
   • shellsort
   • tournamernt sort
   • heaps
   • heapsort
   • quicksort
   • medians
   • radix exchange sort
   • radix sort
   • mergesort
8. 8) Quadtrees:
   • adding nodes
   • pruning quadrants in search
   • bst search
9. General:
   • Proofs
   • Time and Space Complexity