Important Algorithms

As a programmer of any computer language, you should be able to write the following algorithms:

Basic

• use a counter to count the number of loop iterations
• use an accumulator statement to find a running total
• Binary Search
• Sequential (i.e. Linear) Search
• find the smallest value in an array along with its position in the array
• find the largest value in an array along with its position in the array
• swap two variables or objects
• determine if one value is evenly divisible by another
• determine if an integer is prime or composite
• Selection Sort
• Insertion Sort
• Bubble Sort
• compute the average of the numbers in an array
• generate a pseudorandom value between 0 and 1
• generate a pseudorandom value between 1 and some positive integer x
• generate a pseudorandom value between two specified positive values
• reverse the elements of an array
• use a loop to compute a factorial

Advanced

• compute amortized interest
• use the Babylonian Algorithm to approximate the square root of a positive value c:
  • Let e be your tolerance; e.g. e = 5E-12.
  • Let x0 = 0.0.
  • Let x1 = 1.0.
  • Repeat while abs(x0-x1) < e:
  • Let x0 = x1.
  • Let x1 = (x0 + c/x0)/2.
  • Return x1.
• use the Euclidean Algorithm for computing the greatest common divisor of two positive integers m and n:
  • Repeat until m == 0 or n == 0
  • If m > n, decrease m by n
  • Otherwise decrease n by m.
  • Return the larger of m or n.
• use the Interpolation Search for finding a key among a sorted sequence a = {a[0], ..., a[n]}:
  • Let p = 0 and q = n.
  • Repeat steps 2-5 while p <= q:
  • Let r = (key-a[p])/(a[q]-a[p]).
  • If a[r] == key, return r.
  • If a[r] < key, let p = r;
  • Otherwise, let q = r.
  • Return -1.
  • This algorithm runs in hyperlogarithmic time (i.e., O(log(log(n)) if the sequence is uniformly distributed. It is a modification
    of the Binary search, which is what you get if you let r = 1/2 on each iteration.

Other Computational Thinking Concepts

• abstraction
• algorithm
• Boolean logic
• code
• collection
• collision detection
• conditionals
• data type
• data structure
• database
• debugging
• decomposition
• design
• efficiency
• evaluation
• event-handling
• expression
• loop, iteration
• memory
• modularity
• nesting
• parallel processing
• procedure
• randomization
• recursion
• refactoring
• search
• sequence
• simulation
• string
• type safety
• user interface
• variables