MITx Certificate in Computer Science Using Python

January 23rd, 2014



Ron Fredericks writes: I completed the first of 7 MITx courses in the new Foundations in Computer Science XSeries titled “6.00.1x Introduction to Computer Science and Programming using Python.” The XSeries in computer science offered by the M.I.T. Department of Electrical Engineering and Computer Science, is a sequence of courses that introduce key concepts of computer science and computational thinking. Python, Java, Digital Circuits, Programmable Architectures, and Computer Systems Organization are covered by this series of courses.

It was a pleasure to take this course with such an expert teacher leading the videos, Dr. Eric Grimson, chancellor of MIT’s EE and CS departments. I noticed that one of professor Grimson’s best teaching skills was his ability to cover a topic with surprisingly short videos. Yet he covered the material well and made the material memorable with historical anecdotes or useful insights.

Course Stats

Because each video in the course is unlisted on YouTube, it is reasonable to use each video’s view count as an indicator of student activity. There were 98 videos in the course totaling 12 hours and 10 minutes spread over an 8 week period. Each video is on average 7.5 minutes long. The number of views (and proportional estimate to the decline in the number of active students by extension), follows a typical power law distribution. I see a similar power curve using LectureMaker’s Cross-domain Video Distribution Platform where % watched is a standard analytics tool measuring viewer engagement. See chart below where the purple curve is the estimated power curve:

VideoViewsChart

Another interesting review comes from the likes and dislikes recorded with each of the 98 YouTube videos. The distribution of student “likes” over the course period seems to have several spikes, even as the number of views per course is decreasing as shown in the previous chart. See the chart below:

LikesDislikesChart

I have labeled several of the peaks where students appear to vote highly for a particular video from A to I in the chart above. Here is a list of the videos voted highly by the students:

Symbol in Chart Week Number Lecture Number Lecture Topic Video Title
A 1 1 Introduction to Computation Introduction
 
B 1 2 Core Elements of Programs Introduction
 
C 1 2 Core Elements of Programs Branching Programs
 
D 2 4 Functions Computing Powers as an Example
 
E 3 5 Recursion Towers of Hanoi
 
F 4 7 Debugging Debugging as Search
 
G 5 9 Efficiency and Orders of Growth Measuring Complexity
 
H 5 10 Memory and Search Amortized Cost Analysis: Demo
 
I 8 Research Videos Dr. Fredo Durand 3D Computer Graphics

Certificate

Each course comes with a permanent link to a proof of completion called an honor certificate. The completed series comes with a final XSeries certificate. Total cost for the program is estimated at $425.

Here is a permanent link to my course honor certificate

Grade

While each course certificate states that the student passed the course. A grade is also assigned for the student’s benefit.

Note that each quiz, test, midterm, and final are auto-graded. The multiple choice questions and python source code are all auto-graded. The auto-grader did get confused on a few of my source code submissions. The confusion came from code comments using key words that the auto-grader mistook for live python grammar. I solved this problem by submitting my code samples without comments. In some cases the problems where auto-graded incorrectly through teaching staff errors. These errors were announced and handled as best they could. Because of the rarity in auto-grading problems, I found that the policy of throwing out my worst test score solved any remaining issues I may have had around grading issues.

Here is a copy of my grade (click image to enlarge):

grade_snippet

Progress

This course included 8 weeks of instruction with:

  • Multiple problem sets during each week,
  • An end of week problem set,
  • A midterm, and
  • A final exam.

I found the evolving progress report helpful to stay motivated to complete the course. There are horizontal grid marks for various milestones such as passing and grade levels. The lowest weekly problem set is automatically thrown out, as marked by the “x”. I wish a student average for the course could have been included as well.

Here is a what my progress report looks like (click image to enlarge):

progress

Courseware

The courseware includes several features and navigation menus. See image below to match discussion with each red letter.

A
Along the top are the main course services:

  • Courseware – As shown in image below with video instruction and links to all other course services.
  • Updates and News – changes, errors, and comments from teaching staff.
  • Calendar – Due dates for problem sets, midterm date, and final date.
  • Wiki – Support material and useful links supplied by students and teaching staff.
  • Discussion – A link to all discussion threads launched by students. Each video segment (several per week) has a discussion, merged together into this link.
  • Progress – Individual progress report, summary (as shown in image above), along with each graded exercise.
  • Textbook – A link to the official text book. Textbook is optionally and offered at about 50% discount.

B
Down the left margin are links to each week’s course material. Each week becomes available according to the calendar. When the course is completed, the full course is still available as an archive. See Week 7 is the image below for details.

C
Each lecture includes a ribbon of activities as shown horizontally just above the current video – with icons for each video, tests, and additional material (icon not shown) in a time ordered sequence.

D
Each video includes a time encoded transcript to the right of the video. As the video progresses, the text is highlighted. A student can click on the text and the video will preposition to that portion of the text. The video can be downloaded for those with slow Internet, and the timed transcript can be downloaded as well.

E
Each lesson includes a slide set that can be downloaded as well as any software examples discussed.

F
Each lesson includes a discussion forum where students can post questions or comments. Some discussions end up with improved ranking based on “+1″ clicks by students. Teaching staff can also mark a discussion as useful with a unique icon as well. These per video discussion threads are grouped into one common discussion link discussed above (in section “A”) so ideas can be searched or further ranked by interest.

Here is what the courseware looks like (click image to enlarge):

Sample_Course_Page_Week7

Technorati Tags: , , , , , ,

Visualizing Software Tree Structures

December 11th, 2013


Ron Fredericks writes: in this post I present revision 3 of a software class called visualizeTree, to draw and visualize a tree structure using Python 2.7, TK graphics modules, pyDot module with GraphViz, and FFmpeg. You can reuse the videos presented here as a teaching aid for common search algorithms: depth first search (DFS), breadth first search (BFS), and depth first ordered search (DFSOrdered). You can also use these examples to create and visualize your own trees and search methods.

For revision 3, I split the growing code into four .py files. Included is a new class called slideShow to animate search algorithms within the main python program itself using TK graphics. The original FFmpeg video animation method is fully supported and allows animations to be played from Internet hosts or from a teachers slide set as mpeg4 video to name a few examples. Only now, using my slideShow class, you can visualize and animate search tree operations without leaving the python interpreter.

Python IDE showing buildBalancedTree(), searchTree(), and playSlides() results.

Python IDE showing buildBalancedTree, searchTree, & playSlides results.

See the reference section below for details on the required support software used in this project, or check out the source code from GitHub

Binary Search Tree Overview

In this article I focus on the binary search tree (BST). BSTs are a fundamental data structure used to construct more abstract data structures such as sets and associative arrays.

The information represented by each node is usually a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records. In the demos presented here, the search key is simply an ascending integer or character for each node.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient. In the demos presented here, the search method DFSOrdered visually shows the value of in-order traversal.

Unbalanced Tree
A BST is sometimes also called an ordered or sorted binary tree. The structure has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.
  • There must be no duplicate nodes.

The average number of nodes to search in a worst case example using the tree shown below is 2.65. This is the sum of each depth first search to leaves on the tree: 3, 3, 2 or 8/3

This tree was drawn automatically with the software presented in this article

This tree was drawn using the buildUnbalancedTree() and sketchTree()
functions presented in this article

The information presented in this section came from the following wiki article: Binary search tree

Balanced Tree
A balanced BST includes two more provisions: All leaves in the tree must be at the same maximum depth, or one level above the maximum depth. And, nodes must have left and right branches, except for final level in the tree. These additional restrictions can shorten a search and offer more reliable complexity.

The average number of nodes to search in a worst case example is 2.25. This is the sum of each depth first search to leaves on the tree: 2, 2, 2, 4 or 9/4. An improvement over the unbalanced tree shown above.

This tree was drawn using the buildBalancedTree() function presented in this article.

This tree was drawn using the buildBalancedTree() and sketchTree()
functions presented in this article.

Videos Generated Using This Article’s Software

These videos were created with the python code and FFmpeg batch file listed below. This type of video could be used to research the behavior of a new search or tree creation algorithm integrated into this code – or the videos can be used in their current form as a teaching aid, perhaps as part of a ppt slide set.

Breadth First Search (BFS) Video

This video demonstrates the breath first search algorithm helper function BFS() associated with the visualizeTree class featured in the python code listing below. In this case we are searching for tree element “7″. The search goes from left to right, then top to bottom. The search needs to test each node in the tree since element “7″ is the worst case location.

 

Youtube link

 

Depth First Search Video

This video demonstrates the depth first search algorithm as a helper function DFS() associated with the visualizeTree class featured in the python code listing below. In this case we are searching for the same tree element “7″. The search goes from top to bottom, starting from the left, then moving to right. The search needs to test each node in the tree since element “7″ is the worst case location.

 

Youtube link

 

Ordered Depth First Search Video

This video demonstrates an improved depth first search algorithm based on the helper function DFSOrdered() as seen in the python code listing below. The search uses information about balanced trees, and the element to find, in order to make an intelligent search decision.

In this case we are searching for the same tree element “7″ again. The search still goes from top to bottom, left to right, just like the DFS search video above. Yet, the search will also test for right branched children that are less than the element we are searching, element “7″ in this case. So, the search path becomes much shorter.

 

Youtube link

 

Ordered Depth First Search Video – Balanced with 26 Nodes

This video demonstrates an improved tree structure since all nodes are balanced. The video was again generated using the tools supplied in this article. The pydot interface shows correct depth for each node with all edges pointing in the same direction aligned parallel to each other.

In this case we are searching for tree element “j”. The search still goes from top to bottom, left to right, just like the DFS search videos above. The tree was generated using the supplied function “buildBalancedTree() from a sorted list of 26 characters (a to z).

 

Youtube link

 

Layout of software and files for this demo

 

The image below shows the two files used to animate tree structures:

  • The python code for creation of dot graphics with pyDot module, an interface to the GraphViz open source cross-platform graphic program.
  • The FFmpeg utility in a batch file to automate conversion of png image sequences generated by the python code in the subdirectory vidImages

Read the python source code for comments and links to get the supporting software module: pyDot and cross-platform programs: GraphViz and FFmpeg

screenshot_programs

 

The image below shows the png image sequence created by the python code as well as videos generated with the FFmpeg video utility batch file. Using settings shown in the batch file, each png file represents one second of video, for a total of 21 seconds of mpeg-4 video content.

screenshot of vidImages Subdirectory

Main program: binarySearchTreeAnimationApp.py

 

The main program presented here walks you through all the steps to generate a tree, search a tree, and animate the results. Yet the actual tree, search visualization, and animation code are shown in the next sections.

Note: The source code highlighting tool for both the python and DOS Batch file listings include hyperlinks that are automatically generated to get more information about a given keyword, language element, or group of related topics. I suggest using the github version controlled software to get the software however, because “‘” single quote marks tend to get mangled into back-ticks in this tool.

