FP-PaulOppenheim-presentation-1

From CS 294-10 Visualization Sp10

Jump to: navigation, search


Why Algorithm Visualization?

  • Software is hard to understand.
  • In-code: comments, unit tests
  • Out-of-code: whiteboards, diagrams, meetings, documentation
  • Are there universal guidelines about diagrams relating to software and algorithms?
  • How would you implement such guidelines, today?

Software is often difficult to explain. Code authors frequently comment source code, write unit tests, and write external documentation. Additionally, developers use whiteboards and diagrams to communicate how their software works. Are there universal guidelines about diagrams relating to software and algorithms? What are the practical applications that can be taken today given the body of research on the subject?

Why an Algo Vis Language?

  • Need *some* type of tool to make initial vis!
  • Embed vis description near the code itself in the comments
  • Comment-extracting tools (e.g. Doxygen, Sphinx) enhanced to process vis syntax
  • Tools make HTML; vis should be web-friendly

One of the most immediate needs of anyone interested in answering this question is a practical tool for generating graphs given pseudocode / visual-code annotations. Ideally, such code would be embedded inside the code itself in the comments along with other documentation. Tools currently used for extracting comments (e.g. Doxygen, Sphinx, etc.) could be enhanced to process additional syntax to generate images. Documentation generated from such tools is typically HTML with other web-friendly data types; as such, it would be expected that diagrams in the software would be similarly web-standards friendly.

Class Project Goals

  • research the existing body of work regarding algorithm visualizations
  • create a simple, usable language to draw the primitives outlined in the existing work

Bonus / Later Work

  • generate an extension to an existing documentation tool which processes this graphing language
  • give a simple example by explaining some algorithms in a piece of existing software with these annotations

NOT going to

  • be suitable for general-purpose image generation
  • automatically generate graphs based on non-annotation source code in any language
  • reimplement DOT - http://www.graphviz.org/
  • reimplement processing - http://processing.org/
  • draw UML
    • the graphs will be informal, to the user's specification (possibly to UML, but ideally *mostly* arbitrary)
    • UML *will* play a role in minimal flexibility (as in, minimally a user should be able to specify something close to existing UML diagram types)

Example - Quicksort

Data Structures and Algorithms with Object-Orientated Design Patterns in Java (Preiss)

<img src="quicksort Preiss text book Data Structures and Algorithms with Object-Orientated Design Patterns in Java.gif" alt="" title="quicksort Preiss text book Data Structures and Algorithms with Object-Orientated Design Patterns in Java"/>

Example - Quicksort

Wikipedia

<img src="Quicksort-diagram-wikipedia.png" alt="" title="Quicksort diagram wikipedia"/>

Example - Quicksort

Intel

<img src="quicksort_diag1_intel.gif" alt="" title="Quicksort diagram intel"/>

<img src="quicksort_diag2_intel.gif" alt="" title="Quicksort diagram intel"/>

<img src="quicksort_diag3_intel.gif" alt="" title="Quicksort diagram intel"/>

Example - Quicksort

Possible annotation to generate wikipedia version (completely uneducated guess at this point)

	array, box whitespace
	
	3 7 8 5 2 1 9 5 4
	
	  +-----------+ +-+
	  V           | V |
	3 7 8 5 2 1 9  5  4
	  |               ^
	  +---------------+
	

etc

Example - Quicksort

Or another annotation, closer to software

	array a = 3, 7, 8, 5, 2, 1, 9, 5, 4;
	idx p = 0; idx i = 1; idx j = len(a) - 1;
	i++ until *i > p
	j-- until *j < p
	line directed j.init, j
	lint directed j, i.init
	line directed i, j.init
	{tmp = a[i.init]; a[i.init] = *j; a[j]=
	

 

 

Will be based on research as I go, many iterations

 

 

HOPEFULLY LESS AWFUL THAN MY HACK OF AN EXAMPLE.

Thanks! Questions? Comments?

<img src="scotty.png" alt="" title="Scotty Dog"/>

Presentation - S5 javascript / CSS slideshow



[add comment]
Personal tools