CSPC 24 - Algorithm and Complexity PDF

CSPC 24 Algorithm and Complexity Introduction to Algorithms Objectives Define and understand the meaning of algorithm. Identify and understand the different examples of algorithm. Identify the kinds of problems solved by algorithms. Appreciate the importance of algorithmic problem sol...

CSPC 24 Algorithm and Complexity Introduction to Algorithms Objectives Define and understand the meaning of algorithm. Identify and understand the different examples of algorithm. Identify the kinds of problems solved by algorithms. Appreciate the importance of algorithmic problem solving. ALGORITHM In computer science it is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. Always definite and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks. Every Algorithm must satisfy the following properties: Input - There should be 0 or more inputs supplied externally to the algorithm. Output - There should be at least 1 output obtained. Definiteness - Every step of the algorithm should be clear and well defined. Finiteness – The algorithm should have finite number of steps. Correctness – Every step of the algorithm must generate a correct output. EXAMPLE OF AN ALGORITHM One of the most obvious examples of an algorithm is a recipe. It's a finite list of instructions used to perform a task. One of the attributes of an algorithm is that, since it is a list of instructions, there is some step-by-step process that occurs in order. Let's say that you have a friend arriving at the airport, and your friend needs to get from the airport to your house. Fundamentals Of Algorithmic Problem Solving Understanding the problem Ascertain the capabilities of the computational device Exact /approximate solution Decide on the appropriate data structure Algorithm design techniques Methods of specifying an algorithm Proving an algorithms correctness Analyzing an algorithm Understanding The Problem An input to an algorithm specifies an instance of the problem the algorithm solves. It is very important to specify exactly the set of instances the algorithm needs to handle. Ascertaining The Capabilities of The Computational Device Majority of the algorithms can be programmed for a computer closely resembling the von Neumann machine. Algorithms designed to be executed on such machines are called sequential algorithms. Algorithms that take advantage of concurrent execution capability are called parallel algorithms. Choosing Between Exact and Approximate Problem Solving Exact algorithms are algorithms that always find the optimal solution to a given optimization problem. Approximate algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Decide On the Appropriate Data Structure Some algorithms do not demand any in-Genuity in representing their inputs. Some others are in fact are predicted on ingenious data structures. A data type is a well-defined collection of data with a well-defined set of operations on it. Algorithm Design Techniques A given problem can be solved in various different approaches and some approaches deliver much more efficient results than others. Algorithm analysis is a technique used to measure the effectiveness and performance of the algorithms. Main Algorithm Design Techniques Greedy algorithms Divide and conquer Dynamic Programming Randomized Algorithms Backtracking Algorithms Methods Of Specifying an Algorithm These are the two options that are most widely used nowadays for specifying algorithms. 1. Pseudocode 2. Flowchart Proving An Algorithms Correctness An important aspect of any algorithm is that it is correct: it always produces the expected output for the range of inputs and it eventually terminates. It's difficult to prove that an algorithm is correct. Programmers often use empirical analysis to find faults in an algorithm, but only formal reasoning can prove total correctness. Analyzing An Algorithm The determination of the amount of time and space resources required to execute it. The efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps, known as time complexity, or volume of memory, known as space complexity. A complete analysis of the running time of an algorithm involves the following steps: Implement the algorithm completely. Determine the time required for each basic operation. Identify unknown quantities that can be used to describe the frequency of execution of the basic operations. Develop a realistic model for the input to the program. Analyze the unknown quantities, assuming the modeled input. Calculate the total running time by multiplying the time by the frequency for each operation, then adding all the products. Kinds of Problems Solved by Algorithms Basic numerical algorithms - concerned with basic arithmetic problems like finding the sum, product or quotient of two numbers. Cryptographic algorithms - digitally sign and encrypt your data when it’s sent over the internet and help protect you from people spying on your data or stealing your identity. Sorting and searching algorithms - allow programmers to arrange data in memory in many different ways so that specific pieces of data can later be retrieved efficiently when they are needed. Signal processing algorithms - they are used to compress audio and video data very efficiently and allow us to store a whole 3-hourUHD movie on a single plastic disc, or stream it live over the internet. Kinds of Problems Solved by Algorithms Graph algorithms - They are most successfully used for any kind of problem where you need to find an efficient path through some kind of network — be it a computer network, a road network, or something else. Computational geometry algorithms - are important in games and are also heavily used in CAD software. Numerical analysis - simulate the physical behavior of their systems and optimize them for performance before they are even built. Computer vision algorithms allow software to recognize features in images, from your cellphone scanning a QR code all the way to autonomous cars probing their environment with laser scanners. Rendering algorithms in computer graphics - generate more and more photo-realistic images out of some artificial scene. Video games and movies are the most spectacular uses, but there are many others. Importance of Algorithms The more you know about algorithms, the better your chances are of finding a good way to solve the problem. Understanding the process of building an algorithm helps us build a strong foundation in logical thinking and problem solving. The best-chosen algorithm makes sure computer will do the given task at best possible manner.  Thank you! REFERENCES: Cormen T., Leiserson C., Rivest R., & Stein C. (2009). Introduction to Algorithms Third Edition. The MIT Press, Cambridge, Massachusets Fleck, Margaret M., (2013). Building Blocks for Theoretical Computer Science. Version 1.3 (January 2013) Lehman, Eric F., Leighton, Thomson & Meyer, Albert R. (2018). Mathematics for Computer Science. June 2018 ONLINE REFERENCES: https://www.geeksforgeeks.org/ http://www.freebookcentre.net/CompuScience/free-computer-algorithm-books.html