These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else



Download 186,06 Kb.
Page1/24
Date conversion03.05.2017
Size186,06 Kb.
  1   2   3   4   5   6   7   8   9   ...   24

These notes are intended for use by students in CS1501 at the University of Pittsburgh and no one else

  • These notes are intended for use by students in CS1501 at the University of Pittsburgh and no one else
  • These notes are provided free of charge and may not be sold in any shape or form
  • These notes are NOT a substitute for material covered during course lectures. If you miss a lecture, you should definitely obtain both these notes and notes written by a student who attended the lecture.
  • Material from these notes is obtained from various sources, including, but not limited to, the following:
    • Algorithms in C++ by Robert Sedgewick
    • Introduction to Algorithms, by Cormen, Leiserson and Rivest
    • Various Java and C++ textbooks

Goals of Course

  • Definitions:
    • Offline Problem:
    • Algorithm
      • A step-by-step procedure for solving a problem or accomplishing some end
    • Program
      • an algorithm expressed in a language the computer can understand
    • An algorithm solves a problem if it produces an acceptable output on EVERY input

Goals of Course

  • Goals of this course:
    • To learn how to convert (nontrivial) algorithms into programs
      • Often what seems like a fairly simple algorithm is not so simple when converted into a program
      • Other algorithms are complex to begin with, and the conversion must be carefully considered
      • Many issues must be dealt with during the implementation process
        • Let's hear some

Goals of Course

    • To see and understand differences in algorithms and how they affect the run-times of the associated programs
      • Many problems can be solved in more than one way
      • Different solutions can be compared using many factors
        • One important factor is program run-time
          • Sometimes a better run-time makes one algorithm more desirable than another
          • Sometimes a better run-time makes a problem solution feasible where it was not feasible before
        • However, there are other factors for comparing algorithms
          • Let's hear some

Algorithm Analysis

    • Determine resource usage as a function of input size
      • Which resources?
    • Ignore multiplicative constants and lower order terms
      • Why?
    • Measure performance as input size increases without bound (toward infinity)
      • Asymptotic performance
    • Use some standard measure for comparison
      • Do we know any measures?

Algorithm Analysis

      • Big O
        • Upper bound on the asymptotic performance
      • Big Omega
        • Lower bound on the asymptotic performance
      • Theta
        • Upper and lower bound on the asymptotic performance – Exact bound
      • Compare on the board
    • So why would we ever use Big O?
      • Theta is harder to show in some cases
      • Lower bounds are typically harder to show than upper bounds
        • So sometimes we can just determine the upper bound

Algorithm Analysis

  • So is algorithm analysis really important?
    • Yes! Different algorithms can have considerably different run-times
      • Sometimes the differences are subtle but sometimes they are extreme
      • Let's look at a table of growth rates on the board
        • Note how drastic some of the differences are for large problem sizes

Algorithm Analysis

    • Consider 2 choices for a programmer
      • Implement an algorithm, then run it to find out how long it takes
      • Determine the asymptotic run-time of the algorithm, then, based on the result, decide whether or not it is worthwhile to implement the algorithm
      • Which choice would you prefer?
      • Discuss

Exhaustive Search

  • Idea:
    • We find a solution to a problem by considering (possibly) all potential solutions and selecting the correct one
  • Run-time:
    • The run-time is bounded by the number of possible solutions to the problem
    • If the number of potential solutions is exponential, then the run-time will be exponential

Exhaustive Search

  • Example: Hamiltonian Cycle
    • A Hamiltonian Cycle (HC) in a graph is a cycle that visits each node in the graph exactly one time
    • Note that an HC is a permutation of the nodes in the graph (with a final edge back to the starting vertex)
      • Thus a fairly simple exhaustive search algorithm could be created to try all permutations of the vertices, checking each with the actual edges in the graph
        • See text Chapter 44 for more details

Exhaustive Search

  • A
  • G
  • F
  • E
  • C
  • B
  • D

Exhaustive Search

      • Unfortunately, for N vertices, there are N! permutations, so the run-time here is poor
  • Pruning and Branch and Bound
    • How can we improve our exhaustive search algorithms?
      • Think of the execution of our algorithm as a tree
        • Each path from the root to a leaf is an attempt at a solution
        • The exhaustive search algorithm may try every path
      • We'd like to eliminate some (many) of these execution paths if possible
        • If we can prune an entire subtree of solutions, we can greatly improve our algorithm runtime
  1   2   3   4   5   6   7   8   9   ...   24


The database is protected by copyright ©sckool.org 2016
send message

    Main page