code=python
  1. """
  2. File: binarySearchTreeAnimationApp.py
  3.  
  4. Animate a Binary Search Tree using Python, pyDot, GraphViz, TK, and FFmpeg utility
  5.  
  6. Project home: http://www.embeddedcomponents.com/blogs/2013/12/visualizing-software-tree-structures/
  7.  
  8. Developed by Ron Fredericks, Video Technologist, at LectureMaker LLC, http://www.LectureMaker.com
  9.     MIT License, Copyright (c) 2013, Ron Fredericks
  10.     Free to use following these terms: http://opensource.org/licenses/MIT 
  11.  
  12. Revision 3: 1/5/2014
  13.  
  14. Usage:
  15.      Input: A binary search tree to sketch (example provided).
  16.             A search algorithm to animate (examples provided).
  17.             Examples include all code needed to generate and visualize tree structures:
  18.                 1) binaryTree.py includes binaryTree class,
  19.                     functions to create unbalanced and balanced tree from a list, and
  20.                     manual creation of a tree one node at a time.
  21.                 2) visualizeTree.py includes visualizeTree class,
  22.                     functions for breadth first, depth first, and ordered depth first search.
  23.    
  24.      Output: This demo software presents two forms of graphic animation, using a series of png images:
  25.                 1) Animate images using the supplied slideShow TK graphics python class
  26.                 2) Animate images using mpeg4 video produced from supplied FFmpeg batch file
  27.    
  28.  
  29. Inspired by MITx 6.00.1x "Introduction to Computer Science and Programming"
  30. As taught by Professor Eric Grimson, Chairman of EECS Department, MIT
  31. Fall 2013, http://www.edx.org
  32.  
  33.  
  34. Required Software:
  35.     The following free open source programs should be installed on your computer:
  36.         GraphViz: Graph visualization tool: http://www.graphviz.org/
  37.         FFmpeg: Cross-platform solution to record, convert and stream audio and video: http://www.ffmpeg.org/
  38.    
  39.     The following python module should be installed into your environment:
  40.         pydot: a python interface to Graphvize’s Dot language: https://code.google.com/p/pydot/
  41.    
  42.     The following python modules are used for display of individual PNG images:
  43.         Tkinter: standard python GUI: https://wiki.python.org/moin/TkInter
  44.         Image and ImageTk: the python image library: http://www.pythonware.com/products/pil/
  45.    
  46.     The following support modules are supplied with this project:
  47.         binaryTree.py     - Used to create a binary search tree to visualize.
  48.         visualizeTree.py  – Used to draw a binary search tree as well as to draw the steps during a search.
  49.         slideShow.py      – Used to animate a series of graphic images,
  50.                                 in this case, the binary tree and the search process.
  51.         png2mpg4.bat      – Used to generate mpg4 video from a series of png graphic images,
  52.                                 in this case, the binary tree and the search process.
  53. """
  54.  
  55. # Local python libraries supplied with this project
  56. import binaryTree
  57. import visualizeTree
  58. import slideShow
  59.  
  60. # import the graphics module used to launch supplied slideShow TK graphics python class
  61.  
  62. # History:
  63. #   Initial project published on 12/11/2013
  64. #
  65. #   Rev 1: 12/16/2013
  66. #       1) Improve comments for accuracy.
  67. #
  68. #   Rev 2: 12/23/2013
  69. #       1) Provide an initialization segment near the top of the code to simplify control of tree sketching and search animation
  70. #       2) New FFmpeg command line to generate intelligently scaled video in HD from PNG image sequences:
  71. #        ffmpeg -f image2 -r 1 -start_number 00001 -i bst_graph%%05d.png  -b:v 5000k -vcodec mpeg4 -r 30 -vf scale="’if(gt(a,4/3),1920,-1)’:'if(gt(a,4/3),-1,1280)’" -y movie.mp4
  72. #
  73. #   Rev 3: 1/4/2014
  74. #       1) Split program into seperate files:
  75. #           a) binaryTree.py – binary search tree
  76. #           b) visualizeTree.py – pydot/GraphViz package
  77. #           c) slideShow.py – TK graphics
  78. #           d) binary_tree_search_video – main program
  79.  
  80. #############################
  81. # User Controlled Parameters
  82. #############################
  83.  
  84. # Examples
  85.  
  86. # Build balanced trees from a sorted list and rootValue set to None
  87. #————————————————————————————–
  88.  
  89. # Build a tree using an integer list. The root value is determined automatically
  90.  
  91. listForTree = sorted([5,2,1,4,8,6,7,3])
  92. rootValue = None   # Note: None will be replaced by the midpoint of the sorted list
  93. findValue = ’1′
  94.  
  95. # build a tree using a character list. The root value is determined automatically
  96. listForTree = [c for c in 'abcdefghijklmnopqrstuvwxyz']
  97. rootValue = None   # Note: None will be replaced by the midpoint of the list
  98. findValue = ‘j
  99.  
  100. # Build unbalanced trees using an unsorted list and rootValue set to a known value in list
  101. #—————————————————————————————
  102.  
  103. # Build a tree using an integer list. The root value is determined manually
  104. """
  105. listForTree = [5,2,1,4,8,6,7,3]
  106. rootValue = 5   # Note: Select a root key from the list of elements in listForTree
  107. findValue = ’7′
  108. """
  109.  
  110. # Longer alpha demo with randomly shuffled tree data, and random choice for search value
  111. """
  112. import random
  113. listForTree = [c for c in 'abcdefghijklmnopqrstuvwxyz']
  114. rootValue = listForTree[len(listForTree)/2] # Note: Select a root key from the list of elements in listForTree
  115. random.shuffle(listForTree)
  116. findValue = random.choice(listForTree)
  117. """
  118.  
  119.  
  120. # Select a predefined search function from options described above (in overview)
  121. #————————————————————————————
  122.  
  123. searchNameFcn = {‘DFSOrdered’: visualizeTree.DFSOrdered, ‘DFS’: visualizeTree.DFS, ‘BFS’: visualizeTree.BFS}
  124.    
  125. #searchName = ”              # Don’t search
  126. searchName = ‘BFS’            # Breadth-first Search
  127. #searchName = ‘DFS’           # Depth-first Search
  128. #searchName = ‘DFSOrdered’    # Ordered Depth-first Search
  129.  
  130.  
  131. # Define path where image sequences will be stored (windows example)
  132. #——————————————–
  133. fileDir = "C:\\Users\\Ron Fredericks\\Documents\\LectureMaker\\Projects\\MOOC\\EDx\\cs600.1\\Video\\vidImages\\"
  134.  
  135.  
  136. #####################################################################################
  137. # Generate a Binary Tree using controls defined above and Print Out Animation Status
  138. #####################################################################################
  139.  
  140. # Display ‘sketch tree’ and ‘animate search’ parameters
  141. if not rootValue:
  142.     print "Generate a balanced tree with",   
  143.     root = binaryTree.buildBalancedTree(listForTree[:], 0, len(listForTree))
  144.     print "Generate an unbalanced tree with",
  145.     root = binaryTree.buildUnbalancedTree(listForTree[:], rootValue)
  146. if not root:
  147.     print "Error: tree not built",
  148.     raw_input("Press return key to continue: ")
  149. print "root value:", root.getValue()   
  150.  
  151. print "List used to generate tree:", str(listForTree)
  152. print "Search for a value of", findValue, "using", searchName, "search method"
  153.  
  154. # Demonstrate insert() and delete() binaryTree methods
  155. nodeInserted = root.insert(1)
  156. if nodeInserted != None:
  157.     print "Node " + str(nodeInserted.getValue()) + " was successfully inserted into tree"
  158.     print root.delete(1)
  159.     print "Node not inserted"   
  160.  
  161.  
  162. ##################################################################
  163. # Draw and animate binary search tree during a BFS or DFS search
  164. ##################################################################
  165.  
  166. # Instantiate the visualizeTree object
  167. vT = visualizeTree.visualizeTree(fileDir)
  168.  
  169. # Draw the initial binary search tree.
  170. vT.searchTree(root, visualizeTree.sketchTree)
  171. vT.setVidFrames(3)
  172. vT.updateGraph()
  173. vT.appendVisualizeList()
  174.  
  175. # Animate a search to find a node in the tree.
  176. if searchName:
  177.     vT.setVidFrames(1)
  178.     vT.searchTree(root, searchNameFcn[searchName], findValue)
  179.  
  180. # extend the final segment of video for 3 more frames (or 3 seconds in video, based on FFmpeg settings)
  181. vT.setVidFrames(3)
  182. vT.updateGraph()
  183.  
  184.  
  185. ##################################################################
  186. # Animate the search method using TK graphics
  187. ##################################################################
  188.  
  189. mainTitle = "Find " + ‘"’ + findValue + ‘"’ + " using " + searchName
  190. rootTk = Tkinter.Tk()
  191. playList = vT.visualizeList
  192. sShow = slideShow.slideShow(rootTk)
  193. sShow.setImageScaling(1280, 720)
  194. sShow.playSlides(playList, mainTitle, "Quit", True)
  195. rootTk.destroy()

Python class: binaryTree.py

 

Use this code with the main program to create and operate on binary tree structures. Several sample trees are generated using this class from the main program. You can use your own class or use the methods I provide.

