📄️ Asymptotic Analysis
Introduction
📄️ Solving Recurrences
Recall that one of our main aims in CS3230 is to be able to analyze algorithms. Often, we have recursive algorithms which leads to running time in the form of recurrence relations. For example, the recurrence relation for MergeSort is $T(n) = 2T(n/2) + O(n)$.
📄️ Proof of Correctness
In this module, our goal is to design and analyse algorithms. One of the main requirements is that the algorithm must be correct (an inefficient correct algorithm is better than an efficient incorrect algorithm).
📄️ Divide and Conquer
A Familiar Paradigm
📄️ Sorting Algorithms
Introduction
📄️ Randomised Algorithms and Order Statistics
As an example of randomized algorithms, we shall analyze the time complexity of quicksort in detail (for both cases: fixed pivot and random pivot).