Is the answer to part b) of the problem based on markov's inequality or chernoff bound?
  Is it based on some classic problem or algorithm?

ProcessStream(stream S):

   Repeat:
          xi = next item in the stream
          [do something really simple and fast with xi]
          Until the stream stops
          Output [something interesting]