code=python
  1. """
  2. File: binaryTree.py
  3.  
  4. Support Module for: Animate a Binary Search Tree using Python
  5.  
  6. Project home: http://www.embeddedcomponents.com/blogs/2013/12/visualizing-software-tree-structures/
  7.  
  8. Developed by Ron Fredericks, Video Technologist, at LectureMaker LLC, http://www.LectureMaker.com
  9.     MIT License, Copyright (c) 2013, Ron Fredericks
  10.     Free to use following these terms: http://opensource.org/licenses/MIT 
  11.  
  12. Revision 3: 1/5/2014
  13.  
  14. ###########################################
  15. # Class binaryTree()
  16. ###########################################
  17.  
  18. Create a binary search tree
  19.  
  20. Public methods to interconnect nodes:
  21.     setLeftBranch()
  22.     setRightBranch()
  23.     setParent()
  24.     getValue()
  25.     getLeftBranch()
  26.     getRightBranch()
  27.     getParent()
  28.  
  29. Public methods to operate on nodes:   
  30.     insert()            – insert a node
  31.     lookup()            – find a node
  32.     delete()            – delete a node
  33.     children_count()    – return number of children associated with a node
  34.     print_tree()        – print a sorted list of nodes in the tree
  35.  
  36. External functions to build a tree:
  37.     manual method           - highlighted example in comments
  38.     buildBalancedTree()     - generate a balanced tree from a sorted list
  39.     buildUnbalancedTree()   - generate an unbalanced tree from an unsorted list
  40. """
  41.  
  42. # History:
  43. #   Initial project published on 12/11/2013
  44. #
  45. #   Rev 1: 12/16/2013
  46. #       1) Improve comments for accuracy.
  47. #
  48. #   Rev 2: 12/23/2013
  49. #       1) Provide 3 tree generation options: manually create tree, generate random unbalanced tree, create balanced tree.
  50. #       2) Improve draw method to include left, right, and middle "invisible" nodes and intelligent edge weights,
  51. #            now all edges in same direction are parallel, and every node of the same depth is displayed at the same depth.
  52. #       3) Fix bug in DFSOrdered() search function
  53. #       6) Improve video scaling:
  54. #            a) support large trees
  55. #            b) support HD video during graph generation and in FFmpeg for 1920 x 1080 pixel size
  56. #
  57. #   Rev 3: 1/4/2014
  58. #       1) Create (this) binaryTree.py module to clarify and shorten original project code
  59. #       2) Fix bug in binaryTree.lookup() method: fix the case for lookup not found
  60. #       3) Add new binaryTree.delete() method to delete a node, and helper function binaryTree.children_count() to return node’s number of children
  61. #       4) Add new binaryTree.print_tree() method to list node values in sorted order to standard output
  62. #       5) Improve insert recursive binaryTree.insert() method: a) detect when node already present, b) return inserted node object on success
  63. #       
  64.  
  65.  
  66. class binaryTree(object):
  67.     # Reference: Structure and node naming convention came from edx.org’s mitX MOOC course 6.00.1x slides taught by professor Eric Grimson, Fall 2013.
  68.     def __init__(self, value):
  69.         self.value = value
  70.         self.leftBranch = None
  71.         self.rightBranch = None
  72.         self.parent = None
  73.        
  74.     def setLeftBranch(self, node):
  75.         self.leftBranch = node
  76.        
  77.     def setRightBranch(self, node):
  78.         self.rightBranch = node
  79.        
  80.     def setParent(self, parent):
  81.         self.parent = parent 
  82.        
  83.     def getValue(self):
  84.         return self.value
  85.        
  86.     def getLeftBranch(self):
  87.         return self.leftBranch
  88.        
  89.     def getRightBranch(self):
  90.         return self.rightBranch
  91.        
  92.     def getParent(self):
  93.         return self.parent
  94.  
  95.     def insert(self, value):
  96.         """
  97.         Insert new node with data key set to value
  98.         Return inserted node object to caller, or None if node not inserted (when node was already present)
  99.         Modified from reference: http://www.laurentluce.com/posts/binary-search-tree-library-in-python/
  100.         """       
  101.         if value < self.value:
  102.             if self.getLeftBranch() is None:
  103.                 self.setLeftBranch(binaryTree(value))
  104.                 self.getLeftBranch().setParent(self)
  105.                 return self.getLeftBranch()
  106.             else:
  107.                 return self.getLeftBranch().insert(value)
  108.         elif value > self.value:
  109.             if self.getRightBranch() is None:
  110.                 self.setRightBranch(binaryTree(value))
  111.                 self.getRightBranch().setParent(self)
  112.                 return self.getRightBranch()
  113.             else:
  114.                 return self.getRightBranch().insert(value)             
  115.  
  116.     def lookup(self, value):
  117.         """
  118.         Lookup node containing data key set to value
  119.         Returns node object to caller, or None if not found
  120.         Modified from reference: http://www.laurentluce.com/posts/binary-search-tree-library-in-python/
  121.         """
  122.         if value < self.value:
  123.             if self.getLeftBranch() is None:
  124.                 return None
  125.             return self.getLeftBranch().lookup(value)
  126.         elif value > self.value:
  127.             if self.getRightBranch() is None:
  128.                 return None
  129.             return self.getRightBranch().lookup(value)
  130.         else:
  131.             return self 
  132.            
  133.     def delete(self, value):
  134.         """
  135.         Delete node containing data key set to value
  136.         Returns status text message
  137.         Modified from reference: http://www.laurentluce.com/posts/binary-search-tree-library-in-python/
  138.         """
  139.         # get node containing value and its number of children | or return with node not found message
  140.         node = self.lookup(value)
  141.         if not node:
  142.             return "Error in delete method: node " + str(value) + " not found"
  143.         else:
  144.             children_count = node.children_count(node)
  145.         if children_count == 0:
  146.             # if node has no children, just remove it
  147.             parent = node.getParent()
  148.             if parent.getLeftBranch() is node:
  149.                 parent.setLeftBranch(None)
  150.             else:
  151.                 parent.setRightBranch(None)         
  152.         elif children_count == 1:
  153.             # if node has 1 child, replace node by its child
  154.             if node.getLeftBranch():
  155.                 n = node.getLeftBranch()
  156.             else:
  157.                 n = node.getRightBranch()
  158.             parent = node.getParent()
  159.             if parent:
  160.                 if parent.getLeftBranch() is node:
  161.                     parent.setLeftBranch(n)
  162.                 else:
  163.                     parent.setRightBranch(n)
  164.         elif children_count == 2:
  165.             # if node has 2 children, find its successor
  166.             parent = node
  167.             successor = node.getRightBranch()
  168.             while successor.getLeftBranch():
  169.                 parent = successor
  170.                 successor = successor.getLeftBranch()
  171.             # replace node value by its successor value
  172.             node.value = successor.value
  173.             # fix successor’s parent’s child
  174.             if parent.getLeftBranch() == successor:
  175.                 parent.setLeftBranch(successor.getRightBranch())
  176.             else:
  177.                 parent.setRightBranch(successor.getRightBranch())
  178.         childMessageFrag = ("no children", "1 child", "2 children")
  179.         return "Node " + str(value) + " has " + str(childMessageFrag[children_count]) + " and was successfully deleted"
  180.            
  181.     def children_count(self, node):
  182.         """
  183.         Returns the number of children of a tree node object: 0, 1, 2
  184.         """
  185.         if node is None:
  186.             return None
  187.         cnt = 0
  188.         if self.getLeftBranch():
  189.             cnt += 1
  190.         if self.getRightBranch():
  191.             cnt += 1
  192.         return cnt           
  193.  
  194.     def print_tree(self):
  195.         """
  196.         Print tree content inorder
  197.         """
  198.         if self.getLeftBranch():
  199.             self.getLeftBranch().print_tree()
  200.         print self.getValue(),
  201.         if self.getRightBranch():
  202.             self.getRightBranch().print_tree()
  203.      
  204.     def __str__(self):
  205.         return str(self.value)
  206.  
  207.  
  208. """
  209. A Manual Method to Instantiate a Tree
  210. ————————————-
  211.  
  212. n5 = binaryTree(5)
  213. n2 = binaryTree(2)
  214. n1 = binaryTree(1)
  215. n4 = binaryTree(4)
  216. n8 = binaryTree(8)
  217. n6 = binaryTree(6)
  218. n7 = binaryTree(7)
  219. n3 = binaryTree(3)
  220.  
  221. n5.setLeftBranch(n2)
  222. n2.setParent(n5)
  223. n5.setRightBranch(n8)
  224. n8.setParent(n5)
  225. n2.setLeftBranch(n1)
  226. n1.setParent(n2)
  227. n2.setRightBranch(n4)
  228. n4.setParent(n2)
  229. n8.setLeftBranch(n6)
  230. n6.setParent(n8)
  231. n6.setRightBranch(n7)
  232. n7.setParent(n6)
  233. n4.setLeftBranch(n3)
  234. n3.setParent(n4)
  235.  
  236. # define sketch tree and animate search parameters
  237. root = n5
  238. findValue = ’7′
  239. listForTree = None
  240. """
  241.  
  242.  
  243. # Helper functions to instantiate a tree from a list
  244. # ————————————————–
  245.  
  246. def buildBalancedTree(sortedList, start, end):
  247.     """
  248.     Build a balanced binary search tree from a sorted linked list.
  249.  
  250.     This function uses class binaryTree, with methods:
  251.         ‘getLeftBranch()’, ‘getRightBranch()’ and optionally setParent().
  252.  
  253.     Input:
  254.         sortedList: sorted list, any data structure with ‘pop(0)’ method,
  255.             which removes and returns the leftmost element of the list. The
  256.             easiest thing to do is to use a list for the sorted
  257.             list.
  258.         start: int, start index, on initial call set to 0
  259.         end: int, on initial call should be set to len(sortedList)
  260.     Output:
  261.         root node of type binaryTree if the supplied list has 2 or more values,
  262.             or None.
  263.            
  264.     Note:
  265.         The sortedList list is destroyed during the process.
  266.        
  267.     References:
  268.         The original python implementation used a sorted "linked" list found here:
  269.             http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
  270.         Based on an original solution in C found here:
  271.             http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
  272.     """
  273.     if start >= end:
  274.         return None
  275.     middle = (start + end) // 2
  276.     node = buildBalancedTree(sortedList, start, middle)
  277.     root = binaryTree(sortedList.pop(0))
  278.     root.setLeftBranch(node)
  279.     if root.getLeftBranch():
  280.         root.getLeftBranch().setParent(root)   
  281.     root.setRightBranch(buildBalancedTree(sortedList, middle+1, end))
  282.     if root.getRightBranch():
  283.         root.getRightBranch().setParent(root)     
  284.     return root     
  285.  
  286.  
  287. def buildUnbalancedTree(unsortedList, rootValue):
  288.     """
  289.     Build an unbalanced binary search tree
  290.     Input: An unsorted list of key values to generate a tree,
  291.            The root key value, a member of the unsortedList.         
  292.     Output: rootNode when rootValue was found in unsortedList, otherwise return None.           
  293.                          
  294.     Notes:
  295.         The unsortedList list is destroyed during the process.
  296.         The nodes will be inserted into the tree using unsortedList list from left to right,
  297.             Uses the binaryTree.insert() method.
  298.     """
  299.     if rootValue not in unsortedList:
  300.         return None
  301.     rootIndex = unsortedList.index(rootValue)
  302.     rootNode = binaryTree(unsortedList[rootIndex])
  303.     unsortedList.remove(unsortedList[rootIndex])
  304.     while len(unsortedList):           
  305.         rootNode.insert(unsortedList[0])
  306.         unsortedList.remove(unsortedList[0])
  307.     return rootNode

Python class: visualizeTree.py

 

The visualization is carried out using a class called visualizeTree along with its included three helper functions DFS(), DFSOrdered() and BFS() for searching with animation using depth first or breadth first. The code produces a series of PNG images as a sequence in a subdirectory called vidImages. The code ends with a visual display of the last PNG image.

The python code uses the pyDot module to interface with GraphViz: both free and open source software. More details are described in the reference section of this article.

