Introduction to Algorithms

• Introduction to Algorithm by Chris Piamonte from the Polytechnic University of the Philippines, College of Computer and Information Sciences, Department of Computer Science.
• The learning objectives are to define algorithms, understand the fundamentals of algorithmic problems, and identify important problem types.

Donald Knuth on Algorithms

• A computer science professional is skilled in constructing, manipulating, understanding, and analyzing algorithms.
• Algorithmic knowledge extends beyond computer programming, serving as a versatile tool applicable in fields like chemistry, linguistics, and music.
• Formalizing concepts into algorithms leads to an understanding that surpasses conventional methods.

Brain Teaser: Man, Goat, Wolf, and Cabbage

• The classic brain teaser involves a man needing to transport a wolf, a goat, and cabbage across a river, but his boat can only carry himself and one item at a time.
• Challenges include the wolf eating the goat, or the goat eating the cabbage if left unattended, with their safety ensured only in the man's presence.
• One algorithmic solution is to take: goat across, return alone. Then take wolf across, bring goat back. Take cabbage across, return alone and finally, take goat across.

What is an Algorithm?

• An algorithm consists of clear, step-by-step instructions designed to solve a specific problem.
• Algorithms produce the desired output for any authorized input within a finite time frame.

Algorithm Characteristics

• Ambiguity in any step of an algorithm is NOT allowed.
• The appropriate inputs must be specified for effective outcomes.
• Algorithms can be represented in multiple formats and multiple algorithms can solve the same problem.
• Algorithms for the same problem can differ and result in drastically different speeds.
• Algorithms are precise procedures to reach a solution, not necessarily a solution themselves.

Problem Solving Diagram

• Problem is presented as input to algorithm for computation.
• The computer processes the algorithm on the input.
• Output is the computer's algorithmic solution to the problem.

Proofs vs Algorithms

• Mathematics focuses on proofs.
• Computer science focuses on algorithm development.
• Algorithms are constructive proofs

Algorithm Conditions

• Algorithms must work for all appropriate inputs
• Algorithms are required to solve a problem every time.

Euclidean Algorithm

• The Euclidean algorithm is designed to find the greatest common divisor (GCD) of two non-negative integers m and n.
• If n = 0, the GCD = m
• If n ≠ 0, divide m by n to find the remainder, r
• Then, assign n to m and assign r to n, looping until you have GCD.

Alternative GCD Algorithms

• Consecutive Integer Checking will find the minimum of m and n and call it, t
• Divide m by t
  • If there is a remainder, decrease t
• If no remainder, divide n by t
  • If no remainder, t = GCD
  • If remainder, decrease t

Middle School GCD Procedure

• Find the prime factors of m.
• Find the prime factors of n.
• Identify all the common prime factors.
• Compute the product of the factors.

Sieve of Eratosthenes

• Start with a list of numbers from 2 to n
• Mark the first number as prime
• Remove all multiples of that number
• The next unmarked number is prime, return until all numbers have been exhausted

Fundamentals of Algorithmic Problem Solving

Algorithm Design and Analysis Steps

• Understanding the Problem
• Identifying the Capabilities of the Computing Device
• Choosing between exact or approximate solutions
• Identifying Algorithm Design Technique
• Designing an algorithm and data structures
• Proving Correctness of the algorithm
• Analyzing the problem
• Coding the Algorithm
• A good algorithm is the result of repeated effort and rework
• Algorithms need to be investigated for optimality to find the minimum amount of effort any algorithm needs to solve a problem.

Step 1: Understanding the Problem

• Thoroughly read the problem's description
• Do a few small examples by hand to get an understanding
• Consider special cases
• Precisely define the set of all possible instances an algorithm needs to handle

Step 2: Identifying

• Consider the capabilities of the computational device
• Choose between precise and close problem solving
• Select an appropriate algorithm design technique
  • An algorithm design technique or strategy guides the algorithmic approach to solving a variety of computing problems.

Step 3: Designing an Algorithm and Data Structures

• Begin with a strategic approach
• Combine strategies as needed
• Choose data structures that suit the algorithm’s requirements

Step 4: Proving an Algorithm's Correctness

• Mathematical induction is a common technique
• The algorithm should, in a finite amount of time yield the required results for every legitimate input.
• The algorithm must halt.
• Exact algorithms must emphasize correctness and optimality
• Approximate algorithms need proof that errors do not exceed a predefined limit.

Step 5: Analyzing an Algorithm

• Efficiency in time and space
• Simplicity
• Generality of the problem
• The set of inputs
• Error rate
• Communication
• Information

Step 6: Coding

• Translate the algorithm design into a running program
• Check for correctness and efficiency
• Check for correctness, but small programs may use formal verification
• Validity is established by software testing
• Analysis through empirical analysis of running time based on actual input or quality of error.

Problem Types

• Decision Problems
• Search
• Sorting
• Counting
• Enumeration Problems
• String Processing
• Graph Problems
• Numerical Problems
• Geometric Problems
• Optimization Problems
  • Continuous
  • Combinatorial

Well-Known Computational Problems

• Sorting
• Searching
• Shortest paths in a graph
• Minimum spanning tree
• Primality testing
• Traveling salesman problem
• Knapsack problem
• Chess
• Towers of Hanoi
• Program termination
• Some of these don't have efficient algorithms or algorithms at all.

Decision Problems

• A computational problem where every instance is either yes or no
• An example is primality testing (yes if prime, no if not)

Search Problems

• The goal is finding a specific value or "search key" inside of a set.
• Examples include sequential search and binary search.

Counting and Enumeration Problems

• Counting problems ask for the number of solutions to a given search problem
• For example: "Given a positive integer n, count the number of nontrivial prime factors".
• Enumeration problems find the set of all solutions.

String Processing

• Strings are sequences of characters.
• This can include text strings, bit strings, or gene sequences like ACGT.
• String processing includes string matching and can apply to programming languages.

Graph Problems

• Graphs are collections of points called vertices connected by edges or line segments.
• Graphs can be used to model real-life problems.
• Some examples include modeling WWW, communication networks and relationships of different entities.

Numerical Problems

• Numerical problems use mathematical objects of a continuous nature.
• Some examples include solving equations and computing definite integrals.

Geometric Problems

• Geometric problems use objects like points, line segments, polygons, and polyhedra

Optimization Problems

• The problem finds the best solution from the set of all feasible solutions.
• Optimization includes continuous and combinatorial optimization.

Continuous Optimization

• The standard form of a continuous optimization problem is to minimize f(x) which is subject to various constraints with variables.

Combinatorial Optimization

• Formally, it is a quadruple consisting of instances, feasible solutions, measure, and goal function.
• Examples of combinatorial optimization include the
  • Knapsack Problem,
  • Minimum Spanning Tree, and
  • Traveling Salesman problems.
• These problems are often approached using search strategies, where the search space may be quite large.

Algorithm Summary

• An algorithm is a sequence of unambiguous instructions for solving a problem in a finite amount of time.
• Inputs define the problem context that an algorithm handles.
• Algorithms can be expressed in natural language, pseudocode, or program code.
• Algorithms can be grouped by problem type or design technique.

Problem Types Summary

• Main Important problem types include sorting, searching, string processing, graph problems, combinatorial problems, geometric problems, and numerical problems.
• "Strategies" are approaches applicable to a variety of problems from different areas of computing.
• A great algorithm results from repeated efforts and rework.