Introduction to Algorithm

In computer science, an algorithm is a sequence of well-defined instructions to solve a problem, usually within a finite amount of time and space. And it is an essential and indispensable part of computer science, theoretically and practically.

Here’s a rough schedule of what will be discussed in this topic:

• 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
  • Knapsack
  • Travelling Salesman Problem
• Greedy
• Network Flow
• NP Optimization

Program Correctness

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!

---

Credit

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.