code=python
  1. """
  2. File: visualizeTree.py
  3.  
  4. Support Module for: Animate a Binary Search Tree using Python, pyDot, GraphViz
  5.  
  6. Project home: http://www.embeddedcomponents.com/blogs/2013/12/visualizing-software-tree-structures/
  7.  
  8. Developed by Ron Fredericks, Video Technologist, at LectureMaker LLC, http://www.LectureMaker.com
  9.     MIT License, Copyright (c) 2013, Ron Fredericks
  10.     Free to use following these terms: http://opensource.org/licenses/MIT 
  11.  
  12. Revision 3: 1/5/2014
  13.  
  14. #############################################################
  15. # Class visualizeTree
  16. #############################################################
  17.  
  18. Graph tree as a png file, and generate a sequence of images to animate a search.
  19.    
  20.     A tree node must provide these methods for this class to work:
  21.         getValue()
  22.         getLeftBranch()
  23.         getRightBranch()
  24.    
  25.     A tree must provide the root node for this class to work.                                         
  26.  
  27. External search functions included:
  28.     DFS()         - animate a search using depth first search
  29.     DFSOrdered()  – animate an ordered search using depth first search   
  30.     BFS()         - animate a search using breath first search
  31.    
  32. Public drawing methods:
  33.     sketchTree()          – draw a tree 
  34.     searchTree()          – search a tree (using a search function as described above), with animated trail of search
  35.     setVidFrames()        – number of png images to generate for each step in the video
  36.     updateGraph()         - generate a png image
  37.     appendVisualizeList() – add a png image name to a list for use with "showVideo" class         
  38. """
  39.  
  40. import pydot
  41.  
  42. # History:
  43. #   Initial project published on 12/11/2013
  44. #
  45. #   Rev 1: 12/16/2013
  46. #       1) Improve automated tree graphic image design so that no node is displayed directly below its parent.
  47. #            a) add invisible nodes, and invisible edges as placeholders to replace leaves that are not in the tree definition,
  48. #            b) change the default weight of edges to zero, so that displayed trees have freedom to spread out on the canvas.
  49. #       2) Redesign the draw() method to support automated inclusion of invisible nodes when a left or right sibling is missing from tree,
  50. #           remove automated display of "root", "node", and "leaf" in the node label.
  51. #       3) Redesign search routines BFS, and DEF so that drawing of graphic image information is not mixed in.
  52. #            Now new search routines can be designed solely on the merits of search.
  53. #       4) Add a new search routine: DFSOrdered.
  54. #       5) Add a new drawing routine: sketchTree.
  55. #           This routine adds the drawing information previously mixed into the search routines.
  56. #           Use this routine once to draw the full tree image during initialization.
  57. #       6) Change method blinkNodeTraversed color scheme to show a history of nodes searched in a new color
  58. #
  59. #   Rev 2: 12/23/2013
  60. #       1) Clean up PNG image display code.
  61. #       2) Improve video scaling:
  62. #            a) support large trees,
  63. #            b) support HD video during graph generation for 1920 x 1080 pixel size (corresponding changes made to FFmpeg script).
  64. #
  65. #   Rev 3: 1/4/2014
  66. #       1) Create visualizeTree.py module to clarify and shorten original project code.
  67. #       2) Include special case to support drawing a one node tree: see draw(), and sketchTree() for details.
  68. #       3) Create new visualizeList[] list to hold a subset of images generated by visualizeTree() class,
  69. #            to display using a new interactive Tkinter Slideshow() class.
  70. #       
  71.  
  72.  
  73. class visualizeTree(object):
  74.     def __init__(self, fileDir, fileName=‘bst_graph’, fileExt=‘.png’, vidFrames=1, fileCount=0):
  75.         self.fileDir = fileDir      # string, full directory path to where image sequence files will be stored
  76.         self.fileName = fileName    # string, base name of the file
  77.         self.fileExt = fileExt      # string, image file extension (currently ".png" is the only supported type)
  78.         self.vidFrames = vidFrames  # integer, a counter used generate duplicate copies of the PNG image files,
  79.                                     #   a way to stretch the video time line.
  80.         self.fileCount = fileCount  # integer, first number to use with generate sequenced image files.                                   
  81.        
  82.         self.treeList = []       # storage for the DFS or BFS tree search as a queue or stack
  83.         self.nodeNames = {}      # store each node name (key) with each node’s pyDot object (value), used by draw() method to ensure each node is drawn once
  84.         self.fullFileName = ""   # store the current full file name for png images
  85.        
  86.         self.visualizeList = []  # hold unique png files for Tkinter display
  87.        
  88.         self.initGraph(graph_type=‘digraph’, nodesep=.5, pad=.3, size="19.2, 10.1")
  89.         self.setNodeDefaults(style="filled", fillcolor="grey", shape="circle")
  90.         self.setEdgeDefaults(color="blue", arrowhead="vee")
  91.        
  92.     def initGraph(self, **kwargs):           
  93.         # Initialize a directional graph
  94.         #     Dot attributes:
  95.         #     graph_type = "graph" (edges drawn as lines)| "digraph" (edges drawn as arrows)
  96.         #     rankdir= "TB", "LR", "BT", "RL", corresponding to directed graphs drawn from top to bottom, from left to right, from bottom to top, and from right to left, respectively.
  97.         #     ranksep=float_value: rank separation in fraction of an inch 0.75 default, minimum vertical distance between nodes of equal rank
  98.         #     nodesep=float_value: node separation in fraction of an inch 0.25 default, minimum horizontal distance between nodes of equal rank
  99.         #     size = "string_value width, string_value height" in inches. Example: size="4, 8"
  100.         #     dpi=300 for better image quality, or dpi=96 for default value
  101.         #     optional layout="neato" | "sfpd" | "fpd" | "twopi" | "circo" to create a differently style for graph
  102.         #     pad=float_value for both width and height of pad around graph margins, in inches (.3 seems to be a good value)
  103.         #     bgcolor="red" set the background color
  104.         #     label="hello" set a text label just below the graph
  105.         self.graph = pydot.Dot(**kwargs)
  106.  
  107.     def setNodeDefaults(self, **kwargs):       
  108.         # Set default node attributes
  109.         #     Node attributes:
  110.         #     style = ‘filled’ | ‘invisible’
  111.         #           Many more options here: http://www.graphviz.org/doc/info/attrs.html#d:peripheries
  112.         #     shape = ‘box’ | ‘ellipse’ | ‘circle’ | ‘point’ | ‘triangle’
  113.         #           Many more shapes here: http://www.graphviz.org/doc/info/shapes.html
  114.         #     fillcolor = "grey" for example, the color of the shape inside
  115.         #     color = "red" for example, the color of the shapes outer border (or borders with ‘doublecircle’)
  116.         #     height and width float_value inches, for example: height=1.5, width=1.5
  117.         #     text control: ‘fontcolor’, ‘fontsize’, ‘label’, ‘fontname’, 
  118.         self.graph.set_node_defaults(**kwargs)   
  119.  
  120.     def setEdgeDefaults(self, **kwargs):       
  121.         # Set edge attributes
  122.         #     Edge attributes:
  123.         #     style     = ‘dashed’ | ‘dotted’ | ‘solid’ | ‘invis’ | ‘bold’
  124.         #     arrowhead = ‘box’ | ‘crow’ | ‘diamond’ | ‘dot’ | ‘inv’ | ‘none’ | ‘tee’ | ‘vee’
  125.         #     place a label: label="and back we go again", labelfontcolor="#009933", fontsize="10.0"
  126.         #     Adjust weighted flexibility in edge drawings: weight="0" for maximum flex, "3" for
  127.         #     minlen=2 minimum edge length in inches (default is 1
  128.         #     weight="0" to "100"
  129.         self.graph.set_edge_defaults(**kwargs)       
  130.      
  131.     def setVidFrames(self, vidFrames):
  132.         # Method to control the number of duplicate png images to generate (ie stretch or shrink video time)         
  133.         self.vidFrames = vidFrames
  134.  
  135.     def searchTree(self, root, searchMethod, find=None):
  136.         # Method to search a binary tree
  137.         # Input:
  138.         #     searchMethod is a helper function that defines the type of search to perform,
  139.         #        current examples implemented: DFS, BFS, and DFSOrdered
  140.         #     find is string representing the node to search and highlight, or None to display full binary tree
  141.         # Output:
  142.         #     True if node is found, or False if node is not found, or False when drawing the full tree (not searching)         
  143.         self.treeList = [root]
  144.         while len(self.treeList) > 0:
  145.             node = self.treeList.pop(0)
  146.             if node!=None:
  147.                 #print str(node) # activate to display nodes searched when debug needed
  148.                 if find==str(node):
  149.                     self.highlightNodeFound(str(node))
  150.                     return True
  151.                 elif find!=None:
  152.                     self.blinkNodeTraversed(str(node))           
  153.                 searchMethod(node, self.treeList, find, self.draw)   
  154.         return False
  155.  
  156.     def draw(self, parent_name, child_name=None, fill_color="grey", style_type=‘filled’):
  157.         # Method to draw a node and an edge of a Binary Tree
  158.         # Input:
  159.         #   parent_name is a string lable identifying the parent node to draw (if not drawn already)
  160.         #   child_name is a string lable identifying the child node to draw (or None, for a one node tree)
  161.         #   fill_color is the color to fill nodes drawn
  162.         #   style_type is either "filled" for normal drawing of tree nodes, or "invisible" for drawing nodes not part of tree         
  163.         if not child_name:
  164.             # Draw a tree with only one node
  165.             self.nodeNames[parent_name] = pydot.Node(parent_name, label=parent_name, fillcolor=fill_color, style=style_type)
  166.             self.graph.add_node(self.nodeNames[parent_name])
  167.             return           
  168.                                      
  169.         if style_type=="invisible":
  170.             # save original edge defaults
  171.             weight_ = "100"
  172.             saveEdgeDefaults = self.graph.get_edge_defaults()[0]
  173.             self.graph.set_edge_defaults(style=style_type, color="white", arrowhead="none")  # comment during debug
  174.             ###fill_color="#6699cc"  # debug, display invisible edges and nodes as light blue
  175.             ###style_type="filled"   # debug, display invisible edges and nodes as light blue 
  176.         else:
  177.             weight_ = "3"
  178.         edge = pydot.Edge(parent_name, child_name, style=style_type, weight=weight_)
  179.         self.graph.add_edge(edge) 
  180.         if style_type=="invisible":
  181.             # restore original edge defaults
  182.             self.graph.set_edge_defaults(**saveEdgeDefaults)       
  183.  
  184.         if not self.nodeNames:
  185.             # root node identified (the top most tree element)
  186.             self.nodeNames[parent_name] = pydot.Node(parent_name, label=parent_name, fillcolor=fill_color, style=style_type)
  187.             self.graph.add_node(self.nodeNames[parent_name])
  188.         if (parent_name not in self.nodeNames):
  189.             # node (a tree element with leaves) identified       
  190.             self.nodeNames[parent_name] = pydot.Node(parent_name, label=parent_name, fillcolor=fill_color, style=style_type)
  191.             self.graph.add_node(self.nodeNames[parent_name])
  192.         if child_name not in self.nodeNames:
  193.             # leaf element identified (a parent with no children)
  194.             self.nodeNames[child_name] = pydot.Node(child_name, label=child_name, fillcolor=fill_color, style=style_type)
  195.             self.graph.add_node(self.nodeNames[child_name])
  196.                      
  197.     def highlightNodeFound(self, node):
  198.         # Method to animate the found node in a search tree         
  199.         self.graph.add_node(pydot.Node(node, fillcolor="green"))
  200.         self.updateGraph()
  201.         self.appendVisualizeList()
  202.        
  203.     def appendVisualizeList(self):
  204.         self.visualizeList.append(self.fullFileName)   
  205.  
  206.     def blinkNodeTraversed(self, node):
  207.         # Method to animate a node being traversed in a search tree 
  208.         self.graph.add_node(pydot.Node(node, fillcolor="red"))
  209.         self.updateGraph()
  210.         self.appendVisualizeList()
  211.         # use a redish grey color #cc9999 to show a breadcrumb to searched nodes in tree
  212.         self.graph.add_node(pydot.Node(node, fillcolor="#cc9999"))
  213.         self.updateGraph()       
  214.              
  215.     def setFileName(self):
  216.         # Method to set the file name based on:
  217.         #    directory, name, count and extension in support of our ffmpeg png to video batch file 
  218.         self.fullFileName = self.fileDir + self.fileName + ‘%05d’ % self.fileCount + self.fileExt
  219.    
  220.     def getFileName(self, count=None):
  221.         if count == None:
  222.             # Method to get the current full file name         
  223.             return self.fullFileName
  224.         else:
  225.             return self.fileDir + self.fileName + ‘%05d’ % count + self.fileExt
  226.    
  227.     def getFileCount(self):
  228.         # Method to return maximum file count: the number of png images created
  229.         return self.fileCount
  230.    
  231.     def updateGraph(self):
  232.         # Method to write multiple copies of the same png image in support of ffmpeg png to video batch file       
  233.         for i in range(0, self.vidFrames):
  234.             self.fileCount += 1
  235.             self.setFileName()
  236.             self.graph.write_png(self.fullFileName)   
  237.  
  238.  
  239. # Helper search functions for use with visualizeTree’s method named "searchTree()"
  240. # ——————————————————————————–
  241.  
  242. def DFS(node, queue, find=None, draw=None):
  243.     # Depth First Search helper function for binaryTree.searchTree():
  244.     #    Start at root followed by all nodes from top to bottom, then left to right,
  245.     #       until key value found or queue exhausted.
  246.     # Input:
  247.     #     node: Current node in binary tree,
  248.     #     queue: First in First out (FIFO) ,
  249.     #     find and draw: Unused.
  250.     if node.getRightBranch():
  251.         queue.insert(0, node.getRightBranch())
  252.     if node.getLeftBranch():
  253.         queue.insert(0, node.getLeftBranch())   
  254.            
  255. def DFSOrdered(node, queue, find, draw=None):
  256.     # Ordered Depth First Search helper function for binaryTree.searchTree():
  257.     #    Start at root followed by selected nodes from top to bottom, then left to right,
  258.     #       that meet our find requirment, until key value found or leaf node examined.
  259.     # Input:
  260.     #     node: Current node in binary tree,
  261.     #     queue: First in First out (FIFO) ,
  262.     #     find: the string value we are searching for in a tree,
  263.     #     draw: Unused.       
  264.     if node:                                                       
  265.         if node.getRightBranch() and find > str(node.getValue()):
  266.             queue.insert(0, node.getRightBranch())
  267.         if node.getLeftBranch() and find < str(node.getValue()):
  268.             queue.insert(0, node.getLeftBranch())       
  269.  
  270. def BFS(node, stack, find=None, draw=None):
  271.     # Breadth First Search helper function for binaryTree.searchTree():
  272.     #    Start at root followed by all nodes from left to right, then top to bottom,
  273.     #       until key value found or queue exhausted.
  274.     # Input:
  275.     #     node: Current node in binary tree,
  276.     #     stack: Last in First out (LIFO) ,
  277.     #     find and draw: Unused.     
  278.     if node.getLeftBranch():
  279.         stack.append(node.getLeftBranch())       
  280.     if node.getRightBranch():
  281.         stack.append(node.getRightBranch())         
  282.  
  283. # Sketch complete tree
  284. # makes calls to visualizeTree’s draw() method to graph edge and node elements
  285. # Input: node in binary tree, stack for depth first drawing
  286. # Unused: find
  287. def sketchTree(node, stack, find=None, draw=None):
  288.     if node.getLeftBranch():
  289.         draw(str(node), str(node.getLeftBranch()))
  290.         stack.append(node.getLeftBranch())
  291.         if node.getRightBranch():
  292.             # insert invisible third node in-between left and right nodes
  293.             draw(str(node), ":"+str(node), style_type="invisible")
  294.     elif node.getRightBranch():
  295.         # draw any missing left branches as invisible nodes/edges with dummy unique labels
  296.         draw(str(node), ":"+str(node), style_type="invisible")
  297.     if node.getRightBranch():
  298.         draw(str(node), str(node.getRightBranch()))
  299.         stack.append(node.getRightBranch())     
  300.     elif node.getLeftBranch():
  301.         # draw any missing right branches as invisible nodes/edges with dummy unique labels
  302.         draw(str(node), ";"+str(node), style_type="invisible")
  303.     if not node.getLeftBranch() and not node.getRightBranch() and not node.getParent():
  304.         # special case: draw a tree with only one node
  305.         draw(str(node))

