Regular expression for the strings without a particular substring
I did the following multistep technique.

Step 1: make a DFA that accepts all strings with "110".  I am able to construct a DFA that accepts all strings with substring "110" and has just 4 states.

Step 2: Flip all the accepting states to non-accepting and all the non-accepting states to accepting.  This page at Old Dominion describes the technique quite succinctly.  This creates a DFA that accepts the language you want.

Step 3: Now you need to convert the DFA back to a regular expression.  As @Alejandro Sazo mentioned there is a proof that this is possible.  But you need an algorithm.  This paper by Christoph Neumann describes three different techniques.  The easiest one is the "state removal technique."   You remove a state and replace all the edges between states that were connected to the removed state with edges labeled with regular expressions.  As you reduce in this way you eventually get to a regular expression for the whole DFA.  (Note that Figure 4 in the paper I linked is not quite right.  The self-loop on state $q_j$ should have the regular expression "c e* b", not "c e* d".)

By going through this process it became clear that: the language you are going to need to solve for this particular problem has the property that once you have seen the sub-string "11" then you can never see another "0".