Algorithms Basics

1 . Algorithm:
A sequence of unambiguous statements that produce output given ligetimate input to it in finite amount of time

Characteristics:

1. Finiteness: It terminates after finite number of steps


2. Input: Takes a valid precisely defined input


3. Output: Generates output that is expected.


4. Definiteness: The steps are rigiously and unambigiously specified.


5. Effectiveness: the steps are sufficiently simple and basic.

II. Devising
A. Expressing
(1) English, (pure language) (easy but the most least precise)
(2) pseudocode, or (Language that dosn't give any syntax errors) (better happy medium)
(3) a real programming language (difficult to write and understand)

B. Validation
How to prove that the algorithm works?
one of the hardest parts?
it is easy to convince our selves that an algorithm works for a simple problem. But actual validation of the problem is diffult we need abstract problem specifications.

For validation
1. specify (all the assumptions and consider all the possibilities)
duplicate numbers in input, ordering of duplicates, etc.

2. Proof:
a. formal proof: -predicate calculus
use mathematical language to describe each component
from input ---> operation ---->ouput

b. informal proof: "it is obvious that..."
an argument is broken down into small steps
problem: brittle, make one wrong assuption, everrything falls apart.

c. Testing: give conctret input and see if it gives proper or expected outputs
problem: can not test all cases, in somecases you can...

Problem of not knowing the correct answer sometimes:
try solving different methods and verify if the solutions match to the other kwon method..

Axioms: The assumptions that are made
Lemas: the small parts of the theoroms, simpler parts, pieces of proofs
Theorms: the goal to reach,

C. Analysis

D. Computing models
E. Time complexity
1. Size of problem
2. Best/Average/Worst-case analysis
F. Space complexity
G. Simplicity/understandability
H. Optimality
III. Complexity
A. Complexity bounds
1. Asymptotic notation
o
O




B. Relations between asymptotic
bounded classes
C. Typical complexities
1. Polynomial
2. Polynomial-bounded
3. Exponential
4. Factorial
5. Logarithmic
IV. Recurrences
A. Iteration method
B. Substitution method
C. Master Method
D. Master method
V. Sorting
A. Proof of ( log )n n for comparison
sorts
B. Quicksort
1. Average-case analysis
2. Optimizations
a) Use of sentinels
b) Non recursive algorithm
c) Stack depth consideration
d) Median-of-three
e) Handling of small sublists
C. Counting sort
D. Radix sort
VI. Searching
A. Binary search
B. Interpolation search
C. Digital search tree
D. Tries
E. Patricia trie
VII. Convex hull algorithms
A. O(n2) algorithm (using cross-products)
B. Quick hull (idea only)
C. Graham’s algorithm (idea only)
D. Reduction / optimal complexity bound
VIII. Graphs
A. Terminology
B. Representation
C. Traversal & related algorithms
1. bfs
2. dfs
D. Related algorithms
1. Prim’s algorithm
2. Dijkstra’s algorithm
3. Topological sorting
4. Strongly connected components
From here forward is ~60% of exam
E. Union-find
1. Kruskal’s algorithm
2. Components in directed graphs
F. Flow graphs
1. Flow network definitions
a) [muliple] source/sink
b) Capacity constraints
2. Maximum flow problem
a) Cancellation
b) Ford-Fulkerson method
(1) residual networks
(2) augmenting path
(3) residual capacity
c) cuts & max-flow/min-cut theorem
d) example (maximum bipartite matching)
IX. NP Completemess
A. Notion of tractability
B. Abstract problem
1. Types (decisions, combinatorial...)
C. Concrete problem
1. Definition
2. Encoding
3. Encoding efficiency
D. Language Theory
1. Terminology
2. Accept vs decide string
E. Complexity class P
1. Definitons
F. Verification algorithms
G. Nondeterministic algorithms
H. Complexity class NP
NP problems and NP-Complete problems (our intrest topic)
For NP-complete problems, although there is no effecient algorithm found for NPC probs, nobody has ever proven that an efficient algorithm for one cannot exist. in other words, it is unknown whether or not efficient algorithms exist for NPC problems. Second, the set of NP-Complete probs has the remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. Third, several NPC probs are similar but not identical, to problems for which we do know of efficet algorithms. A small change to the problem statement can cause a big change to the efficiency of the best known algorithm.

1. definitons
2. relation to class P
I. Complexity class NP-Complete
1. Cook’s Theorem
2. Evidence for P NP
3. Polynomial-time reduction
4. Proof method that problem is NPC
5. Examples of NPC problems
J. Complexity class NP-Hard
1. Definitions
K. Relationship between complexity
classes