Plython class: slideShow.py

 

The slide show code is built around a TK update() loop with event driven buttons to control the presentation of png images located in the playSlides() method. Each cycle of the idle loop sleeps for a fraction of a second set by public attribute: idleTimeSlice. On my computer with a 0.05 second sleep state per idle loop, the fastest playback clocks in at around 0.09 seconds per image while running from my Canopy 64-bit development environment. This speed is more than enough to generate a flicker free “flip book” visual experience. I have found that a playback speed ranging from from .35 to 1. second per png image works well. The playback speed is not set with the idle loop time slice, instead a list of play times can be set using the setSpeedList() method. Perhaps other developers may find this stand-alone class useful for animation or photo slide show projects of their own.

Python 2.7 class slideShow() being used as an animation tool for this project.

Python 2.7 class slideShow() being used as an animation tool for this project.

code=python
  1. """
  2. File: slideShow.py
  3.  
  4. Support Module for: Animate a Binary Search Tree using Python, and TK graphics
  5.  
  6. Project home: http://www.embeddedcomponents.com/blogs/2013/12/visualizing-software-tree-structures/
  7.  
  8. Developed by Ron Fredericks, Video Technologist, at LectureMaker LLC, http://www.LectureMaker.com
  9.     MIT License, Copyright (c) 2013, Ron Fredericks
  10.     Free to use following these terms: http://opensource.org/licenses/MIT 
  11.  
  12.  
  13.  
  14. ################################################
  15. # Class slideShow
  16. ################################################
  17.  
  18. Animate a sequence of images in a TK window, assumes all images are the same size.                         
  19.  
  20. Public methods:
  21.     slideShow(rootTk)  - instantiate slide show class
  22.     setImageScaling()  - update default image scale factor
  23.     setSpeedList()     - update default list of playback speeds
  24.     setColorScheme()   - update default button color scheme
  25.     setIdleTimeSlice() - update defalut sleep time during idle loop
  26.     playSlides()       - launch a slide show   
  27. """
  28.  
  29. # Import TK graphics packages.
  30. import Image, ImageTk
  31.  
  32.  
  33. # History:
  34. #   Initial project published on 12/11/2013
  35. #
  36. #   Rev 1: 12/16/2013
  37. #       1) Improve comments for accuracy.
  38. #
  39. #   Rev 2: 12/23/2013
  40. #       1) Improve comments for accuracy.
  41. #
  42. #   Rev 3: 1/4/2014
  43. #       1) Create (this) slideShow.py module to clarify and shorten original project code.
  44. #       2) Turn single image display into slideShow() class to display multiple images.
  45. #   Rev 3a: 1/10/2014
  46. #       1) Improve clarity of idle loop
  47. #       2) Improve clarity of performance display in main playback loop
  48.  
  49.  
  50. class slideShow(object):
  51.     def __init__(self, rootTk):
  52.        
  53.         # Root for TK graphics (example: rootTk = Tkinter.Tk())
  54.         self.rootTk = rootTk
  55.         # Text title for TK graphics playback window.
  56.         self.mainTitle = "Slide Show"
  57.         # List of images to play during slide show (example: playList = ["c:\tmp\im1.png", "c:\tmp\im2.png"...]).
  58.         self.playList = []
  59.         # Activate (set True) to display performance of main timing loop to screen (standard output).
  60.         self.testPerformance = False       
  61.                
  62.         # Polling loop controls for playSlides() method...         
  63.         self.speedList = [.01, .05, .1, .35, .5, 1., 2.]  # A sorted list of wait times between images to play during a slide show,
  64.                                                           #   where speedList pointer controlled by "Faster" and "Slower" buttons.
  65.         self.speedPointerDefault = 3                      # The default wait time (during startup and after a reset) index within speedList[].
  66.                                                           #   Recommended setting (integer): len(speedList)/2
  67.         self.idleTimeSlice = .01/2.1                      # Idle loop time slice between Tkinter updates.
  68.                                                           #   Recommend setting based on Nyquist Interval (float): min(.1, speedList[0]/2.1),
  69.                                                           #   and the need for python code associated with button activity to be responsive to user.
  70.        
  71.         # Button colors...
  72.         self.bg_color_f = "#ccffff"  # Background color for buttons.
  73.         self.bg_color_r = "#ffffcc"  # Background color for play/pause button and reverse/normal buttons
  74.                                      #    when user selects reverse playback option.
  75.         self.fg_color_f = "blue"     # Text color for buttons.
  76.         self.fg_color_r = "black"    # Text color for play/pause button and reverse/normal buttons
  77.                                      #    when user selects reverse playback option.                                     
  78.         self.exitButtonText = "Quit" # Text for use in exit button, use "Next" (for example),
  79.                                      #    when cascading several slide shows together.
  80.                                      
  81.         # Image scaling to fit within monitor...
  82.         self.w_screen = None         # Width of screen: use None for auto-detection and auto-scaling,
  83.                                      #   otherwise set to maximum png width in pixels plus 20 for borders (controller width only takes 420).
  84.         self.h_screen = None         # Height of screen: use None for auto-detection and auto-scaling,
  85.                                      #   otherwise set to maximum png height in pixels plus 70 for borders, title bar, and buttons (controller height only takes 66).               
  86.        
  87.     def setImageScaling(self, wMax, hMax):
  88.         # Set maximum width and height values in pixels for png images.
  89.         #    Auto-scaling will take place when images are larger than these values.
  90.         self.w_screen = float(wMax)
  91.         self.h_screen = float(hMax)
  92.        
  93.     def setSpeedList(self, speedList, speedPointerDefault):
  94.         # Update the default list of playback times offered by the "faster" / "slower" buttons
  95.         assert len(speedList) >= 3, "List should be 3 or floating point times. Example: speedList = [.01, .05, .1, .35, .5, 1., 2.]"
  96.         assert speedPointerDefault < len(speedList), "Default time pointer should be an integer: between 0 and len(speedList) - 1"
  97.         self.speedList = speedList       
  98.         self.speedPointerDefault = speedPointerDefault   
  99.        
  100.     def setIdleTimeSlice(self, idleTimeSlice):
  101.         # Update the default idle loop time slice. Use faster time for more responsive buttons. Use slower time for slower computers.
  102.         assert type(idleTimeSlice) == float, "Wait time between rootTk.update() calls should be a float. Example: idleTimeSlice = .05"
  103.         self.idleTimeSlice = idleTimeSlice   
  104.        
  105.     def setColorScheme(self, bg_color_f="#ccffff", bg_color_r="#ffffcc", fg_color_f="blue", fg_color_r="black")
  106.         # Set text and background colors for buttons. The "_f" colors are used for initial buttons, and controller title.
  107.         #    The "_r" colors are used for revere playback on "play/pause" and "normal" buttons.
  108.         self.bg_color_f = bg_color_f
  109.         self.bg_color_r = bg_color_r                                     
  110.         self.fg_color_f = fg_color_f   
  111.         self.fg_color_r = fg_color_r   
  112.                                                                                                                                                                                                                                                                                                                                            
  113.    
  114.     def setExitFlag(self):
  115.         # Exit play loop when user clicks operating system's window exit button, or slideShow's "Quit" button.
  116.         # manage WM_DELETE_WINDOW event
  117.         self.closeViewer = True
  118.         self.measureValid = False
  119.        
  120.     def tooglePlayPause(self):
  121.         # Modify play loop for playback or pause. Auto pause when playback comes to an end.
  122.         self.measureValid = False
  123.         if self.playFlag:
  124.             self.Play.configure(text = ' Play  ')
  125.             self.playFlag = False
  126.         elif not self.playFlag and not self.reverseFlag and self.imageCount < self.imageCountMax:
  127.             # forward play should only take place when imageCount (frame count) is not already at the end
  128.             self.Play.configure(text = 'Pause')
  129.             self.playFlag = True
  130.         elif not self.playFlag and self.reverseFlag and self.imageCount > 0:
  131.             # reverse play should only take place when imageCount (frame count) is not already at the begining
  132.             self.Play.configure(text = 'Pause')
  133.             self.playFlag = True   
  134.         else:
  135.             # Auto pause when playback comes to an end.
  136.             self.toogleReverse()
  137.              
  138.     def incrementFaster(self):
  139.         # Modify play loop for shorter delay between images.   
  140.         self.speedPointerCurrent = max(0, self.speedPointerCurrent-1)     
  141.         self.setTime = self.speedList[self.speedPointerCurrent]
  142.         self.updateSpeedButtons()
  143.        
  144.     def incrementSlower(self):
  145.         # Modify play loop for longer delay between images.
  146.         self.speedPointerCurrent = min(len(self.speedList)-1, self.speedPointerCurrent+1)     
  147.         self.setTime = self.speedList[self.speedPointerCurrent]
  148.         self.updateSpeedButtons()
  149.  
  150.     def updateSpeedButtons(self):
  151.         # Helper function for "faster" and "slower" buttons to display correct text with each button.
  152.         self.measureValid = False
  153.         tmpText = '{:7.2f}'.format(self.setTime)
  154.         if self.testPerformance == True:
  155.             print "Update time:", tmpText         
  156.         self.Speed.configure(text = tmpText)
  157.         if self.speedPointerCurrent == len(self.speedList)-1:
  158.             self.Slower.configure(text = 'Slowest')
  159.         else:
  160.             self.Slower.configure(text = 'Slower')   
  161.         if self.speedPointerCurrent == 0:
  162.             self.Faster.configure(text = 'Fastest')
  163.         else:
  164.             self.Faster.configure(text = 'Faster')     
  165.          
  166.     def toogleReverse(self):
  167.         # Modify play loop for forward or reverse playback.
  168.         #    Update play/pause and reverse/normal button color scheme for improved user awareness of current state.
  169.         self.measureValid = False
  170.         if self.reverseFlag:
  171.             self.reverseFlag = False
  172.             self.Reverse.configure(text = 'Reverse', bg=self.bg_color_f, fg=self.fg_color_f)
  173.             self.Play.configure(bg=self.bg_color_f, fg=self.fg_color_f)
  174.         else:
  175.             self.reverseFlag = True
  176.             self.Reverse.configure(text = 'Normal', bg=self.bg_color_r, fg=self.fg_color_r)
  177.             self.Play.configure(bg=self.bg_color_r, fg=self.fg_color_r)
  178.    
  179.     def doReset(self):
  180.         # Modify play loop to initial state.
  181.         self.measureValid = False 
  182.         self.resetJustHappened = True
  183.         self.setTime = self.speedList[self.speedPointerDefault] 
  184.         self.speedPointerCurrent = self.speedPointerDefault
  185.         self.updateSpeedButtons()
  186.         if self.reverseFlag:
  187.             self.toogleReverse()
  188.         if self.playFlag:   
  189.             self.tooglePlayPause()
  190.         if self.imageCount != 0
  191.             self.imageCount = 0
  192.  
  193.     def scaleFactor(self):       
  194.         # Determine visual environment, and generate width/height scale dimensions as needed.
  195.         # Output: Return tuple: updated width and height, and flag to scale or not.
  196.        
  197.         # Get screen size. Leave some room for boarders and buttons, use float values for scale calculations.
  198.         if not self.w_screen:
  199.             self.w_screen = self.rootTk.winfo_screenwidth() - 20
  200.            
  201.         if not self.h_screen:
  202.             self.h_screen = self.rootTk.winfo_screenheight() - 70
  203.         # Get width, height, and then initialize display using initial png image in sequence
  204.         image = Image.open(self.playList[0])
  205.         w = image.size[0]
  206.         h = image.size[1]
  207.        
  208.         scaleFactorW = 1.
  209.         scaleFactorH = 1.
  210.         if w > self.w_screen:
  211.             scaleFactorW = w / self.w_screen
  212.         if h > self.h_screen:
  213.             scaleFactorH = h / self.h_screen
  214.            
  215.         # Find largest scale factor, a scale factor below 1.0 would cause image to be magnified.
  216.         scaleFactor = max(1. , max(scaleFactorW, scaleFactorH))
  217.         w = int(w / scaleFactor)
  218.         h = int(h / scaleFactor)
  219.        
  220.         # Determine if scaling should be done on images.
  221.         useScaleFactor = False
  222.         if scaleFactor != 1.:
  223.             useScaleFactor = True
  224.        
  225.         #Return tuple: updated width and height, and flag to scale or not.
  226.         return (w, h, useScaleFactor)   
  227.  
  228.        
  229.     def playSlides(self, playList, mainTitle="Slide Show", exitButtonText="Quit", testPerformance=False):
  230.         # Main playback loop
  231.        
  232.         self.initPrivateProps()
  233.          
  234.         assert len(playList) > 0, 'Error: playList is a ist of images to play during slide show (example: playList = ["c:\tmp\im1.png", "c:\tmp\im2.png"...])'
  235.         self.playList = playList
  236.        
  237.         self.mainTitle = mainTitle
  238.        
  239.         assert type(exitButtonText) == str, "Error: Exit button text should be passed as a string value"
  240.         self.exitButtonText = exitButtonText
  241.        
  242.         self.testPerformance= testPerformance       
  243.        
  244.         assert self.rootTk and self.rootTk.winfo_exists(), "Error: Tkinter root not valid (initialization example: s = slideShow(Tkinter.Tk(), 'Title')"
  245.        
  246.         self.rootTk.title(self.mainTitle)                           # Place title in top window boarder.
  247.         self.speedPointerCurrent = self.speedPointerDefault         # Current playback speed set to default time index in speedList[].
  248.         self.setTime = self.speedList[self.speedPointerCurrent]     # Initialize time to wait between images during playback.
  249.         self.imageCountMax = len(self.playList) - 1                 # Maximum image count [0 to n].               
  250.        
  251.         wScale, hScale, useScale = self.scaleFactor()               # Calculate image scale details
  252.              
  253.         # group buttons together tightly using this frame
  254.         frame = Tkinter.Frame(self.rootTk, width=100)
  255.         frame.grid(row = 1, column=1)
  256.        
  257.         # manage user buttons
  258.         #---------------------
  259.        
  260.         # place menu name by the buttons
  261.         msg = Tkinter.Label(frame, text="Controller: ", font=("Helvetica", 14), fg=self.fg_color_f)
  262.         msg.grid(row = 1, column = 0)
  263.        
  264.         # define play/pause button
  265.         self.Play = Tkinter.Button(frame, text = " Play  ", bg=self.bg_color_f, fg=self.fg_color_f, command = self.tooglePlayPause)
  266.         self.Play.grid(row = 1, column = 1)
  267.        
  268.         # define play faster and slower buttons
  269.         self.Faster = Tkinter.Button(frame, text = "Faster", bg=self.bg_color_f, fg=self.fg_color_f, command = self.incrementFaster, width=6)
  270.         self.Faster.grid(row = 1, column = 2)
  271.         self.Speed = Tkinter.Label(frame, text = '{:7.2f}'.format(self.setTime), fg=self.fg_color_f, relief="sunken", borderwidth=2)
  272.         self.Speed.grid(row = 1, column = 3)
  273.         self.Slower = Tkinter.Button(frame, text = "Slower", bg=self.bg_color_f, fg=self.fg_color_f, command = self.incrementSlower, width=6)
  274.         self.Slower.grid(row = 1, column = 4)
  275.        
  276.         # define reverse play button
  277.         self.Reverse = Tkinter.Button(frame, text = "Reverse", bg=self.bg_color_f, fg=self.fg_color_f, command = self.toogleReverse)
  278.         self.Reverse.grid(row = 1, column = 5)
  279.        
  280.         # define reset button
  281.         Reset = Tkinter.Button(frame, text = "Reset", bg=self.bg_color_f, fg=self.fg_color_f, command = self.doReset)
  282.         Reset.grid(row = 1, column = 6)
  283.        
  284.         # define quit button, and link window exit button to it
  285.         self.rootTk.protocol("WM_DELETE_WINDOW", self.setExitFlag)
  286.         Exit = Tkinter.Button(frame, text = self.exitButtonText, bg=self.bg_color_f, fg=self.fg_color_f, command = self.setExitFlag)
  287.         Exit.grid(row = 1, column = 7)
  288.              
  289.         # Initialize main polling loop.
  290.         self.doReset()
  291.         self.resetJustHappened = False   
  292.         startMeasureTime = 0# measureValid will is initialized to False during doReset()
  293.        
  294.         # Main polling loop.
  295.         while True:         
  296.             if self.testPerformance == True:
  297.                 if self.measureValid:
  298.                     deltaTime = time.clock() - startMeasureTime
  299.                     print "deltaTime:", '{:2.5f}'.format(deltaTime), "imageCount:", "%02d" % (self.imageCount)                 
  300.                 startMeasureTime = time.clock()
  301.                 self.measureValid = True
  302.            
  303.             # Exit slide show if a quit button or exit window button was pressed.
  304.             if self.closeViewer:
  305.                 break
  306.                        
  307.             # Display an image.
  308.             f = self.playList[self.imageCount]
  309.             image = Image.open(f)
  310.             if useScale: image = image.resize((wScale,hScale),Image.ANTIALIAS)
  311.             # Use alternate image storage to avoid flicker.
  312.             if self.imageCount % 2 == 0:
  313.                 tkpi = ImageTk.PhotoImage(image)       
  314.                 label_image = Tkinter.Label(self.rootTk, image=tkpi, relief="sunken")
  315.                 label_image.grid(row=0, columnspan=6)             
  316.             else:
  317.                 tkpi2 = ImageTk.PhotoImage(image)       
  318.                 label_image2 = Tkinter.Label(self.rootTk, image=tkpi2, relief="sunken")
  319.                 label_image2.grid(row=0, columnspan=6)
  320.             self.rootTk.update()             
  321.            
  322.             # Initialize wait time.       
  323.             idleLoopTimeInit = time.clock()
  324.             while True:
  325.                 # Idle polling loop. Wait for user controls, ellapsed time to next image, or end of slide show.
  326.                
  327.                 # update TK graphics thread.
  328.                 self.rootTk.update()
  329.                
  330.                 # Exit idle loop on quit/close
  331.                 if self.closeViewer:
  332.                     break             
  333.                 # Exit idle loop on reset
  334.                 if self.resetJustHappened:
  335.                     break
  336.                    
  337.                 # Skip idle loop on initial image.
  338.                 if self.playFlag:
  339.                     if self.imageCount == 0 and not self.reverseFlag:
  340.                         self.measureValid = False
  341.                         break
  342.                     elif self.imageCount == self.imageCountMax and self.reverseFlag:
  343.                         self.measureValid = False
  344.                         break
  345.                     else:
  346.                         if time.clock() - idleLoopTimeInit > self.setTime:
  347.                             # Re-initialize wait time unless playback is underway.       
  348.                             idleLoopTimeInit = time.clock()
  349.                             break
  350.                         # Update graphics display at least every idleTimeSlice seconds, even when we want to delay for a longer period of time.                                     
  351.                         time.sleep(self.idleTimeSlice)                                                     
  352.                
  353.             if self.imageCount >= self.imageCountMax and not self.reverseFlag:
  354.                 # Stop normal playback, update play/pause button text, and wait in a loop.
  355.                 self.tooglePlayPause()
  356.                 # Toogle reverse playback so the user can play the png images in reverse direction.
  357.                 self.toogleReverse()
  358.            
  359.             elif self.imageCount < = 0 and self.reverseFlag:
  360.                 # Stop reverse playback, update play/pause button text, and wait in a loop.
  361.                 self.tooglePlayPause()
  362.                 # Toogle reverse playback so the user can play the png images in forward direction.
  363.                 self.toogleReverse()
  364.                            
  365.             elif not self.resetJustHappened:
  366.                 # Normal playback by incrementing/decrementing the png image to display.
  367.                 if self.reverseFlag:
  368.                     self.imageCount -= 1
  369.                 else:
  370.                     self.imageCount += 1
  371.             else:
  372.                 # clear reset flag and return to main playback loop with all attributes reset
  373.                 self.resetJustHappened = False                   
  374.        
  375.     def initPrivateProps(self):                             
  376.         # Private attributes for play loop and interactive button management.                             
  377.         self.closeViewer = False
  378.         self.playFlag = False
  379.         self.Play = None
  380.         self.Reverse = None
  381.         self.reverseFlag = False
  382.         self.imageCount = 0       
  383.         self.measureValid = False
  384.         self.Speed = None
  385.         self.Faster = None
  386.         self.Slower = None
  387.         self.resetJustHappened = False

