.. _ToDo:


.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = False;ODSA.SETTINGS.MODULE_NAME = "ToDo";ODSA.SETTINGS.MODULE_LONG_NAME = "ToDo";ODSA.SETTINGS.MODULE_CHAPTER = ""; ODSA.SETTINGS.BUILD_DATE = "2022-11-29 16:52:11"; ODSA.SETTINGS.BUILD_CMAP = false;</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


.. index:: ! todo

TODO List
=========
.. raw:: html

   <hr /><h1>AV</h1><hr />

.. raw:: html

   <h2><a href="AnalIntro.html#todo0">source: AnalIntro</a></h2>

.. todo::

  type: AV

   To make students more engaged in the GrowthRates exercise, we may
   need a tool that allows students to input two growth rate functions.
   Then the tool should plot the graph of both functions and mark
   their crossing point. The student also should be allowed to play
   with the constant values for both functions and see that this only
   changes the crossing point but doesn't change which function grows
   faster than the other.

.. raw:: html

   <h2><a href="HashCImproved.html#todo0">source: HashCImproved</a></h2>

.. TODO::

  type: AV

   Fix and return hashAV.html to here.

   The following visualization lets you test out different combinations
   of hash function and collision resolution, on your own input data.

.. raw:: html

   <h2><a href="GraphTopsort.html#todo4">source: GraphTopsort</a></h2>

.. TODO::

  type: AV

   Provide a unified AV that can allow the user to pick which topsort
   (DFS or Queue), with or without cycles in the graph. The start of
   this is in ``AV/Development/TopSort/topSortAV*`` (for just random DFS),
   ``AV/Development/TopSort/qTopSortAV.*`` (for just random queue-based
   topsort), and ``AV/Development/TopSort/topSortAVs*`` (tries to unify).

.. raw:: html

   <h2><a href="GraphShortest.html#todo2">source: GraphShortest</a></h2>

.. TODO::

  type: AV

   Provide an AV that runs on a random graph. An initial version is in
   ``AV/Development/TopSort/dijkstraAV.*``.

.. raw:: html

   <h2><a href="GraphShortest.html#todo4">source: GraphShortest</a></h2>

.. TODO::

  type: AV

   AV here to demonstrate the minVertex implementation.

.. raw:: html

   <h2><a href="KDtree.html#todo0">source: KDtree</a></h2>

.. TODO::

  type: AV

   Add version where you can click to get the node inserted.

.. raw:: html

   <h2><a href="PerfectHash.html#todo1">source: PerfectHash</a></h2>

.. TODO::

  type: AV

   Make a proper visualization for perfect hashing, that lets the user
   specify a set of input keys, computes the hash function, then lets
   the user input keys to the table. A proper explanation for the
   process should be part of the visualization.

.. raw:: html

   <h2><a href="FFT.html#todo0">source: FFT</a></h2>

.. todo::

  type: AV

   Practice fft algorithm. Maybe only practice the final for loop since
   the rest of the algorithm is recursivly dividing the polynomial and
   performing fft on the smaller polynomials.

.. raw:: html

   <hr /><h1>BlockPy</h1><hr />

.. raw:: html

   <h2><a href="Iteration.html#todo0">source: Iteration</a></h2>

.. TODO::

  type: BlockPy

   Put first BlockPy exercise here.

.. raw:: html

   <h2><a href="Iteration.html#todo1">source: Iteration</a></h2>

.. TODO::

  type: BlockPy

   Put second BlockPy exercise here.

.. raw:: html

   <h2><a href="Iteration.html#todo2">source: Iteration</a></h2>

.. TODO::

  type: BlockPy

   Put third BlockPy exercise here.

.. raw:: html

   <hr /><h1>Code</h1><hr />

.. raw:: html

   <h2><a href="GraphShortest.html#todo3">source: GraphShortest</a></h2>

.. TODO::

  type: Code

   Why does the code look for an unvisited value first?
   Is there an easier way?

.. raw:: html

   <hr /><h1>Diagrams</h1><hr />

.. raw:: html

   <h2><a href="Compiler.html#todo0">source: Compiler</a></h2>

.. TODO::

  type: Diagrams

   Look at Susan's original notes (sectcomdes) to see what these are
   supposed to look like (she used cline to help build boxes, but
   MathJax cannot support it).

.. raw:: html

   <hr /><h1>Equation cross-reference</h1><hr />

.. raw:: html

   <h2><a href="Recurrence.html#todo0">source: Recurrence</a></h2>

.. TODO::

  type: Equation cross-reference

   Throughout this module, there are references to equations, both
   on this page and in the Summations module. These should be made
   into proper cross-references rather than hard-coded equation numbers.

.. raw:: html

   <hr /><h1>Exercise</h1><hr />

.. raw:: html

   <h2><a href="ListADT.html#todo0">source: ListADT</a></h2>

.. TODO::

  type: Exercise

   This exercise ought to get expanded to a much richer set of
   variations on the question.

