What are some common degenerate cases for structures or functions in computer science?

Question

I can think of only a few for example the zero length list or set. The zero length string. How about empty matrices or tensors? How about parallelograms with all zero degree angles? How about a rectangle with two sides zero length? Or a triangle having ones side 180 degrees and the other two are zero? Can we keep going with many sided polygons? Nah that doesn't feel right. But I do believe there are similar degenerate shapes in 3-space.

But those I am not much interested in. I'm looking for some common math functions often used in programming which have well known degenerate cases. I do lots of Mathematica and some JavaScript programming but the actual programming language doesn't really matter as this is more of a computer science task.

Answer 1

There are some interesting examples of degenerate data structures

• Degenerate Binary Tree - It's basically a Binary Tree where every parent has only one child. So it degenerates into a linked list.

• Hash Table with a constant hash function - Hash Table collisions can be handled in two main ways:

  1. Chaining - Every cell of the array links to a linked list and elements with the same hash value are chained together into this list. So, when the hash function is constant, all elements have the same hash value and they are all connected; here, the hash table degenerates into a linked list.
  2. probing - Here, if an element has the same hash as another one, I simply look for an empty space. Now, when the probing sequence is linear (so if the cell i is occupied I'll look for the cell i+1) and the hash value is always the same, I will generate only collisions, every element is put into the first empty space of the list and It will degenerate into an another linked list.

• Classes with no methods - A class without methods, so written like this:

  class Fraction {
      int numerator;
      int denominator;
  }
  

  It degenerates into a struct, so like this:

  struct Fraction {
      int numerator;
      int denominator;
  }
  

And so on. Obviously, there are many other examples of degenerate cases for data structures or functions (in graph theory for example). I hope this can help.