DOS Batch File png2mpg4.bat

 

Use this batch file to convert the PNG image sequence into a mpeg-4 video using the FFmpeg utility. This is a DOS / Windows script. A similar script can be generated for Mac OS X or Linux since the FFmpeg utility is available for these operating systems too.

code=dos
  1. @echo off
  2. echo Batch File encodes a sequence of png files into mpeg-4 video using FFmpeg
  3. :
  4. REM File name: png2mpg4.bat
  5. REM Ron Fredericks, LectureMaker LLC, http://www.LectureMaker.com
  6. REM Revision 1 12/23/2013: Now auto-scales and supports HD video at 1920 x 1080 pixels
  7. :
  8. REM Files of the form: bst_graph00001.png, counting up.
  9. REM Frame rate set to 1 seconds per frame on input and 12 fps on output.
  10. REM Output video will reside in the same directory as the PNG sequence images.
  11. REM Note the use of a double %% to encode sequence numbers in this batch file,
  12. REM      use only one % outside of the batch file.
  13. :
  14. REM ffmpg parameters used:
  15. REM     -f image2 forces input to image file demuxer, creating video from many images, following a pattern
  16. REM     -r 1 indicates reading input at 1 second for each png file
  17. REM     -start_number 00001 is the start number for the png file sequence
  18. REM     -i bst_graph%%05d.png is the input pattern for the png file image sequence (numbers are 5 digits long)
  19. REM     -b:v 5000k is a high quality bitrate for video on output
  20. REM     -vcodec mpeg4 is the video codec
  21. REM     -r 30 is the frame rate for the video on output
  22. REM     -vf scale=720:480 is a simple video filter to scale output to a normal size of 720x480
  23. REM     -vf scale="'if(gt(a,4/3),1920,-1)':'if(gt(a,4/3),-1,1280)'" is a more advanced video filter to scale output to 1920x1080 (HD)
  24. REM     -y overides output file without asking
  25. REM     movie.mp4 is the output file name
  26. :       
  27. @echo on
  28. cd .\vidImages
  29. ffmpeg -f image2 -r 1 -start_number 00001 -i bst_graph%%05d.png  -b:v 5000k -vcodec mpeg4 -r 30 -vf scale="'if(gt(a,4/3),1920,-1)':'if(gt(a,4/3),-1,1280)'" -y movie.mp4
  30. @echo off
  31. :
  32. ECHO.&ECHO.Press any key to end the application.&PAUSE>NUL&GOTO:EOF

