Tips/tricks related to Computer Graphics, GPUs and other programming

Archive for the ‘Python’ Category

Binary Search Tree in Python

It has been a while since I have written a data structure from scratch (had to write B-Trees for an Advanced Data Structures course 2 years ago), so I decided to refresh my memory by quickly writing up Binary Search Trees in Python. Making sure you are familiar with data structures always helps with interviews too.

You can access the file here. I have only tested this for integers, so might need a little bit of work for other data types. The following methods have been implemented:

  • add(data)
  • remove(data)
  • Traversals:

  • preorder()
  • inorder()
  • postorder()
  • bfTraversal() (Breadth-first traversal)
  • Helper methods:

  • isLeaf(node) – checks if a node is a leaf
  • lcAncestor(value1, value2) – finds the least common ancestor of two nodes with values value1 and value2
  • printAllPaths() – prints all the possible paths from the root to the leaves

I won’t go over how a BST works, but hopefully the code is self-explanatory.

If there are any questions let me know – hope people find it useful.


Evaluating Bicubic Bézier Surfaces using (Py)OpenCL

GitHub Repository here

I’ve been meaning to get into OpenCL for a while, so I thought I would write a simple program which would evaluate Bicubic Bezier patches (surfaces) in parallel.
I also wanted to program in Python more, so I decided to use PyOpenCL. You can find more info about the OpenCL implementation in Python from the link.

I am not going to go over what a Bezier patch is and how it can be evaluated. There is a straightforward equation for evaluating one which I will be showing later on, but for more info about Bezier patches you can find other info online.

Let’s begin.