In the worst-case analysis of algo-rithms, the overall performance of an algorithm is summarized by its worst performance on any input. This approach has countless success stories. However, there are also major computational problems (like linear programming, clustering, and online caching) where the worst-case analysis framework does not provide any helpful advice on how to solve the problem. In this talk, we study improved algorithms for edit distance and longest common subsequence, which are among the most fundamental problems in combinatorial optimization, beyond their worst-case. The proposed algorithms obtain $1+o(1)$ approximate solutions for both problems in truly subquadratic time if the input satisfies a mild condition. In this setting, first, an adversary chooses one of the input strings. Next, this string is perturbed by a random procedure. Then the adversary chooses the second string arbitrarily after observing the perturbed one.