Notes on Software Use

You can download the full source code from Github.com as a zip file, see reference section below.

To use this software, the pydot module must be installed into your python environment which is an interface to the popular GraphViz application. I recommend installing GraphViz before installing pydot because pydot installation will try to set up a path to GraphViz. I installed pydot first and had to configure my Windows path manually. These two modules are available for Windows, Mac OS and Linux.

Before running the main program, binarySearchTreeAnimationApp.py, create a subdirectory to store your temporary images. The variable name is "filedir". There is a windows example and a Mac OS example in the main program.

If you run the program from the IDE, make sure you are using a graphics friendly environment for TK. I use Enthought's Canaopy so I go into the Edit -> Preference -> Python tab and change PyLab backend from default of "interactive Qt" to "Inline (SVG)". Without this change, the program will just hang without showing the TK slide show window.

If you run the program from the command line as:
"python binarySearchTreeAnimationApp.py" then the TK graphics will work without changing the graphics backend in the IDE.

On the Mac, the play and reverse buttons will not change color when the user clicks on the reverse button. This is a common issue for many graphics packages, not just TK, in the Mac OS environment.

References

 

Get the software described here on GitHub: The python source and batch file can be downloaded from GitHub: https://github.com/RonFredericks/visualizeTree

pydot: a python interface to Graphvize's Dot language: https://code.google.com/p/pydot/

GraphViz: Graph visualization cross-platform program: http://www.graphviz.org/

Some more graphviz links:

graphviz gallery (crazy examples here!): http://www.graphviz.org/Gallery.php
graphviz documentation: http://www.graphviz.org/Documentation.php
graphviz documentation on attributes: http://www.graphviz.org/doc/info/attrs.html
Generating Graph Visualizations with pydot and Graphviz http://pythonhaven.wordpress.com/2009/12/09/generating_graphs_with_pydot/

FFmpeg: Cross-platform solution to record, convert and stream audio and video: http://www.ffmpeg.org/

Tkinter: standard python GUI: http://docs.python.org/2/library/tkinter.html

Image and ImageTk: the python image library: http://www.pythonware.com/products/pil/

align="left">GeSHi source code highlighting: An open source library: http://qbnz.com/highlighter/

The binaryTree class used in this software demo was taken from professor Eric Grimson's lecture series as part of MITx course 6.00.1x: http://www.edx.org

RXPF2THP4RWE

Technorati Tags: , , , , , , , , , , ,

Software Complexity and Big-O Notation

November 25th, 2013


Ron Fredericks writes: for the next submission to my new series on Python I thought I would share my notes on using Big-O notation.

Big O notation

Big O notation gives an upper bound on asymptotic growth of a function. It also represents worst case time complexity, or order of growth. This is a useful concept when choosing an algorithm or in evaluating the performance of software code. As a developer, your goal is to select an algorithm or develop code with the lowest software complexity. This post shows you how to analyze software to determine an estimation of execution time.
Get more details from wikipedia: Big O Notation

Computer science includes a range of common algorithms that have well known Big O complexities. Common algorithms include:

  • Searching
  • Sorting
  • Data structures
  • Heaps
  • Graphs

Follow this link to see a list of these algorithms with their associated time and space complexity: Big-O Cheat Sheet

Complexity classes

Below I list common levels of complexity from lowest to highest. I include a short description, and a sample Python function. In the source code, I identify the portion of the code that drives the Big O complexity.

O(1) constant running time

In the python modten function below there are no loops and no recursion. No matter the size of n, the worst case execution time will be a constant.

code=python
  1. def modten(n):
  2.     # The function timing does not depend on the size of n.
  3.     return n%10

O(log n) logarithmic running time

In the code below, line 9 “i = i / 10″, defines the Big O complexity. In this case each iteration of the while loop is reduced by “i/10″. So as the integer, i gets larger, the complexity of the algorithm grows at a rate of log_10 i.

Why is that?

We need to solve this problem to arrive at complexity:
10^Theta = i

Or how many times can one divide i by 10?
Answer: Theta = log_10 i

code=python
  1. def intToStr(i):
  2.      digits = ’0123456789′
  3.      if i == 0:
  4.           return ’0′
  5.      result =
  6.      while i > 0:
  7.           result = digits[i%10] + result
  8.           # Big O defined by this loop counter.
  9.           i = i/10
  10.      return result

O(n) linear running time

Example of linear complexity: O(len(s))

code=python
  1. def addDigits(s):
  2.      val = 0
  3.      # The function has one loop with s iterations
  4.      for c in s:
  5.           val += int(c)
  6.      return val

Example of linear complexity: O(n).
For worst case analysis, we assume n is a very large positive number.

code=python
  1. def factorial(n):
  2.      answer = 1
  3.      # The function has one loop with n iterations
  4.      while n > 1:
  5.           answer *= n
  6.           n -= 1
  7.      return answer

O(n log n) log-linear running time

The complexity of this program includes two functions:

  • Merge is O(len(L)) for comparisons
  • Merge is O(len(L1) + len(L2)) for copy operations
  • Merge function as a whole is O(len(L))
  • Mergesort is O(len(L))* number of calls to merge

The Big O complexity of the program will be based on the complexity of the function with the larger complexity – the Mergesort. The number of recursive calls to merge is like any other loop or O(log_2(L)) as indicated in the code’s comment. The Big O combination of the two segments of Mergesort is O(n log_2 n)

code=python
  1.  
  2. def merge(left, right, compare):
  3.      result = []
  4.      i,j = 0, 0
  5.      while i < len(left) and j < len(right):
  6.           if compare(left[i], right[j]):
  7.                result.append(left[i])
  8.                i += 1
  9.           else:
  10.                result.append(right[j])
  11.                j += 1
  12.      while (i < len(left)):
  13.           result.append(left[i])
  14.           i += 1
  15.      while (j < len(right)):
  16.           result.append(right[j])
  17.           j += 1
  18.      return result
  19.  
  20. def mergeSort(L, compare = operator.lt):
  21.      if len(L) < 2:
  22.           return L[:]
  23.      else:
  24.           # The L/2 assignment indicates a log2 (L) complexity for mergeSort
  25.           middle = int(len(L)/2)
  26.           left = mergeSort(L[:middle], compare)
  27.           right = mergeSort(L[middle:], compare)
  28.           return merge(left, right, compare)

O(n^c) polynomial running time

Select input arguments for worst case analysis. In this case, both L1 and L2 would be of equal size, and no value in either list would have matching values. In this case, both for loops would run through and examine each value in L1 would have to be compared with each value in L2. So complexity would be O(len(L1)*len(L2)), or quadratic complexity.

code=python
  1. def isSubset(L1, L2):
  2.      # each for loop on input counts towards Big O complexity
  3.      for e1 in L1:
  4.           matched = False
  5.                # each for loop on input counts towards Big O complexity
  6.                for e2 in L2:
  7.                     if e1 == e2:
  8.                          matched = True
  9.                          break
  10.                if not matched:
  11.                     return False
  12.      return True

O(c^n) exponential running time

In function below, for a set of size k, there are 2^k cases. Result is a Big O complexity of 2^n, or exponential complexity.

code=python
  1. def genSubsets(L):
  2.      res = []
  3.      if len(L) == 0:
  4.           return [[]]
  5.      smaller = genSubsets(L[:-1])
  6.      extra = L[-1:]
  7.      new = []
  8.      for small in smaller:
  9.           new.append(small+extra)
  10.      return smaller+new

References

Technorati Tags: , ,

Welcome to Python – New Blogging Initiative

November 16th, 2013


Ron Fredericks writes: I am taking on a new programming language for research and web development: Python.

I am impressed with the power of the language for processing speed, ease to program new ideas, large base of supported platforms, and the many freely available open source packages available.

I am using Enthought Canopy Express v: 1.1.0 (64-bit) as a programming environment on my windows 7 PC and Mac OS X computers.

