- Basic Graph Algorithms
- Breadth-first search & Depth-first search
- Dijkstra’s shortest path
- Floyd-Warshall algorithm
- Prim’s algorithm
- Divide & Conquer
- Merge Sort
- Dynamic Programming
- Longest Increasing Subsequence
- Travelling Salesman Problem
- Network Flow
- NP Optimization
What is a program? A program, the implementation of an algorithm, is a sequence of instructions that are used to solve a problem or do some calculations. It always comes with specifications, including input and output. The process of getting output from the input is considered as a program.
Before getting started, we will discuss some basics of an algorithm: program correctness, a method helps us to verify if an algorithm is correct or not.
Program correctness sometimes has been split into two parts: soundness and termination.
- Soundness: on every valid input, if program terminates, then its output is correct.
- Termination: on every valid input, the program terminates.
This is important as we will frequently use it to determine if our algorithm is correct. One technique that is helpful to prove program correctness is mathematical induction. If you are interested, here are more examples provided by Cornell.
Remember, algorithm can be intriguing and fun to exploit! Good luck and have fun!
Some material in this topic is selected from the coursework of CS577: Introduction to Algorithm and ICPC training material written by Prof. Van Melkebeek @ University of Wisconsin-Madison.