.. raw:: html

   <h2><a href="ListDouble.html#todo0">source: ListDouble</a></h2>

.. TODO::

  type: Exercise

   Need exercises for inserting to and deleting from doubly linked lists.

.. raw:: html

   <h2><a href="HuffProof.html#todo0">source: HuffProof</a></h2>

.. TODO::

  type: Exercise

   Battery of MCQs for content.

.. raw:: html

   <h2><a href="Quicksort.html#todo0">source: Quicksort</a></h2>

.. TODO::

  type: Exercise

   Consider the Quicksort implementation for this module, where the
   pivot is selected as the middle value of the partition.
   Give a permutation for the values 0 through 7 that will cause
   Quicksort to have its worst-case behavior.

   There are a number of possible correct answers. To assess the
   answer, will need to run Quicksort over student's
   partition, and verify that at each step it will generate new
   partitions of size 6, 5, 4, 3, 2, then 1.

.. raw:: html

   <h2><a href="IndexingSumm.html#todo0">source: IndexingSumm</a></h2>

.. TODO::

  type: Exercise

   This is a good question, but its not nearly enough for a chapter
   summary.

.. raw:: html

   <h2><a href="GraphImpl.html#todo0">source: GraphImpl</a></h2>

.. TODO::

  type: Exercise

   Add a battery of questions to test knowledge of the
   implementations.

.. raw:: html

   <h2><a href="GraphTraversal.html#todo0">source: GraphTraversal</a></h2>

.. TODO::

  type: Exercise

   Summary exercise for graph traversals.

.. raw:: html

   <h2><a href="GraphShortest.html#todo7">source: GraphShortest</a></h2>

.. TODO::

  type: Exercise

   Summary battery of questions for Dijkstra's algorithm

.. raw:: html

   <h2><a href="MCST.html#todo2">source: MCST</a></h2>

.. TODO::

  type: Exercise

   Proficiency exercise for Prim's algorithm.

.. raw:: html

   <h2><a href="Kruskal.html#todo0">source: Kruskal</a></h2>

.. TODO::

  type: Exercise

    Summary battery of questions for Prim's and Kruskal's algorithms.

.. raw:: html

   <h2><a href="Impossible.html#todo0">source: Impossible</a></h2>

.. TODO::

  type: Exercise

   Need an exercise to study lower bound on Colletz function

.. raw:: html

   <hr /><h1>Explanation</h1><hr />

.. raw:: html

   <h2><a href="LinearIndexing.html#todo0">source: LinearIndexing</a></h2>

.. TODO::

  type: Explanation

   The slideshow should subsume the next paragraph and the caption.

.. raw:: html

   <hr /><h1>Figure</h1><hr />

.. raw:: html

   <h2><a href="Garbage.html#todo0">source: Garbage</a></h2>

.. TODO::

  type: Figure

   Replace this figure with an applet that demonstrates the use of
   handles.

.. raw:: html

   <h2><a href="DynamicProgramming.html#todo0">source: DynamicProgramming</a></h2>

.. TODO::

  type: Figure

   Put the figure here that was specified in the original document
   (top of the 3rd page), showing the recursion tree.

.. raw:: html

   <h2><a href="DPDA.html#todo0">source: DPDA</a></h2>

.. TODO::

  type: Figure

   Show figure

.. raw:: html

   <hr /><h1>Proficiency Exercise</h1><hr />

.. raw:: html

   <h2><a href="GraphTopsort.html#todo3">source: GraphTopsort</a></h2>

.. TODO::

  type: Proficiency Exercise

   Provide a proficiency exercise that randomly alternates between
   proficiency for DFS-based and queue-based Topsort.
   The bare beginnings of an exercise can be found in
   ``AV/Development/TopSort/topSortDFSPE.*``

.. raw:: html

   <hr /><h1>Revision</h1><hr />

.. raw:: html

   <h2><a href="ExchangeSort.html#todo0">source: ExchangeSort</a></h2>

.. TODO::

  type: Revision

   Rewrite along these lines: Here are two measures of "out of order":
   inversions and min-swaps. Selection sort (especially w/
   optimization) meets min-swaps, but that's not a useful measure in
   general. Insertion sort tracks inversions, it is I + n. Now, if we
   had an exchange sort, what would cost be? Go on to the proof.

.. raw:: html

   <h2><a href="SortOpt.html#todo0">source: SortOpt</a></h2>

.. TODO::

  type: Revision

   Rewrite along these lines: A classic form of code tuning is "test
   to save work". For each of our three sorting algorithms, we have a
   potential "test to save work" "optimization". The question is: When
   is the cost of test worth the work saved? Let's look at each of the
   three.

.. raw:: html

   <hr /><h1>Slideshow</h1><hr />

.. raw:: html

   <h2><a href="AnalProgram.html#todo0">source: AnalProgram</a></h2>