I am using the edX MOOC platform for my initial training by professor Eric Grimson, MITx 6.00.1x as my jumpstart into learning the language titled “Introduction to Computer Science and Programming”

MIT OpenCourseware (OCW) offers a self-study program for learning Python based on the 2011 course 6.00sc taught by professor John Guttag: Introduction to Computer Science and Programming

Technorati Tags: , ,

Dual-Channel Digital Volume Control Circuit Simulation

January 11th, 2012


Ron Fredericks writes: In today’s post, I will demonstrate the value in using LTspice to simulate a complete circuit.

In several previous LTspice posts I described how to use the simulator as a test jig for single IC’s and gates. Each block in a circuit should be tested within LTspice before creating a multi-circuit simulation to verify performance against expected results. The test jig process included downloading a custom gate, IC, and spice code for the cd4066 bi-polar analogue switch from the yahoo LTspice user group, and the creation of my own 74LS193 pre-setable up/down counter from primitive logic gates. Ltspice is very flexible. Most discrete components are readily available in the library, with a great support group from on yahoo. There are a wide variety of spice and pspice models to important from many Internet sources as well..

The Circuit to Simulate

I came across this digital volume control circuit during a web search. The circuit seems to be fairly popular as it shows up in thousands of places on the web. I thought it would be a good place to start my investigation of digital volume control even though there are many industry specific chips out there to manage some of these functions as well as chips that offer much larger feature sets. With this circuit I hope to expand on the features to create new volume control and measurement circuits – perhaps while investigating the value in using an more advanced volume control chip.

This circuit could be used for replacing your manual volume control in a stereo amplifier. In this circuit, push-to-on switch S1 controls the forward (volume increase) operation of both channels while a similar switch S2 controls reverse (volume decrease) operation of both channels.
Here IC1 timer 555 is configured as an astable flip-flop to provide low-frequency pulses to up/down clock input pins of pre-setable up/down counter 74LS193 (IC2) via push-to-on switches S1 and S2. To vary the pulse width of pulses from IC1, one may replace timing resistor R1 with a variable resistor.

Operation of switch S1 (up) causes the binary output to increment while operation of S2 (down) causes the binary output to decrement. The maximum count being 15 (all outputs logic 1) and minimum count being 0 (all outputs logic 0), it results in maximum and minimum volume respectively.

The active high outputs A, B, C and D of the counter are used for controlling two quad bi-polar analogue switches in each of the two CD4066 ICs (IC3 and IC4). Each of the output bits, when high, short a part of the resistor network comprising series resistors R6 through R9 for one channel and R10 through R13 for the other channel, and thereby control the output of the audio signals being fed to the inputs of stereo amplifier. Push-to-on switch S3 is used for resetting the output of counter to 0000, and thereby turning the volume of both channels to the minimum level. — Sheena K. for electronicsforu magazine

Dual-Channel Digital Volume Control Circuit (click to enlarge)

The LTspice Simulation

The Circuit

Volume Controller Schematic in LTspice (click to enlarge)

The Simulation Results

LTspice Simulation Results (click to enlarge)

Simulating the CD4066 Quad Bilateral Switch With LTspice

December 12th, 2011


Ron Fredericks writes: Today is Robert Norton Noyce’s birthday (born 12/12/1927) – co-inventor of the integrated circuit (IC). So I thought I would take a few minutes and document my work modeling the CD4066 quad bilateral switch with the LTspice simulator.

In this post I describe how flexible LTspice can be as a general SPICE circuit simulator, and how accurate its behavior can be in comparing LTspice test results with the physical IC’s datasheet. In this example I use the CD4066B as the IC to model. I test the model using its characteristic “on” resistance curves under various voltage and current operating conditions. I conclude by using a standard CD4066 datasheet to verify the accuracy of the model.

Meanwhile this is the last IC I need to simulate the analog section of the digital volume control circuit using LTspice I mentioned in two of my previous blog entries:

Define one of four bilateral switches on CD4066 for LTspice

 

To get the CD4066 IC into my circuit simulation, I first created a symbol for one of the four bilateral switches in this package, and defined a SPICE subcircuit definition for the switch using existing SPICE CD4007 gate models as the starting point.

Symbol for one of four bilateral switches on the CD4066 IC

 

LTspice symbol for one of four bilateral switches on cd4066 (click to enlarge)

LTspice Subcircuit Definition for CD4066
Note the LTspice implementation of the SPICE language is highlighted (below) using my own GeSHi language highlighter library with key sections of the language (.model and .subcircuit) hyper-linked into SPICE language definitions that I have created on the contributor pages of this website. SPICE is a difficult language to highlight using GeSHi because many of the SPICE language constructs are so short that they overlap with longer language constructs. I plan to add more language definitions in the future as my circuit models need them, and I continue to find unique look-up algorithms to match GeSHi language highlighter categories.

 

code=ltspice
  1.  
  2. * CD4066 Analog Switch
  3. * SYM=CD4066
  4. * Transistor models are from LTspice group member kcin_melnick
  5. * See message number 16897, http://tech.groups.yahoo.com/group/LTspice/
  6. * Analog Switch Control In Out Vdd Vss
  7. .SUBCKT CD4066 2 11 4 10 7
  8. X1 2 6 10 7 INVERT
  9. X2 6 1 10 7 INVERT
  10. M1 14 6 7 7 CD4007N
  11. M7 11 6 14 10 CD4007P
  12. M3 11 1 14 14 CD4007N
  13. M4 11 1 4 14 CD4007N
  14. M8 11 6 4 10 CD4007P
  15. .SUBCKT INVERT 1 2 3 4
  16. * Inverter In Out Vcc Vss
  17. M1 2 1 3 3 CD4007P
  18. M2 2 1 4 4 CD4007N
  19. .ENDS
  20. .MODEL CD4007N NMOS (
  21. + LEVEL=1 VTO=1.44 KP=320u L=10u W=30u GAMMA=0 PHI=.6 LAMBDA=10m
  22. + RD=23.2 RS=90.1 IS=16.64p CBD=2.0p CBS=2.0p CGSO=0.1p CGDO=0.1p
  23. + PB=.8 TOX=1200n)
  24.  
  25. .MODEL CD4007P PMOS (
  26. + LEVEL=1 VTO=-1.2 KP=110u L=10U W=60U GAMMA=0 PHI=.6 LAMBDA=40m
  27. + RD=21.2 RS=62.2 IS=16.64P CBD=4.0P CBS=4.0P CGSO=0.2P CGDO=0.2P
  28. + PB=.8 TOX=1200N)
  29. .ENDS

Testing the CD4066 Circuit in LTspice

Finally, I dragged the symbol with subcircuit models into my LTspice program and ran a series of tests to demonstrate the “on” resistance characteristics associated with the switch at various voltage and current values. Note the multicolored graph showing the resistance curves at various VI levels.

 

VI curves and circuit schematic for cd4066 bilateral switch under test (click to enlarge)

Get these files from LTspice Yahoo Group

The 4 main files used to create this demo circuit can be obtained from LTspice Yahoo Group. Special thanks to Helmut Sennewald

See the figure below…

LTspice Yahoo Group File List (click to enlarge)

Comparison of LTspice circuit simulation with datasheet

The TI datasheet compares favorably with my simulations. The LTspice “on” resistance curves and values are nearly exactly the same as those shown in figures 2,3, and 4 of TI’s datasheet (page 6) for the range I tested.

At this stage of development in simulating the analog path for my automatic volume control circuit, I see that the “on” resistance curve may create an unstable signal path under normal audio conditions unless the operating voltage (Vcc ) is much higher than the original circuit’s proposed 5 VDC power supply.

References

Linear Technologies LTspice Landing Page

Texas Instruments datasheet for the CD4066B

What’s All This CD4007 Stuff, Anyhow?
Bob Pease | ED Online ID #6073 | April 5, 1999
http://electronicdesign.com/Articles/ArticleID/6073/6073.html

Fault in CD4066 Model
kcin_melnick | LTspice Yahoo Tech Group Message #16897 | June 24, 2007
http://tech.groups.yahoo.com/group/LTspice/message/16897

Technorati Claim Tag
SH66YHJAPDBA

Technorati Tags: , , , , ,

Forum Newsletter – New RTOS Videos

December 5th, 2011

Embedded Components and Tools forum: December 2011

The forum introduces real-time embedded systems technology designed, reviewed, or filmed by Ron Fredericks. Ron focuses on hardware, software, and cloud services for the embedded systems industry through the EmbeddedComponents.com platform and his Bay Area media lab located in Sunnyvale California called LectureMaker LLC.

Read the rest of this entry »

Technorati Tags: , , , , , , , , , , , , , , ,

How to Use LectureMaker Video Studio for Hardware/Software Demos

March 23rd, 2010


Ron Fredericks writes: Have you tried to post software demo’s on youtube? If so, then this online video produced from LectureMaker‘s high-tech video studio can help you get up to speed very quickly on how to solve the video publishing problems associated with software screencasting. The video demonstrates how to build a simple external hard disk starting from an enclosure for USB and eSTATA connectivity with a PC, MAC, or Linux box. The video concludes with a walk-through on how to format the disk into two partitions.

Enjoy…

Hardware Software Demonstration
Presented by Ron Fredericks, Business Videographer and Open Studio Director

Video Link

Technorati Tags: , , , , , ,

Embedded Hypervisor – the RTOS in the clouds

February 11th, 2010

Ron Fredericks writes: I just read the press release on Wind River‘s Hypervisor and Mark Hermeling‘s blog on the subject of multi-core virtualization.

Wind River gets a second chance on connecting smart devices into the enterprise world.

One of their previous attempts was Wind’s office political initiative into Embedded BSD/OS. I thought the BSD OS play was great for Wind River if only they connected their robust multi-core OS from the smart device into the enterpise. Now I see and hope that Wind River has learned from this prior effort and is off to a second chance.

The classic Hypervisor diagram
The Wind River Hypervisor

So there are a few different kinds of hypervisor: here is a link to a short discription of the server OS, versus their type 1 and 2 hypervisors. Follow Wind River to learn more about their vision for an embedded system hypervisor.

Now of course the cloud is more tied to the embedded system world than ever. Just look at UC Berkeley‘s upcoming annual technology day called BEARS, where CAL’s EE and CS researchers share with the technology industry.

I sure hope Wind River will be attending!

This year’s 2010 Berkeley EECS Annual Research Symposium event is called: From Clouds to Sensors – A Berkeley View

BEARS symposium image: from clouds to sensors
The CAL BEARS 2010 Symposium view from the clouds

Ron has been in the enterprise, embedded systems, and smartphone technical marketing and partner development for the past 15+ years. Contact him to learn more about how relationship marketing can be used to connect the embedded systems hypervisor to the enterprise clouds with effecient use of industry and university partnerships.

Technorati Tags: , , , , , , , ,

Introduction to Google Android

February 5th, 2010


Ron Fredericks writes: Are you new to the google android smartphone platform and developer ecosystem? If so, then this online video produced from LectureMaker‘s high-tech video studio can help you get up to speed very quickly. The video includes several navigation dots along the time line so you can jump to the content you want to watch (once it has downloaded). Expect to get an overview, some sample code demos, and an understanding of the business case behind developing apps for Android from watching this great video presented by Marko Gargenta of Marakana.

Enjoy…

Android Introduction by Marko Gargenta, marakana
Presented by Peter Lam, Mobile SIG Co-chair, Software Developer Forum

Video Link

Technorati Tags: , , , , , ,