Debian – How to list currently not installed packages

From the dpkg man page

  -C, --audit
          Searches for packages that have been installed only partially on your system. dpkg will suggest what to do with them to get them working.

So dpkg -C (as user) may work. However, I can't test this since I don't have any broken packages.

Search for packages that are manually installed, and that are a mandatory or recommended dependency of an installed package. Aptitude can do that.

aptitude search -q -F %p '?installed !?automatic (?reverse-depends(?installed .*) | ?reverse-recommends(?installed .*))'

I don't think there's a way to indicate what dependency was found for each package. If you want that information, Python would be the way to go. This very quick-and-dirty script seems to do it (mostly, I think it may be incorrect in some non-straightforward cases involving disjunctions, version dependencies, pre-depends, …).

#!/usr/bin/env python2
import apt
packages = apt.Cache()
covered = {}
# Inverse dependency computation: for each installed package, record which
# packages require it (as Depends: or Recommends:).
for p in packages:
    if p.installed:
        for l in p.installed.dependencies + p.installed.recommends:
            for d in l:
                if packages.has_key(d.name) and packages[d.name].installed:
                    if not covered.has_key(d.name):
                        covered[d.name] = []
                    covered[d.name] += [p.name]
# Print out the manually installed packages that are required by another
# installed package, as well as the requiring package(s).
for p in sorted(covered.keys()):
    if not packages[p].is_auto_installed:
        print(' '.join([p] + covered[p]))