Data Structures

algorithm

a sequence of unambiguous instructions for solving a problem

algorithmics

the core of computer science

What is required for an algorithm?

finiteness

definiteness

input

output

effectiveness

What are the algorithm design strategies?

brute force

decrease and conquer

divide and conquer

transform and conquer

greedy approach

dynamic programming

space and time tradeoffs

brute force algorithms

straightforward approach to solving a problem, usually directed based on the problem’s statement and definitions of concepts involved

brute force algorithm examples

O(N²) quadratic sorting algorithms (selection and bubble sort)

sequential searching a list

string pattern matching

decrease and conquer algorithms

exploiting relationship between solution to a given problem instance and a solution instance of the same problem

decrease and conquer algorithm examples

insertion sort

depth and breadth first searching (trees and graphs)

divide and conquer algorithms

a problem’s instance is divided into several (often two) smaller instances of the same problem (type of decrease and conquer)

divide and conquer algorithm examples

mergesort

quicksort

O(N log_2 N)

binary search

binary tree traveralst

transform and conquer algorithms

a problem’s instance is modified to be more amenable to solution

transform and conquer algorithm examples

presorting

gaussian elimination (solving systems of equations)

balanced search trees (AVL, 2-3 trees)

heaps (priority queues)

heapsort

space and time tradeoffs

well-known issue to computer scientists

space and time tradeoff examples

sorting by counting

hashing

b-trees

dynamic programming

optimizing multistage decision processes

dynamic programming examples

computing binomial coefficients

warshall’s algorithm (transitive closure in digraphs)

optimal binary search trees

greedy technique

solving problem by reducing the remaining amount the most

greedy technique examples

spanning trees (Prim and Kruskal MSTs)

Dijkstra’s Algorithm (single-source shortest-path through graph)

Huffman trees (variable-length encoding, files compression, optimal external sorting)

Euclid’s Algorithm for GCD

gcd(m,n) = gcd(n,m mod n) until m mod n = 0

time efficiency

how fast the algorithm runs

analyzed by determining the number of repetitions of the basic operation as a function of input size

space efficiency

how much extra memory is needed

simplicity

easier to understand and program resulting in fewer bugs

generality

for problem and for range of inputs

important computational problem types

sorting

searching

string processing

graph problems

combinatorial problems

geometric problems

numerical problems

sorting problems

rearranging items of a given list in ascending order

key is specifically chosen to piece of information to guide sorting

searching problems

finding a given value in a given set

string processing problems

applications dealing with non-numerical data

string is sequence of characters from some alphabet

string matching problems

graph problems

oldest area in algorithmics

vertices and edge

transportation and communication networks

graph traversal algorithms

combinatorial problems

permutation or combination that satisfies certain constraints and has some desired property

typically grows extremely fast with increase in problem size n

geometric problems

computer graphics, robotics, computer vision, image processing

numerical problems

mathematical objects

majority can be solved only approximately

difficulty because dealing with real numbers

leading to accumulation of round-off error which can distort output

focus shifted in recent times to business applications

set

unordered collection of distinct items called elements

explicit listing of elements or specifying property that all elements must satisfy

abstract data types (ADT)

set of abstract objects representing data items with collection of associated operations that can be performed on them

O(g(n)) (Big-O)

class of functions f(n) that grow no faster than g(n)

ϴ(g(n)) (Big-Theta)

class of functions f(n) that grows at same rate as g(n)

Ω(g(n)) (Big-Omega)

class of functions f9n) that grow at least as fast as g(n)

O-notation

a function t(n) is said to be O(g(n)), denoted t(n)∈O(g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n

Ω-notation

a function t(n) is said to be Ω(g(n), denoted t(n)∈Ω(g(n)), if t(n) is bounded below by some positive multiple g(n) for all large n

ϴ-notation

a function t(n) is said to be ϴ(g(n)), denoted t(n)∈ϴ(g(n)), if t(n) is bounded both above and below by some constant multiples of g(n) for all large n

time efficiency of non-recursive algorithms creation steps

decide on parameter(s) n indicating input size

identify algorithm’s basic operation

determine worse, average, and best case input of size n

set up summation for c(n) reflecting algorithm’s loop (iteration) struction

simplify summation using standard formulas

O-notation is bounded

above

Ω-notation is bounded

below

ϴ-notation is bounded

both above and below