.. todo::

  type: Slideshow

   We need to think about a technique for visualizing the running time
   of some loop constructs. This can be very similar to how we
   visualize reaching the closed form solution of summations.

.. raw:: html

   <h2><a href="StackRecur.html#todo0">source: StackRecur</a></h2>

.. TODO::

  type: Slideshow

   The figure above and the following text should all be rolled into
   a slideshow.

.. raw:: html

   <h2><a href="Garbage.html#todo1">source: Garbage</a></h2>

.. TODO::

  type: Slideshow

   Replace this figure with a slideshow that demonstrates the use of
   reference counts (including the problem with cycles).

.. raw:: html

   <h2><a href="Garbage.html#todo2">source: Garbage</a></h2>

.. TODO::

  type: Slideshow

   Put here a visualization that demonstrates the use of reference
   counts.

.. raw:: html

   <h2><a href="Garbage.html#todo3">source: Garbage</a></h2>

.. TODO::

  type: Slideshow

   Replace this figure with an AV that demonstrates DSW.

.. raw:: html

   <h2><a href="GraphTopsort.html#todo0">source: GraphTopsort</a></h2>

.. TODO::

  type: Slideshow

   Replace the above figure with a slideshow that incorporates the
   following paragraph.

.. raw:: html

   <h2><a href="GraphTopsort.html#todo1">source: GraphTopsort</a></h2>

.. TODO::

  type: Slideshow

   Replace the following paragraph with a slideshow.

.. raw:: html

   <h2><a href="GraphTopsort.html#todo2">source: GraphTopsort</a></h2>

.. TODO::

  type: Slideshow

   Incorporate the following into a slideshow.

.. raw:: html

   <h2><a href="GraphShortest.html#todo0">source: GraphShortest</a></h2>

.. TODO::

  type: Slideshow

   Incorporate the following paragraph into a slideshow with the
   figure below it.

.. raw:: html

   <h2><a href="GraphShortest.html#todo1">source: GraphShortest</a></h2>

.. TODO::

  type: Slideshow

   Provide a slideshow to demonstrate the following example.

.. raw:: html

   <h2><a href="GraphShortest.html#todo5">source: GraphShortest</a></h2>

.. TODO::

  type: Slideshow

   This slideshow illustrates Dijkstra's algorithm using the heap.
   The start vertex is A.
   All vertices except A have an initial value of :math:`\infty`.
   After processing Vertex A, its neighbors have their D estimates
   updated to be the direct distance from A.
   After processing C (the closest vertex to A),
   Vertices B and E are updated to reflect the shortest
   path through C.
   The remaining vertices are processed in order B, D,
   and E.
   Changes in the D array should be shown along with this.

.. raw:: html

   <h2><a href="GraphShortest.html#todo6">source: GraphShortest</a></h2>

.. TODO::

  type: Slideshow

   Slideshow to demonstrate the relative costs of the two algorithms.

.. raw:: html

   <h2><a href="MCST.html#todo0">source: MCST</a></h2>

.. TODO::

  type: Slideshow

   Replace the previous diagram with a slideshow illustrating the
   concept of MCST.

.. raw:: html

   <h2><a href="MCST.html#todo1">source: MCST</a></h2>

.. TODO::

  type: Slideshow

   Implement a slideshow demonstrating the Priority Queue version of
   Prim's algorithm

.. raw:: html

   <h2><a href="Kary.html#todo0">source: Kary</a></h2>

.. TODO::

  type: Slideshow

   Slideshow of Book Figure 6.16: shows full and complete \Kary\ trees
   for K=3. In practice, most applications of \Kary\ trees limit them
   to be either full or complete.

   Full and complete 3-ary trees.
   (a)~This tree is full (but not complete).
   (b)~This tree is complete (but not full).}{ThreeTree}

.. raw:: html

   <hr /><h1>Summary Questions</h1><hr />

.. raw:: html

   <h2><a href="GraphTopsort.html#todo5">source: GraphTopsort</a></h2>

.. TODO::

  type: Summary Questions

   Provide a summary battery of questions.

.. raw:: html

   <hr /><h1>Text</h1><hr />

.. raw:: html

   <h2><a href="HashAnal.html#todo0">source: HashAnal</a></h2>

.. TODO::

  type: Text

   Where did that last claim about the linear probing cost come from?

.. raw:: html

   <hr /><h1>exercise</h1><hr />

.. raw:: html

   <h2><a href="KDtree.html#todo1">source: KDtree</a></h2>

.. TODO::

  type: exercise

   We need a proficiency exercise.

.. raw:: html

   <hr /><h1>text</h1><hr />

.. raw:: html

   <h2><a href="AnalTuning.html#todo0">source: AnalTuning</a></h2>

.. TODO::

  type: text

   Give an example of this type of representational change.

.. raw:: html

   <h2><a href="PerfectHash.html#todo0">source: PerfectHash</a></h2>

.. TODO::

  type: text

   Explain how Perfect Hashing works.