You have all of the private key except 20 characters (80 bits)? Then it is possible and feasible to recover the entire key using baby-step-giant-step or pollard's tho algorithm.
It will require 2^40 work, which is a few hours on a GPU.
1) Only if you know the public key too (not the address).
2) baby-step-giant-step in this case (80 bits) would require more than 2^40 work, because you don't have enough Ram to store 2^40 public keys.
To retrieve the last 60 bits (bitcoin case) my program takes about 5 minutes (it run on a single cpu). It uses baby-step-giant-step algorithm and 32 GB.