Algorithms

Introduction

In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

What makes an algorithm good?

• Correctness
• Low time complexity
• Low space complexity

Two Fundamental Problems

Sorting

A sorting problem is to input a sequence of $n$ numbers $[a_1,a_2,\dots ,a_n]$ and output a reordering sequence $[a_1^{\prime },a_2^{\prime },...,a_n^{\prime }]$ such that $a_1^{\prime },a_2^{\prime },...,a_n^{\prime }$ is in ascending order.

Searching

A searching problem is to input a bounded set $X$ with relation $R$ among its elements, and a solution criteria $C$, while output an element $x\in X$ that satisfies the criteria $C$ if any.

Problem Formulation

In reality, problems do not come in well-specified forms. We need to formulate the problem into a well-specified problem that an algorithm can solve. In fact, good problem formulation is usually half the solution.

Contents

Asymptotic Analysis
Recurrence Analysis
Sorting Algorithms
Divide and Concur
Randomized Algorithms
Tree Data Structure
Heap
Dynamic Programming
Greedy Algorithm
Hash Table

Acknowledgement

This part is mainly based on ANU course COMP3600.