Chapter 7 - Algorithms

7.1 Algorithms

  • Before solving a problem, a programmer must first create an algorithm to correctly solve the given problem.

  • Algorithm: A sequence of steps that solves a problem, generating correct output for any valid input values.

    • Ensuring an algorithms correctness is a key job for a programmer.

  • Algorithm time efficiency: The number of calculations required to solve a problem.

7.2 Introduction to Algorithms

  • Computational problem: Specifies an input, a question about the input that can be answered using a computer, and the desired output.

  • An efficient algorithm is one whose runtime increases no more than polynomially with respect to the input size. However, some problems exist for which an efficient algorithm is unknown.

    • Some problems exist for which an efficient algorithm is unknown.

  • NP-complete: Problems are a set of problems for which no known efficient algorithm exists.

    • Characteristics:

      • No efficient algorithm has been found to solve an NP-complete problem.

      • No one has proven that an efficient algorithm to solve an NP-complete problem is impossible.

      • If an efficient algorithm exists for one NP-complete problem, then all NP-complete problems can be solved efficiently.

    • By knowing a problem is NP-complete, instead of trying to find an efficient algorithm to solve the problem, a programmer can focus on finding an algorithm to efficiently find a good, but non-optimal, solution.

7.3 Algorithm efficiency

  • Algorithm efficiency: Typically measured by the algorithm's computational complexity.

  • Computational complexity: the amount of resources used by the algorithm.

    • Most common resources considered are the runtime and memory usage.

  • Runtime complexity, best case, and worst case

    • Runtime complexity: a function, T(N), that represents the number of constant time operations performed by the algorithm on an input size N. Runtime complexity is discussed in more detail elsewhere.

      • Because an algorithm's runtime may vary significantly based on the input data, a common approach is to identify best and worst case scenarios.

        • Best case: the scenario where the algorithm does the minimum possible number of operations.

        • Worst case: the scenario where the algorithm does the maximum possible number of operations.

    • Space complexity: A function, S(N), that represents the number of fixed-size memory units used by the algorithm for an input of size N.

      • Ex: the space complexity of an algorithm that duplicates a list of numbers is S(N) = 2N + k, where k is a constant representing memory used for things like the loop counter and list pointers.

      • Includes the input data and additional memory allocated by the algorithm.

    • Auxilary space complexity: The space complexity not including the input data.

      • Ex: An algorithm to find the maximum number in a list will have a space complexity of S(N) = N + k but has an auxiliary space complexity of S(N) = k where k is a constant

7.4 Searching and algorithms

  • Linear Search: A search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached.

  • Runtime: The time the algorithm takes to execute.

7.5 Binary Search

  • Linear search vs binary search

    • Linear search may require searching all list elements, Binary search checks middle contact first.

      • If desired contact coems alphabetically before the middle contact, binary search will then ewarch the first half and otherwise the last half. Each step reduces the contacts that need to be searched by half.

    • Binary Search: A faster algorithm if searching a list if the list's elements are sorted and directly accessible. Binary search first checks the middle element of the list. If the search key is found, the algorithm returns the matching location. If the search key is not found, the algorithm repeats the search on the remainnig left sublist (if the search key was less than the middle element) or the remaining right sublist (if the search key was greater than the middle element).

7.6 Sorting: Introduction

  • Sorting: The process of converting a list of elements into ascending (or descending) order.

7.7 Heuristics

  • Heuristic: A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.

    • May sacrifice accuracy to improve speed

    • willingly accepts non optimal solutions

  • Heuristic algorithm: An algorithm that quickly determins a near optimal or approximate solution.

7.8 Algorithms summary

  • A programmer must first create a correct algorithm: A sequence of steps to solve a problem.

  • For large data, also relevant is an algorithm's time efficiency: The number of calculations needed to solve a problem.