M1 - Introduction to Algorithms

• Algorithm


  A sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time
• Correctness of an algorithm

  • Partial correctness (if an answer is returned it will be correct)
  • Total correctness (algorithm terminates)
• Characteristics of algorithms


  • Algorithms must have a unique name
  • Algorithms should have explicitly defined set of inputs and outputs
  • Algorithms are well-ordered with unambiguous operations
  • Algorithms halt in a finite amount of time
• Pseudocode


  A high-level description of an algorithm without the ambiguity associated with plain text but also without the need to know the syntax of a particular programming language
• Difference between algorithm and pseudocode

  An algorithm is a formal definition with specific characteristics that describes a process executable by a Turing-complete computer, while pseudocode is an informal and rudimentary human readable description of an algorithm
• Reasons to study algorithms

  • Theoretical importance (the core of computer science)
  • Practical importance (a practitioner's toolkit of known algorithms, framework for designing and analyzing algorithms for new problems)
  • Historical perspective (Muhammad ibn Musa al-Khwarizmi, Euclid's algorithm, Sieve of Eratosthenes)
• Sorting


  Rearrange the items of a given list in ascending order
• Sorting Algorithms


  • Selection sort
  • Bubble sort
  • Insertion sort
  • Merge sort
  • Heap sort
• Stability


  A sorting algorithm is called stable if it preserves the relative order of any two equal elements in its input
• In place


  A sorting algorithm is in place if it does not require extra memory, except, possibly for a few memory units
• Searching


  Find a given value, called a search key, in a given set
• Searching Algorithms


  • Sequential search
  • Binary search
• String Processing


  Searching for a given word/pattern in a text
• Graph


  A collection of points called vertices, some of which are connected by line segments called edges
• Fundamental Data Structures


  • List
  • Stack
  • Queue
  • Priority queue/heap
  • Graph
  • Tree and binary tree
  • Set and dictionary
• Array


  A sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a value of the array's index
• Linked List


  A sequence of zero or more nodes each containing two kinds of information: some data and one or more links called pointers to other nodes of the linked list
• Stack


  A data structure for maintaining a set of elements, with insertion/deletion only at the top (LIFO/FILO)
• Queue


  A data structure for maintaining a set of elements, with insertion at the rear and deletion from the front (FIFO/LILO)
• Priority Queue


  A data structure for maintaining a set of elements, each associated with a key/priority, with operations to find, delete, and insert the element with the highest priority
• Graph


  Formal definition: A graph G = <V, E> is defined by a pair of two sets: a finite set V of items called vertices and a set E of vertex pairs called edges
• Graph Representation


  Adjacency matrix, Adjacency linked lists
• Weighted Graph


  Graphs or digraphs with numbers assigned to the edges
• Path


  A sequence of adjacent (connected by an edge) vertices that starts with u and ends with v
• Connected Graph


  A graph is said to be connected if for every pair of its vertices u and v there is a path from u to v
• Cycle


  A simple path of a positive length that starts and ends at the same vertex
• Acyclic Graph


  A graph without cycles
• Tree


  A connected acyclic graph
• Rooted Tree


  A tree with a designated root vertex
• Ancestors


  For any vertex v in a tree T, all the vertices on the simple path from the root to that vertex are called ancestors
• Descendants


  All the vertices for which a vertex v is an ancestor are said to be descendants of v
• Parent, Child, Siblings


  If (u, v) is the last edge of the simple path from the root to vertex v, u is said to be the parent of v and v is called a child of u. Vertices that have the same parent are called siblings.
• Leaves


  A vertex without children is called a leaf
• Subtree


  A vertex v with all its descendants is called the subtree of T rooted at v
• Depth of a Vertex

  The length of the simple path from the root to the vertex
• Height of a Tree

  The length of the longest simple path from the root to a leaf
• Ordered Tree


  A rooted tree in which all the children of each vertex are ordered
• Binary Tree


  An ordered tree in which every vertex has no more than two children and each child is designated as either a left child or a right child of its parent
• Binary Search Tree


  A binary tree in which each vertex is assigned a number, and the number assigned to each parental vertex is larger than all the numbers in its left subtree and smaller than all the numbers in its right subtree
• Recursion


  A process in which a function calls itself directly or indirectly