Algorithmics 1
Useful Textbooks
- M.T. Goodrich & R. Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley, 2002
- D. Harel & Y. Feldman, Algorithmics: the Spirit of Computing, Addison Wesley, 2004 (also earlier 1992 edition by D. Harel)
- M. Sipser, Introduction to the Theory of Computation, Course Technology, 2006
Contents
Introduction
Fundamental Algorithms and Data Structures
Sorting Algorithms
Strings and text algorithms
Graphs and graph algorithms
NP Completeness
Computability
Introduction
Revision - Algorithm Analysis
- Time and space complexity is written as a function of input size
- Worst case - gives a guarantee of algorithm’s performance
- Asymptotic behaviour indicates what will happen as input size grows
- Expressed using Big O notation
Big O notation
f(n) = O(g(n))
f
grows no faster thang
- there exists a real constant
c
and integer constantN
such that|f(n)| <= |c*g(n)|
for alln => N
f
is usually a complex function, which is not known preciselyg
is a known function eg O(1), O(n) etc- use the “tightest”
g
we can find for an algorithm
Log function
- x = logan if n = ax
- loga m * n = logam + logan
- loga m / n = logam - logan
- loganc = c * logan
Time complexities
For some constant c
:
- Polynomial-time = O(nc)
- Exponential-time = no better than O(cn) where
c > 1
Fundamental Algorithms and Data Structures
- Stacks, queues and priority queues
- Complete binary trees
- Heaps and heap operations
- Java class for (integer) heaps
- Heap sort
Stack abstract data type (LIFO)
Basic operations:
- create
- isEmpty
- push (to top of stack)
- pop (delete and return from top of stack)
Represent it as:
- an array - all operations are O(1)
- a linked list - all operations are O(1)
Queue abstract data type (FIFO)
Basic operations:
- create
- isEmpty
- insert (to the back of queue)
- delete (delete and return item at front of queue)
Represent it as:
- an array - all operations are O(1) and it must be “wrapped around”, treated as circular
- a linked list - all operations are O(1)
Priority queue abstract data type
Basic operations:
- create
- isEmpty
- insert (new item with given priority)
- delete (delete and return item with highest priority)
Represent it as:
- unordered list - insert O(1), delete O(n)
- ordered list - insert O(n), delete O(1)
- heap - insert and delete are O(logn)
- in all cases create and isEmpty are O(1)
Complete Binary Trees
Height of a node:
- length of the longest path from the node to a leaf
- height of a heap is the height of its root node
- a binary tree of height
h
can contain maximum 2h+1 - 1 nodes - therefore the height of a CBT with
n
nodes is é log2( n + 1 ) - 1 ù
A complete binary tree with n
nodes has:
- the minimum possible height
- the maximum possible number of nodes at each level except the last (ie for
i = 0, ... , h - 2
, leveli
has 2i nodes - the nodes on the last level are as far to the left as possible
Properties of a CBT:
- with a height
h
, it has at most 2h+1 - 1 nodes - with
n
nodes, its height is é log2( n + 1 ) - 1 ù - then it has é n / 2 ù leaf nodes
- and it has ⌊ n / 2 ⌋ branch nodes
Heaps
Def: A CBT where each node stores an item, and has a priority value
Heap property: Every node’s priority is greater than or equal to the priorities of all its descendent nodes
Min-heap: Inverted so that the minimum priority is at the root
For a node i
:
- its children are nodes
2i + 1
and2i + 2
- its parent is the node
⌊ (i - 1) / 2 ⌋
Basic operations:
- insert an item
- build a heap containing a given set of items
- delete the item with highest priority
- impose the heap property on a given node
Complexity:
- build is O(n log n) and there is an O(n) alternative
- all other operations are O(log n) for algorithms which take O(1) steps at each level of the heap
Insertion:
while (new_value NOT in root && new_value > parent_value)
swap new_value with parent_value
Imposing:
Pre-condition - a specified node may violate the heap property, but all its descendents satisfy the property
Post-condition - the specified node and all of its descendents satisfy the property
while (bad_value NOT in leaf && bad_value < larger_child)
swap bad_value with larger_child
Deletion:
swap root with node in last (bottom-right) leaf
delete last leaf
impose heap property on bad value now in root
Building:
Pre-condition - values are in arbitrary order
Post-condition - values form a heap
for each non-leaf node in bottom-to-top right-to-left order
impose heap propery
An integer heap class
Represent using an array, where:
- children of a node
i
are in the array at2i + 1
and2i + 2
- parent of a node
i
are in the array at(i - 1) / 2
(floored automatically in Java)
Heap class implementation in Java
Heap Sort
- more efficient than selection sort
- O(n log n) in the worst case
- pseudocode
Sorting Algorithms
- Comparison-based sorting
- Radix sort
- Tries (retrieval)
Common sorts:
O(n2) - selection, insertion, bubble
O(n log n) - merge, heap
Quicksort is O(n log n) on average (but no better than O(n2) in the worst case
Comparison-based sorting
Claim: No sorting algorithm that is based on pairwise comparison can be better than O(n log n) in the worst case
Justification: Draw out the algorithm using a binary decision tree, where each node represents a comparison between two elements
- leaf nodes represent the possible outcomes of the algorithm
- so the number of leaf nodes = the possible ordering of
n
items - so there are at least
n!
and maximum 2h+1 leaf nodes - its worst case complexity is O(h) where
h
= its height - it follows that n! <= 2h+1
Reversing inequality and taking log2 of both sides:
Giving a complexity of O(n log n) as required
Radix sorting
- O(n) complexity
- exploits the structure of items to be sorted to achieve this
- faster than O(n log n) only for very large
n
How it works:
- each iteration the items are distributed into buckets (lists)
- during an
i
th iteration an item is placed in the bucket corresponding to the integer represented by its bits - at the end of an iteration the buckets are concatenated to give a new sequence which will be used as the starting point of the next iteration
- there are
m / b
iterations, wherem
is the length of bit-sequences representing an item, andb
is a chosen factor ofm
To sort the following sequence: 15 43 5 27 60 18 26 2
Where binary encodings are given by:
15 = 001111 43 = 101011 5 = 000101 27 = 011011
60 = 111100 18 = 010010 26 = 011010 2 = 000010
Items have bit positions 0, …, 5 so m
= 6
b
must be a factor of m
, so choose b
= 2
So we have 2b = 22 = 4 buckets labelled 0, 1, 2, 3 (or 00, 01, 10, 11)
And m / b = 3
iterations are required
See radix sorting pseudocode here
Correctness: For two items x
and y
where x < y
, we need to show that x
precedes y
in the final sequence
During the last iteration where some bits of x
and y
differ:
- the bits of
x
must be smaller thany
- so
x
goes into a bucket beforey
does - so
x
precedesy
in the sequence after this iteration - in later iterations,
x
andy
go in the same bucket as they don’t have any more differing bits
Complexity:
- during each of the
m / b
iterations, the sequence is scanned –> O(n) time, and buckets are concatenated –> O(2b) time - overall, O(m / b (n + 2b)) –> O(n)
Time-space trade-off:
- the larger the value of b, the smaller the multiplicative constant (m / b) in the complexity function and so the faster the algorithm will become
- an array of size 2b is required, so increasing
b
will increase space requirements
Tries
- stored items have a key that is interpreted as a sequence of bits/characters
- there is a multiway branch at each node where each branch has an associated symbol
- no two siblings have the same symbol
- the branch to be taken at level
i
is determined by thei
th element of the key - tracing a path from root to a node spells out the key of the item
- eg, used to store strings
Search and insert algorithms for the trie found here
Represent it as:
- an array of pointers, which represent children
- linked lists, containing children of each node
Example trie class to represent a dictionary
Strings and text algorithms
Text compression
- lossless
- compression ratio is
x / y
wherex
= compressed andy
= original - space saved =
1 - (x / y) * 100%
Huffman encoding
- statistical method
- unique, variable-length codeword for each character
- no codeword is the prefix of another
- each character is a leaf node
- codeword is the path from root to appropriate leaf
- when going down the path, left route = 0, right route = 1
Huffman tree construction:
- add leaf nodes containing the character represented and its frequency
- while there are > 1 parentless nodes
- add new parent to the two nodes of smallest weight (frequency)
- weight of the parent node = sum of child weights
The tree for a file with char frequencies:
Space = 15 E = 11 A = 9 T = 8 I = 7 S = 7
R = 7 O = 6 N = 4 U = 3 H = 2 C = 1 D = 1
Tree construction pseudocode
Generating the codewords:
- following left and right paths down the constructed tree
- Space
10
- E
010
- A
111
- T
110
- I
0000
- S
0001
- R
0011
- O
0110
- N
0111
- U
00101
- H
001001
- C
0010000
- D
0010001
- Space
Weighted path length of tree T:
SUM( weight * distance from root )
- sum is over all leaf nodes
- this gives the number of bits in the compressed file
Complexity:
- building tree - O(n)
- compression - O(n)
- decompression - O(n)
- use adaptive Huffman coding
- same tree built and adapted by compressor and decompressor
LZW compression
- dictionary method
- collection of strings, each with a bit pattern that represents it
- dictionary built dynamically during compression and decompression
- if string
s
is represented, so is every prefix ofs
- a trie is an ideal representation
At any given time during comp./decomp. there is a current codeword length k
:
- 2k distinct codewords available
- limits size of dictionary, but can be incremented as necessary (so doubling the codeword availability)
- initial
k
should be large enough to encode all strings of lengthl
LZW compression pseudocode
LZW variants:
- constant - fixed capacity dictionary
- dynamic - add 1 to current length whenever dictionary becomes full
- LRU - when full, current string replaces the least recently used string in the dictionary
LZW decompression:
- builds same dictionary as compression but 1 step out of phase
- may encounter codeword that is not in dictionary
- if (lookup fails) newS = oldS + oldS.charAt(0);
LZW decompression pseudocode
Complexity: O(n) for comp. and decomp. each
String comparison
- given strings
s
andt
of lengthsm
andn
, what is the smallest number of basic operations needed to transforms
intot
? - use
- insertion
- deletion
- subsitution
String distance:
Prefixes:
i
th prefix of strings
is firsti
chars ofs
- let
d( i,j )
= distance between prefixi
ofs
and prefixj
oft
- then distance between
s
andt
=d( m,n )
forlen(s) = m
andlen(t) = n
Optimal alignment:
The last position of the alignment must either be of the form
In other words,
Distance with dynamic programming
- fill in entries of an
m * n
table row by row, and column by column - time and space complexity = O(mn)
- keep most recent entry in each column of the table
- space complexity = O(m + n)
Distances table:
- entries calculated one by one by applying formula above
- final entry
d( 7,8 ) = 4
so string distance is 4 - trace back to entry
( 0,0 )
to find optimal alignment- vertical = deletion
- horizontal = insertion
- diagonal = match/substitution
String/pattern search
Given a text t
of length n
, and a string/pattern s
of length m
, find the position of the last occurence of s
in t
Brute force algorithm
- current starting position in text = 0
- compare chars from
s
andt
left to right until the entire string is matched - if mismatch, advance starting position by 1 and repeat
Brute force pseudocode
Effectiveness:
- expressed using char arrays rather than strings in Java
m
char comparisons needed at eachn - (m + 1)
positions in text before the pattern is found- worse case O(mn)
- average case O(n)
KMP algorithm
- online - removes need to back-up in text
- worst case O(n)
- need to pre-process the string into a border table (an array
b
with an entryb[j]
for each positionj
) - if mismatch at
j
, remain at current text char - the border table says what to compare next
Border of a string s
:
- a substring that
- is a prefix
- is a suffix
- cannot be the string itself
- eg for string
s = a c a c g a t a c a c
- borders are
ac
andacac
acac
is the longest border
- borders are
Border table:
b[j]
is- the length of the longest border of
s[0...j-1]
max { k | s[0...k-1] = s[j-k...j-1] }
- the length of the longest border of
KMP seach :
- implementation
- this is O(n) worst case
- naive method requires O(j2) steps to find
b[j]
, so O(m2) overall - can be implemented in O(m + n) time (to set up border table and to conduct search)
Boyer-Moore algorithm
- string scanned left-to-right
- mismatched char used to decide next comparison
- need to pre-process string to record position of last occurence of each char in the alphabet
- alphabet must be fixed in advance of search
Position of last occurence of char c
in string s
:
max { k | s[k] = c }
if such ak
exists,-1
otherwise- store last occurence position of
c
in array elementp[c]
Jump steps on a mismatch:
- if mismatch between
s[j]
andt[i]
, moves
along sop[t[i]]
ofs
aligns witht[i]
- if this moves
s
in the “wrong direction”, instead moves
one position to the right - if
t[i]
doesn’t appear in the string, slide the string pastt[i]
Jump step cases:
p[t[i]] < j and => 0
- new
i = i + m - 1 - p[t[i]]
- new
j = m - 1
- new
sp = sp + j - p[t[i]]
(starting position)
- new
p[t[i]] > j
- new
i = i + m - j
- new
j = m - 1
- new
sp = sp + 1
- new
p[t[i]] = -1
- new
i = i + m
- new
j = m - 1
- new
sp = sp + j + 1
- new
BM complexity:
- worst case O(mn)
- search for
s = ab...aa
of lengthm
int = aa...aaaa..aa
of lengthn
m - 1
char comparisons needed at eachn - (m + 1)
positions in text
Graphs and graph algorithms
Graph basics
Undirected graphs:
G = (V,E)
- each vertex is a point
- each edge is a line joining a pair of vertices
Connected: every vertex pair is joined by a path
Non-connected: graph has 2+ connected components
Tree: connected and acyclic (no cycles)
Forest: acyclic and components are trees
Complete (clique): every vertex pair is joined by an edge
Bipartite: vertices are in two dijoint sets U
and W
and every edge joins a vertex in U
to one in W
For the graphs above:
- adjacent -
{ a,z } Î E
- non-adjacent -
{ a,b } ∉ E
a
is incident to edge{ a,z }
a, x, b, y, c
is a path of length 4a, x, b, y, a
is a cycle of length 4- all vertices have degree 3
Directed graphs (digraphs):
D = (V,E)
whereV
andE
are finite sets- edges are ordered pairs
- drawn as arrows
- vertices have in-degrees and out-degrees
- paths and cycles must follow edge directions
In the graph above:
u
is adjacent tov
v
is ajdacent fromu
y
has in-degree 2 and out-degree 1
Graph representations
Representing the undirected graph G:
Representing the directed graph D:
Implementing adjaceny lists:
Define classes representing
- an entry of adjacency lists
- a vertex (with a linked list representing its adjacency list)
- a graph (with a size and an array of vertices)
Java implementation of an adjacency list
Graph searching and traversal algorithms
Graph traversal is efficient if it visits all vertices of the graph in O( |V| + |E| )
time (by travelling along edges)
Depth-first search:
- follow a path of unvisited vertices until path can be extended no further
- backtrack until an unvisited vertex is reached
- repeat until there are no unvisited vertices (in all components of graph)
- edges used form a depth-first spanning tree
Represent it as:
- explicit stack
- containing vertices on the path to the current vertex
- popping corresponds to backtracking
DFS example:
DFS implementation
DFS complexity:
- each vertex is visited (
n
) - each element in adj. list is processed (
m
) - O(n + m)
- can adapt to adj. matrix representation, but this increases complexity to O(n2)
Applications of DFS:
- determine if graph is connected and/or identify its connected components
- determine if a graph is bipartite
- determine if a graph contains a cycle
Breadth-first search:
- visit all adjacent vertices of current vertex (processing)
- vertices processed in the order in which they are visited (queue)
- continue until all vertices in current component have been processed
- edges used form a breadth-first spanning tree
Represent it as:
- queue
- visited vertices are added
BFS example:
BFS implementation
BFS complexity:
- each vertex visited and queued exactly once
- each adj. list traversed once
- O(n + m)
- can adapt to adj. matrix as with DFS, but also O(n2)
Applications of BFS:
- finding distance between two vertices
Distance between two vertices:
- assign distance
v = 0
- carry out BFS from
v
- when visiting a new vertex
- assign its distance to be
1 + distance to its predecessor
- assign its distance to be
Weighted graphs
Each edge e
has an integer weight given by wt( e ) > 0
(undirected or directed)
Can represent weighted graphs using adj. lists and matrices as before
Dijkstra’s algorithm:
- finds shortest path from one vertex
u
to all other vertices - maintains a set containing all vertices for which shortest path from
u
is currently known - each vertex
v
not in the set has a labeld(v)
= length of a shortest path fromu -> v
passing only through vertices in the set - after adding
v
to the set, carry out edge relaxation (updating distanced(w)
for all verticesw
still not in the set)
Edge relaxation:
- suppose
v
andw
are not inS
, then we know- the shortest path from
u -> v
passing only throughS
isd(v)
- the shortest path from
u -> w
passing only throughS
isd(w)
- the shortest path from
- suppose
v
is added toS
and the edgee = { v,w }
has weightwt( e )
- calculate the shortest path
u -> w
passing only throughS ∪ { v }
It is either:
- the original path through
S
of lengthd(w)
- the path combining edge
e
and shortest pathv -> u
with lengthwt( e ) + d(v)
Therefore, the distance is:
d(w) = min{ d(w), d(v) + wt( e ) }
Dijkstra’s algorithm implementation
Dijkstra complexity:
- with
n
vertices andm
edges, using an unordered array- O(n) to initialise distances
- O(n2) to find minimum
- O(m) for relaxation
-
hence, O(n2) overall
- with
n
vertices andm
edges, using a heap- O(n) to initialise distances and create heap
- O(n log n) to find minimum
- O(m log n) for relaxation
- hence, O(m log n) overall (more edges than vertices)
Dijkstra example:
Spanning tree:
- subgraph which is both a tree and spans every vertex
- obtained from a connected graph by deleting edges
- its weight = sum of weights of its edges
For a weighted connected undirected graph, find a minimum weight spanning tree (represents the cheapest way of interconnecting the vertices)
Minimum weight spanning tree problem:
This is an example of a greedy algorithm
- makes a sequence of decisions based on local optimality
- ends up with the globally optimal solution
Prim-Jarnik algorithm:
- minimum spanning tree contructed by choosing a sequence of edges
- initialisation is O(n) (where
n
is number of vertices) - outer loop executed
n - 1
times - inner loop checks all edges from a tree-vertex to a non-tree vertex, of which there can be O(n2)
- overall, alg. is O(n3)
Prim-Jarnik algorithm pseudocode
Prim-Jarnik example
The Prim-Jarnik proof of correctness will not be part of the exam, so it is omitted here.
Dijkstra’s refinement:
Introduce attribute bestTV
for each non-tree vertex q
This is the best tree vertex p
for which wt( {p, q} )
is minimised
Pseudocode for this concept
- initialisation is O(n)
- while loop executed
n - 1
time - O(n) to find minimal ntv
- O(1) to adjoin and update
- overall alg. is O(n2)
Topological ordering
Directed Acyclic Graphs:
A topological order on a DAG is a labelling of the vertices 1, ..., n
such that (u, v) Î E
implies label(u) < label(v)
A directed graph D has a topological order if and only if D is a DAG
A source is a vertex of in-degree 0 and a sink has out-degree 0
A DAG has at least one souce and at least one sink, which forms the basis of a topological ordering alg.
Topological ordering of DAG D
:
Topological ordering alg. implementation
TOA correctness:
A vertex is given a label only when the number of incoming edges from unlabelled vertices is 0
For n
vertices, m
edges:
Adj. matrix representation involves
- finding in-degree of each vertex, by scanning each column - O(n2)
- main loop executed
n
times for each row - O(n) - overall alg. is O(n2)
Adj. list representation involves
- finding in-degree of each vertex, by scanning the list - O(n + m)
- main loop executed
n
times for each list - overall alg. is O(n + m)
Deadlock detection:
Methods to detect whether a digraph contains a cycle
- adaptation of topological ordering alg.
- if source list becomes empty before all vertices are labelled, there must be a cycle
- if all vertices can be labelled, the digraph is acyclic
- adaptation of DFS
- when a vertex is visited, check where there is an edge from it to another vertex which is on the current path from the current starting vertex
- the existence of such a vertex indicates a cycle
NP Completeness
- Introduction
- NP-complete problems
- The classes P and NP
- Polynomial-time reductions
- Formal def. of NP-completeness
- How to prove a problem is NP-complete
Introduction
We have seen algorithms for a wide range of problems, all of which are polynomial-time: their worst cast complexity is O(nc) for some constant c
Recall the Eulerian cycle problem: whether a graph has a cycle that traverses each edge exactly once
Theorem: A connected undirected graph has an Eulerian cycle if and only if each vertex has even degree
Therefore we can test and find such a cycle in a graph G
in
- O(n2) time if
G
is represented with an adj. matrix - O(m + n) if it is represented with an adj. list (
m = |E|
andn = |V|
)
Recall the Hamiltonian cycle problem: whether a graph has a cycle that traverses each vertex exactly once
It is similar to the Eulerian cycle problem, but a polynomial-time algorithm has not been found to solve it
Its complexity is O(n2 * n!) in the worst case
No polynomial-time algorithm has been found to solve this
Therefore this problem is NP-complete
- this is exponential (no better than O(bn) for some
b
) - and cannot be expressed as O(nc)
Polynomial vs exponential:
Similar behaviour emerges in terms of computing power
Basically, a thousand-fold increase in computing power would only add 6
to the size of the largest problem instance solvable in 1
hour, for an algorithm of 3n complexity
A problem is polynomial-time solvable if it admits a polynomial-time algorithm
NP-completeness
No polynomial-time algorithm is known for an NP-complete problem
However, if one of them is solvable, then they all are
No proof of intractability is known for an NP-complete problem
However, if one of them is intractable, then they all are
Causes of intractability:
- polynomial time is not sufficient in order to discover a solution
- there are intractability proofs for this
- some problems are undecidable (no alg. could solve them)
- some decidable problems have been shown to be intractable
- solution itself is so large that exp. time is needed to output it
- eg problems of generating all cycles for a given graph
Roadblock:
- two players A and B
- network of roads, with intersections
- each road is coloured black, blue or green
- some intersections are marked “A wins” or “B wins”
- a player has a fleet of cars located at intersections (one car per intersection)
Player A begins, and then they take turns to
- move a car of theirs on one or more roads of the same colour
- a car may not overlap an intersection which already has a car
The problem is deciding, for a given starting configuration, whether A can win, regardless of what moves B takes
So, NP-complete problems
must be equal to one of: Polynomial-time solvable problems
or Intractable problems
, and not equal to the other
Problems:
A problem is characterised by unspecified parameters
A problem instance is created by giving these parameters values
An example of a decision problem is the Hamiltonian cycle:
- the answer is a “yes” or “no”
- its instance if a graph
G
- every instance is either a “yes”-instance or a “no”-instance
Other NP-complete problems:
Travelling Salesman Decision Problem
Instance: a set of n
cities and integer distance d(i, j)
between each pair of cities i, j
and a target integer K
Question: is there a permutation P1P2...Pn-1Pn
of 1, 2,..., n
such that d(P1, P2) + d(P2, P3) + ... + d(Pn-1, Pn) + d(Pn, P1) <= K
?
Clique Problem
Instance: a graph G
and target integer K
Question: does G
contain a clique of size K
? (a set of K
verices for which there is an edge between all pairs
Graph Colouring Problem
Instance: a graph G
and target integer K
Question: can one of K
colours be attached to each vertex of G
so that adjacent vertices always have different colours?
Satisfiability
Instance: boolean expression B
in conjunctive normal form
CNF: C1 ∧ C2 ∧ ... ∧ Cn
where each Ci
is a clause
Clause C
: L1 ∨ L2 ∨ ... ∨ Lm
where each Lj
is a literal
Literal L
: a variable x
or its negation ¬x
Question: is B
satisfiable? (can values be assigned to the variables that make B
true?)
NP-completeness deals primarily with decision problems
- corresponding to each instance of an optimisation or search problem
- there is a family of instances of a decision problem obtainable by setting “target” values
- an optimisation or search problem can be solved in poly. time if and only if the corresponding decision problem can
The classes P and NP
P:
- the class of all decision problems that can be solved in poly. time
- often extended to include search and optimisation problems
NP:
- the class of decision problems solvable in non-deterministic polynomial time (a non-deterministic alg. can make non-deterministic choices, and hence is more powerful than a deterministic alg.)
- P is contained within NP
- there is no problem known to be in NP and known not to be in P
P vs NP:
A decision problem is NP if every “yes”-instance has a short certificate
i.e. a structure that can be used to verify, in polynomial time, that it is a “yes”-instance
No corresponding claim is made for “no”-instances
It is immediate that P ⊆ NP
, but whether P = NP
or P ⊂ NP
is unknown
Most believe that P ≠ NP
But if so, there are problems that must lie in NP and not in P, and these are the NP-complete problems (the hardest, eg HC, TSDP, Graph Colouring etc)
A poly. time alg. for any of these would imply that they are all in P
Non-deterministic algorithms:
- has an extra operation: non-deterministic choice
- has many possible executions depending on values returned from the choice
- it solves a decision problem
Π
if- for a “yes”-instance
I
ofΠ
there is some execution that returns “yes” - for a “no”-instance
I
ofΠ
there is no execution that returns “yes”
- for a “yes”-instance
- and solves a decision problem
Π
in poly. time if- for every “yes”-instance
I
ofΠ
there is some executionE
that returns “yes”, which uses a number of steps bounded by a polynomial in the input
- for every “yes”-instance
A non-deterministic alg. can be viewed as
- a guessing stage (non-deterministic)
- a checking stage (deterministic and poly. time)
Start —> guess a “certificate” —> verify the certificate —> Stop
Example of a non-deterministic alg.
Polynomial-time reductions
A mapping f
from a decision problem Π1
to a decision problem Π2
such that
- for every instance
I1
ofΠ1
we have- the instance
f(I1)
ofΠ2
can be contructed in poly. time f(I1)
is a “yes”-instance ofΠ2
if and only ifI1
is a “yes”-instance ofΠ1
- the instance
- we write
Π1 ∝ Π2
as an abbreviation for: there is a polynomial-time reduction fromΠ1
toΠ2
Properties of polynomial-time reductions:
Transitivity: Π1 ∝ Π2
and Π2 ∝ Π3
implies that Π1 ∝ Π3
Since Π1 ∝ Π2
and Π2 ∝ Π3
we have
- a PTR
f
fromΠ1
toΠ2
- a PTR
g
fromΠ2
toΠ3
For any instance I1
of Π1
, since f
is a PTR, we have
I2 = f( I1 )
is an instance ofΠ2
that can be constructed in poly. timeI2
has the same answer asI1
Since g
is a PTR, we have
I3 = g( I2 )
is an instance ofΠ3
that can be constructed in poly. timeI3
has the same answer asI2
Putting the results together, for any instance I1
of Π1
I3 = g( f( I1 ) )
is an instance ofΠ3
constructed in poly. timeI3
has the same answer asI1
- ie the composition of
f
andg
is a PTR fromΠ1
toΠ3
Π1 ∝ Π2
and Π2 Î P
implies that Π1 Î P
- to solve an instance of
Π1
, reduce it to an instance ofΠ2
Π1 ∝ Π2
means thatΠ1
is no harder thanΠ2
- i.e. if we can solve
Π2
, then we can solveΠ1
without much more effort
For example, reducing the Hamiltonian cycle problem to the travelling salesman problem:
HC instance: a graph G
HC question: does G contain a cycle that visits each vertex exactly once?
TSDP instance: a set of n
cities and integer distance d(i, j)
between each pair of cities i, j
and a target integer K
TSDP question: is there a permutation p
of {1, 2,..., n}
such that d(P1, P2) + d(P2, P3) + ... + d(Pn-1, Pn) + d(Pn, P1) <= K
?
G = (V, E)
is an instance of HC- construct TSP
f(G)
where- cities =
V
d(u, v) = 1
if{u, v} Î E
and0
otherwiseK = |V|
- cities =
f(G)
can be constructed in poly. timef(G)
has a tour of length<= |V|
if and only ifG
has a Hamiltonian cycle (cannot take any of the edges with weight 2)- therefore
TSDP Î P
implies thatHC Î P
- equivalently
HC Ï P
implies thatTSDP Ï P
Definition
A decision problem Π
is NP-complete if
Π Î NP
Π’
is polynomial-time reducable toΠ
(Π’∝Π
for every problemΠ’
in NP)
So if Π
is NP-complete and Π Î P
then P = NP
Every problem in NP can be solved in polynomial time by reduction to Π
Supposing P ≠ NP, if Π
is NP-complete, then Π Ï P
Proving NP-completeness
It is not feasible to describe a reduction from every problem in NP
However, suppose we knew just one NP-complete problem Π1
To prove Π2
is NP-complete, it is enough to show
Π2
is in NP- there exists a polynomial-time reduction from
Π1
toΠ2
(Π1 ∝ Π2
)
Correctness of the approach:
- for any
Π' Î NP
, sinceΠ1
is NP-complete we haveΠ' ∝ Π1
- since
Π' ∝ Π
,Π1 ∝ Π2
and in is transitive, it follows thatΠ' ∝ Π2
- since
Π' Î NP
was arbitrary,Π' ∝ Π2
for allΠ' Î NP
- hence
Π2
is NP-complete
Cook’s Theorem, where the Satisfiability (SAT) problem is NP-complete
- proof consists of generic poly-time reduction to SAT from an abstract definition of a general problem in NP
- generic reduction could be instantiated to give an actual reduction for each individual NP problem
- given this theorem, to prove that problem P is NP-complete it is sufficient to show that
Π
is in NP- there exists a poly-time reduction from SAT to
Π
Clique Problem:
Instance: graph G and target integer K
Question: does G contain a clique of size K?
Proving: show clique is in NP, and that there exists a poly-time reduction from SAT to Π
We need to show SAT ∝ Clique:
Given an instance B of SAT we construct a (G, K)
instance of Clique
- K number of clauses of B
- vertices of G are pairs
(l, C)
wherel
is a literal clause ofC
{(l, C), (m, D)}
is an edge of G if and only ifl ≠ ¬m
andC ≠ D
- edge if distinct literals from different clauses can be satisfied simultaneously
- poly-time construction O(n2) (with
n
literals) - this is a poly-time reduction since B has a satisfying argument if and only if G has a clique of size K
Proving it is a poly-time reduction:
- if B has a satisfying assignment then
- if we choose a true literal in each clause the corresponding vertices form a clique of size K in G
- if G has a clique of size K then
- assigning each literal associated with a vertex in the clique to be true yields a satisfying assignment for B
The following graph G has a clique of size 4 if and only if B has a satisfying assignment (which is a clique of size 4 here)
B = (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ x3 ∨ ¬x4) ∧ (¬x2 ∨ x4) ∧ (x2 ∨ ¬x3 ∨ x4)
There are K = 4 clauses (bracket pairs)
Problem restrictions:
A restriction consists of a subset of the instances of the original problem
If a restriction of a given decision problem Π
is NP-complete, then so is Π
Given NP-complete Π
, a restriction of Π
might be NP-complete
eg a clique restricted to cubic graphs is in P, so a largest clique has size at most 4, so exhaustive search is O(n4)
K-colouring:
Restriction of Graph Colouring for a fixed K number of colours
2-colouring is in P, while 3-colouring is NP-complete
K-SAT:
Restriction of SAT in which every clause contains exactly K literals
2-SAT is in P, while 3-SAT in NP-complete
Showing 3-SAT Î NP is easy
SAT ∝ 3-SAT:
Given instance B of SAT we will construct an instance B’ of 3-SAT
For each clause Ci of B we construct a number of clauses of B’
- if
C = l1
- introduce 2 additional variables x1 and x2, and add the clauses
(l1 ∨ x1 ∨ x2), (l1 ∨ x1 ∨ ¬x2), (l1 ∨ ¬x1 ∨ x2), (l1 ∨ ¬x1 ∨ ¬x2)
to B’
- introduce 2 additional variables x1 and x2, and add the clauses
- if
C = (l1 ∨ l2)
- introduce 1 additional variable y and the clauses
(l1 ∨ l2 ∨ y) and (l1 ∨ l2 ∨ ¬y)
to B’
- introduce 1 additional variable y and the clauses
- if
C = (l1 ∨ l2 ∨ l3)
- add the clause C to B’
- if
C = (l1 ∨ ... ∨ lk)
andk > 3
- introduce k - 3 additional variables z1, …, zk-3
- add the clauses
(l1 ∨ l2 ∨ z1), (¬z1 ∨ l3 ∨ z2), (¬z2 ∨ l4 ∨ z3), ..., (¬zk-4 ∨ lk-2 ∨ zk-3), (¬zk-3 ∨ lk-1 ∨ lk)
to B’
Coping with NP-completeness:
Maybe only a restricted version is of interest (which may be in P)
Seek an exponential-time alg. which improves on exhaustive search
For an optimisation problem:
- settle for an approximation alg. that runs in poly-time
- esp. if it gives a probably good result
- use a heuristic
For a decision problem:
- settle for a probabilistic alg. (correct answer with high probability)
Computability
Introduction
A computer is:
input x --> BLACK BOX --> output f(x)
The black box computes a function that maps an input to an output
What functions can be computed? Alternatively, what problems can be solved?
We need a definition of an algorithm if we view a computer as a device that can execute one
Some problems cannot be solved by a computer, eg the Tiling problem
A 1x1 square tile divided into 4 triangles by its diagonals with each triangle a given colour
Each tile has a fixed orientation and no rotations are allowed
Instance: a finite set S
of tile descriptions
Question: can any finite area, of any size, be completely covered using only tiles of types in S
, so that adjacent tile colours match?
For example, tiling a 5x5 square:
Or extending to a larger region:
- overlap the top two rows with the bottom two rows (for an 8x5 tiled area)
- place two of these 8x5’s side by side (with the right hand rectangle one row above the left hand rectangle)
- and repeat this pattern to tile any finite area
Tiling a 10x10 square:
There is no alg. for this problem
For any alg. A that we might formulate, there is a set of tiles S
for which either A doesn’t terminate or gives the wrong answer
The problem is that:
- “any size” means that we have to check all finite areas and there are infinitely many of these
- for certain sets of tile descriptions that can tile any area, there is no “repeated pattern” we can use
- would really have to be exhaustive
Undecidable problems:
A problem Π
that admits no alg. is called non-computable or unsolvable
If Π
is a decision problem and admits no alg., then it is called undecidable (tiling problem is one)
Post’s correspondence problem:
A word is a finite string over some given finite alphabet
Instance: two finite sequences of words X1, ..., Xn
and Y1, ..., Yn
(in the same alphabet)
Question: does there exist a sequence i1, i2, ..., ir
of integers chosen from {1, ..., n}
such that Xi1Xi2...Xir = Yi1Yi2...Yir
?
For n = 5
- X1 = abb, X2 = a, X3 = bab, X4 = baba, X5 = aba
- Y1 = bbab, Y2 = aa, Y3 = ab, Y4 = aa, Y5 = a
- correspondence given by sequence
2, 1, 1, 4, 1, 5
- word constructed from Xi’s = aabbabbbabaabbaba
- word constructed from Yi’s = aabbabbbabaabbaba
- however, if we removed the first letter from X1 and Y1, then we could never get a correspondence
- thus this problem is undecidable
The halting problem
Instance: a legal Java program X
and an input string S
for X
Question: does X
halt when run on S
?
We will prove that no such program can exist, and that thus, the halting problem is undecidable
The below program T
will terminate if and only if input n ≠ 1
public void t(int n) {
if (n == 1)
while (true)
null;
}
With a word “erratic”, T
is called with n = 7
sequence of values:
22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Then nobody knows whether “erratic” terminates for all values of n
Proof by contradiction that HP is undecidable:
Suppose we have alg. A
that solves HP
Let Q
be an implementation of this alg. as a Java method with X
and S
parameters
Define a new program P
with a legal program W
as input
P
makes a copy ofW
and callsQ(W, W)
Q
terminates by assumption- if it returns “yes”,
P
enters an infinite loop - if it returns “no”,
P
is terminated
Now let the input W
to P
be the program P
itself
Then P
would call Q(P, P)
(recall we assumed that Q
solves HP)
- if
Q
returns “yes”, then by definition ofQ
this meansP
terminates - but this also means
P
does not terminate (it enters into the loop) - this is a contradiction, therefore
Q
must return “no” - and this means by definition of
Q
thatP
does no terminate - but it also means that
P
does terminate - again, it is a contradiction
- so if it can return neither reply, no such
Q
can exist - therefore no alg. can solve HP
Proving undecidabiltiy by reduction:
Suppose we can reduce any instance I
of Π1
into an instance J
of Π2
such that I
has a “yes” answer for Π1
if and only if J
has a “yes” answer for Π2
(no need for J
to be constructed in poly-time)
If Π1
is undecidable and we can perform such a reduction, then Π2
is undecidable
Hierarchy of decision problems:
Models of computation
Deterministic finite-state automata (DFAs):
- simple machines with limited memory
- recognise input on a read-only tape
Consists of:
- a finite input alphabet
A
- a finite set of states
Q
- an initial state
q0 ∈ Q
and set of accepting statesF ⊆ Q
- control/program or transition relation
T ⊆ (Q * A) * Q
((q, a), q') ∈ T
means if in stateq
and reada
, then move to stateq'
- deterministic means that if
((q, a1), q1), ((q, a2), q2) ∈ T
eithera1 ≠ a2
orq1 = q2
- for any state and action there is at most one move
- initial state denoted by incoming arrow
- accepting states denoted by double circles
Control/program for the above example:
A DFA defines a language
- determines whether the string on the input tape belongs to that lang.
- ie solves a decision problem
- it accepts a lang., through the input strings which, when “run”, end in an accepting state
- in the above example, the DFA accepts the lang. consisting of the set of all strings comprising one or more a’s followed by one or more b’s (and its complement ie the language of strings with no consecutive a’s)
Non-deteministic finite-state automation (NFA):
This one recognises strings that start and end with a b
(in state q1
the b
underneath can move to q1
or q2
)
Recognition for NFA is similar to non-deterministics algs. solving a decision problem
- only require there exists a “run” that ends in an accepting state
- any NFA can be converted to a DFA
- therefore non-determinism doesn’t expand the class of languages that can be recognised by finite state automata
NFA to DFA reduction:
- use the subset construction
- states of DFA are sets of states of the NFA
- construction can cause a blow-up in number of states
Example without blow-up (recognises strings that start and end with b
):
Regular languages:
Languages that can be recognised by finite state automata
A reg. lang. over an alphabet A
can be specified by a regular expression over A
ε
and σ
are regex’s
Regular expressions:
If R
and S
are regex’s then so are (in order of lowest precedence first):
R | S
which denotes choiceRS
which denotes concatenationR*
which denotes 0 or more copies orR
(closure)(R)
which is needed to override operator precedence
Additional operations:
- complement
¬x
(equivalent to the “or” of all chars. inA
exceptx
) - any single char.
?
(equivalent to the “or” of all chars.)
Examples:
- the lang. comprising 1+ a’s followed by 1+ b’s
aa*bb*
- the lang. of string containing 2 consecutive a’s
(a* | b*)* a a (a* | b*)*
- the lang of strings that don’t contain 2 consecutive a’s
b* (abb*)* (ε | a)
- the lang. of strings that start and end with
b
b (a* | b*)* b
Note: L(R*)
does not mean { r* | r ∈ L(R) }
- for certain regex’s, this cannot be recognised by any DFA
- for such a lang., would need a memory to remember which string in
r ∈ L(R)
is repeated- might be an unbounded number
Regex example:
Consider lang. (aa*bb*)*
with DFA
A DFA can’t recognise { r* | r ∈ L(aa*bb*) }
- ie { (ambn)
* |
m > 0 and n > 0 } - would need to remember the
m
andn
to check that a string is in the lang. - infinitely many values for
m
andn
- so it would need infintely many states
- so, this is not a regular language
- similarly, it can’t recognise { (anbn)
* |
n > 0 }- might need to use a stack, where a’s are pushed as they are read, and popped as b’s are read (like a counter)
Pushdown automata:
- unlimited memory
- behave like a stack
Consists of:
- finite input alphabet
A
- finite set of stack symbols
G
- finite set of states
Q
including start state and set of accepting states - control/transition relation
T ⊆ (Q * AÈ{ε} * GÈ{ε}) * (Q * GÈ{ε})
Informally, the transition (q, a, w) --> (r, v)
means that
- if we are in state
q
- if
a ≠ ε
thena
is at head of tape - if
w ≠ ε
thenw
is at top of stack - move to state
r
and- if
a ≠ ε
then head++ - if
w ≠ ε
then popw
from stack - if
v ≠ ε
then pushv
onto stack
- if
A PDA accepts an input if and only if after the input has been read, the stack is empty and control is in an accepting state
There is no explicit test for empty stack, but you can just add a $
symbol to the stack at start of computation
Then check for emptiness when this symbol is at top of stack
The PDA defined here are non-deterministic (NDPDA)
More powerful than deterministic PDAs
ie it can recognise languages that the DPDA might not, such as palindromes
Palindromes:
Sequences of chars. that read the same backwards as forwards
Recognising with a PDA:
- push first half of sequence onto stack
- as you read each char., check that it’s the same as the top of the stack and pop that element
- enter an accepting state if all checks succeed
Why we need non-determinism:
- need to “guess” where middle of the stack is
- cannot work this out and then check string
- would need an unbounded number of states as the string could be of any finite length
Palindrome example:
- alphabet is
{a, b}
s0
is start state ands0
ands3
are the only accepting states(s0, ε, ε) --> (s1, $)
move tos1
and push$
onto stack(s1, a, ε) --> (s1, 1)
reada
and push1
(s1, b, 1) --> (s2, ε)
readb
and1
is on top, pop, move tos2
(s2, b, 1) --> (s2, ε)
readb
and1
is on top, pop(s2, ε, $) --> (s3, ε)
if$
is top, pop, move tos3
So the automaton recognises the language { (anbn) |
n => 0 }
PDA are more powerful than finite-state - can recognise languages that a DFA cannot
These languages are the context-free languages
Not all languages are context-free, for example, { (anbncn) |
n => 0 } cannot be recognised by a PDA
Turing Machines:
Recognises a particular languages consisting of:
- finite alphabet
Σ
, including blank symbol#
- unbounded tape of squares
- each holding a single symbol of
Σ
- unbounded in both directions
- each holding a single symbol of
- tape head that scans a single square
- read and write to square
- moves 1 square left/right along the tape
- set
S
of states- start state
s0
and two halt (or terminal) statessY
andsN
- start state
- transition function
- the inbuilt program
- of the form
f: ((S/{sY, sN}) * Σ) --> (S * Σ * {left, right})
For each non-terminal state and symbol, f
specifies
- a new state
- a new symbol
- a direction in which to move
f(s, σ) = (s', σ', d)
means reading σ
from the tape in state s
- move to state
s' ∈ S
- overwrite
σ
withσ ∈ Σ
- move head in the direction
d ∈ {left, right}
Computation:
- finite input string placed on tape
- head placed on first symbol of the input
- starts in state
s0
- if halts in state
sY
, answer is “yes” - if halts in state
sN
, answer is “no”
- if halts in state
Palindrome problem:
Instance: finite string Y
Question: is Y
a palindrome?
Java method for this
We can use a Turing machine for this problem, as we don’t need nondeterminism (don’t need to guess the middle)
TM algorithm for the palindrome problem
For this, we need the following states:
s0
reading, erasing and remember leftmost symbols1, s2
moving right, remembering symbol eraseds3, s4
testing for appropritate rightmost symbols5
moving back to leftmost symbol
A TM can be described with a state transition diagram
A directed graph where
- each state represented by vertex
f(s, σ) = (s', σ', d)
represented by an edge froms
tos'
labelled(σ --> σ', d)
- edge represents moving to
s'
σ --> σ'
represents overwriting symbol on taped
represents moving tape in a directiond
- edge represents moving to
Functions:
TM that accepts language L
actually computes the function f
where f(s) = 1
if s ∈ L
and 0
otherwise
The definition of a TM can be amended as follows:
- to have set
H
of halt states - function it computers is defined by
f(s) = s'
wheres
is inital strings'
is string on tape when the machine halts
eg, the palindrome TM can be redefined such that it deletes the tape contents and
- instead of entering
sY
, it writes1
on tape and enters halt state - instead of entering
sN
, it writes0
on tape and enters halt state
Designing a TM to compute f(k) = k + 1
:
- input 1 0 0 0 1 0, output 1 0 0 0 1 1
- pattern: replace rightmost
0
with0
- then moving right: if
1
, replace with0
and continue right / if blank, halt
- pattern: replace rightmost
- input 1 0 0 1 1 1, output 1 0 1 0 0 0
- same pattern as 1
- input 1 1 1 1 1, output 1 0 0 0 0 0
- this is a special case
- no rightmost
0
- replace first blank before input with
1
- then moving right: if
1
replace with0
and continue right / if blank, halt
TM algorithm for the above function
For this, we need the following states:
s0
initial state moving right seeking start of inputs1
moving left to rightmost0
or blanks2
finding first0
or blank, changing it to1
and moving right, changing1
s to0
ss3
halt state
Recognisable and decidable:
Language L
is Turing-recognisable if, given input string s
:
- if
s ∈ L
, then TM halts in statesY
- if
s Ï L
, then TM halts in statesN
or fails to halt
Language L
is Turing-decidable if, given input string s
:
- if
s ∈ L
, then TM halts in statesY
- if
s Ï L
, then TM halts in statesN
Every decidable language is recognisable, but not every recognisable language is decidable
A function f: S* --> S*
is Turing-computable if there is a TM M
such that, for any input s
, M
halts with output f(s)
Enhanced Turing Machines:
TM can be enhanced in a few ways
- 2+ tapes, rather than just one
- a 2-dimensional “tape”
- TM may operate non-deterministically (transition function may be a relation instead)
None of these enhancements change the computing power
- every lang./func. that is recognisable/decidable/computable with an enhanced TM is also R/D/C with a basic TM
- non-determinism adds power to PDA, but not to DFAs nor TMs
- proved by showing that basic TM can simulate any of these enhanced TMs
P and NP:
P often introduced as the class as decision problems solvable by a TM in poly-time
NP introduced as the class of decision problems solvable by a non-deterministic TM in poly-time
- in a non-deterministic TM, transition function replaced by a relation
f ⊆ ( (S * Σ) * (S * Σ * {left, right}) )
- can make a number of different transition based on current state and symbol at head
- non-det. doesn’t change what can be computed, but speeds it up
To show P ≠ NP, sufficient to show that a standard TM cannot solve an NP-complete problem in poly-time
Counter-programs:
These have
- vartiables of type
int
- labelled statements of the form
L: unlabelled_statement
- unlabelled statements of the form
x = 0
x = y + 1
x = y - 1
if x == 0 goto L
halt;
Counter program example
Church-Turing thesis:
Based on the fact that a whole range of different computational models turn out to be equivalent in terms of what they can compute
Reasonable to infer that any one of these models encapsulates what is effectively computable
This thesis states that everything “effectively computable” is computable by a TM (not a theorem as uses informal terms)
So there is an effective procedure for computing the value of the function, including all computers/programming langs. that we know about at present and even those we do not
So the TM is an appropriate model for the “black box”
Equivalent computational models (each can “simulate” the others):
- lambda calculus (Church)
- TMs (Turing)
- recursive functions (Kleene)
- production systems (Post)
- counter programs and all general purpose programming languages
Heap class implementation in Java
public class Heap {
int size;
int[] items;
// create empty heap of max capacity n
public Heap(int n) {
size = 0;
items = new int[n];
}
// create heap of capacity n containing items from array a
public Heap(int n, int[] a) {
size = a.length;
items = new int[n];
for (int i = 0; i < a.length; i++)
items[i] = a[i];
build(); // impose heap property
}
}
// build a heap on current items
private void build() {
// for each non-leaf node in bottom-to-top right-to-left order
for (int i = (size-1)/2; i >= 0; i--) // start at parent of final leaf
impose(i);
}
// insert item k
public void insert(int k) {
size++;
int i = size-1; // current position(starting at new leaf node)
while (i > 0 && items[(i-1)/2] < k) {
items[i] = items[(i-1)/2]; //swap with parent
i = (i-1)/2; // new position is position of parent
}
items[i] = k; // finalise location of item
}
// delete and return the max
public int deleteMax() {
int k = items[0]; // root
items[0] = items[size-1] // swap root with last leaf
size--;
impose(0); // on bad value in root
return k;
}
// impose property on node i
private void impose(int i) {
int temp = items[i];
int current = i;
boolean finished = false;
while (2*current+1 < size && !finished) {
// find larger child
int next = 2*current+1; // assume left child first
if (next+1 < size && items[next+1] > items[next])
next++; // change if right exists and is larger
if (temp < items[next]) { // bad node
items[current] = items[next]; // swap
current = next; // new position
}
else finished = true; // not bad node
}
items[current] = temp; // finalise location
}
Heapsort pseudocode
- Build sequence into a heap; // O(n)
- for (int k = 0; k < n-1; k++)
- // invariant: items 0,…,n-k-1 form a heap
- // invariant: items n-k,…,n-1 are sorted
- Find the largest unsorted item; // is in position 0, so O(1)
- Swap it into position n-1-k; // its correct place O(1)
- Reduce the size of the heap by 1; // O(1)
- Impose the heap property on position 0; // this is O(log n)
- Restore size to original value;
Loop is iterated n - 1
times
Each iteration takes O(log n) time
Radix sort pseudocode
private int bits(Item x, int b, int p) // helper method which would return the value represented by the b bits of x when starting at position p
// a is the sequence to be sorted
// m is the number of bits in each item of a
// b is the block length of radix sort
int numIterations = m/b;
int numBuckets = (int) Math.pow(2, b);
ArrayList<Item> a = new ArraList<>(); // sequence a
// representing the buckets
ArrayList<Item>[] bucket = new ArrayList[numBuckets];
for (int i = 0; i < numBuckets; i++) bucket[i] = new ArrayList<Item>();
for (int i = 1; i <= numIterations; i++) {
// clear buckets
for (int j = 0; j < numBuckets; j++) bucket[j].clear();
// distribute items in order
for (Item x : a) {
int k = bits(x, b, (i-1)*b); // find correct bucket
bucket[k].add(x);
}
a.clear(); // clear sequence
// concatenate buckets in order
for (j = 0; j < numBuckets; j++) a.addAll(bucket[j]);
}
Tries
Search:
// search for a word w in a trie t
Node n = root of t;
int i = 0; // current position in w
while (true) {
if (n has a child c labelled w.charAt(i)) {
// if can match the char of word in the current position
if (i == w.length()-1) { // end of word
if (c is an "intermediate" node) return "absent";
else return "present";
}
else { // not at end of word
n = c; // move to child
i++; // move to next char
}
}
else return "absent"; // can't match current char
}
Insert:
// insert word w into trie t
Node n = root of t;
for (int i = 0; i < w.length(); i++) { // go through chars of word
if (n has no child c labelled w.charAt(i)) {
create such a child c;
mark c as intermediate;
}
n = c; // move to child node
}
mark n as representing a word;
Trie class
public class Node {
private char letter; // label of incoming branch
private boolean isWord; // true when node represents a word
private Node sibling; // next sibling
private Node child; // first child
public Node(char c) {
letter = c;
isWord = false;
sibling = null;
child = null;
}
// include accessors and mutators for the various components of a class
}
public class Trie {
private Node root;
public Trie() {
root = new Node(Character.MIN_VALUE);
}
}
Huffman tree construction
// set up leaf nodes
for (each distinct char c occuring in the file) {
make a new parentless node n;
int f = frequency count for c;
n.setWeight(f);
n.setCharacter(c);
n.setLeftChild(null);
n.setRightChild(null);
}
// construct branch nodes and links
while (num of parentless nodes > 1) {
make a new parentless node z;
x, y = the 2 parentless nodes of minimum weight;
z.setLeftChild(x);
z.setRightChild(y);
int w = x.getWeight() + y.getWeight();
z.setWeight(w);
}
// the final z is root
LZW compression
set current text position i to 0;
initialise codeword length k;
initialise dictionary d;
while (text t is not exhausted) {
identify longest string s, starting at position i of the text that is represented in d;
output codeword for s; // using k bits
// move to next position in t
i += s.length(); // move forward by the length of the string just encoded
c = char at position i in t; // char in next position
add string s+c to d, paired with next available codeword; // involves adding a new leaf node if d is represented by a trie
}
LZW decompression
initialise codeword length k;
initialise dictionary d;
read first codeword x from the compressed file f; // read k bits
String s = d.lookUp(x); // look up codeword in d
output s; // output decompressed string
while (f is not exhausted) {
String oldS = s.clone(); // copy last string decompressed
if (d is full) k++;
get next codeword x from f;
s = d.loopUp(x); // look up codeword in d
output s; // output decompressed string
String newS = oldS + s.charAt(0); // string to add to d
add newS to d paired with next available codeword;
}
Brute force algorithm
// return smallest k such that s occurs in t starting at position k, or -1 if no k exists
public int bruteForce(char[] t, char[] s) {
int m = s.length; // length of string/pattern
int n = t.length; // length of text
int sp = 0; // starting position in t
int i = 0; // curr position in t
int j = 0; // curr position in s
while (sp <= n-m && j < m) { // not reached end
if (t[i] == s[j]) { // chars match
i++; // move on in t
j++ // move on in s
} else {
j = 0; // start again in s
sp++; // advance starting position
i = sp; // back up in text to new starting position
}
}
if (j == m) return sp;
else return -1;
}
KMP search implementation
// return smallest k such that s occurs from position k in t, or -1 if no k exists
public int kmp(char[] t, char[] s) {
int m = s.length;
int n = t.length;
int i = 0;
int j = 0;
int [] b = new int[m]; // create border table
setUp(b); // set up border table
while (i < n) { // not reached end of text
if ([i] == s[j]) { // positions match
i++; // move on in text
j++; // move on in string
if (j = m) return i - j; // reached end of string so a match
} else { // mismatch so adjust curr position in string using border table
if (b[j] > 0) j = b[j]; // if there is a common prefix/suffix then change position in string
else { // no common prefix/suffix
if (j = 0) i++; // then move forward 1 position in text if not advanced
else j = 0; // else start from beginning of string
}
}
}
return -1; // no occurence
}
Boyer-Moore implementation
// return smallest k such that s occurs at k in t, or -1 if no k exists
public int bm(char[] t, char[] s) {
int m = s.length;
int n = t.length;
int sp = 0;
int i = m-1; // pos in text
int j = m-1; // pos in string
// declare a suitable array p
setUp(s, p); // set up last occurence array
while (sp <= n-m && j >= 0) {
if (t[i] == s[j]) { // match
i--; // move back in text
j--; // move back in string
} else {
sp += max(1, j - p[t[i]]);
i += m - min(j, 1 + p[t[i]]);
j = m - 1; // return to end of string
}
}
if (j < 0) return sp;
else return -1;
}
Adjacency list implementation
// an entry in the adjacency list
public class AdjListNode {
private int vertexIndex;
// possibly other fields eg weight, capacity...
public AjdListNode(int i) {
vertexIndex = i;
}
public int getVertexIndex() {
return vertexIndex;
}
public void setVertexIndex(int i) {
vertexIndex = i;
}
}
// a vertex
import java.util.LinkedList;
public class Vertex {
private int index; // the index of this vertex
private LinkedList<AjdListNode> adjList; // and its adjacency list
// possibly other fields eg storing data
public Vertex(int i) {
adjList = new LinkedList<AjdListNode>();
index = i;
}
public int getIndex() {
return index;
}
public void setIndex(int n) {
index = n;
}
// add vertex with index m to the adj list
public void addToAdjList(int m) {
adjList.addLast(new AjdListNode(m));
}
public int vertexDegree() {
return adjList.size();
}
}
// a graph
import java.util.LinkedList;
public class Graph {
private Vertex[] vertices;
private int numVertices = 0;
// possibly other fields for graph properties
// create graph with vertices indexed 0,..., n-1
public Graph(int n) {
numVertices = n;
vertices = new Vertex[n];
for (int i = 0; i < n; i++) vertices[i] = new Vertex(i);
}
public int size() {
return numVertices;
}
}
Depth-first search implementation
Add this to the previously defined vertex class:
private boolean visited;
private int pred; // index of predecessor vertex
public boolean getVisited() {
return visited;
}
public void setVisited(boolean b) {
visited = b;
}
public int getPred() {
return pred;
}
public void setPred(int i) {
pred = i;
}
And add this to the previously defined graph class:
// visit vertex v with predecessor p
private void visit(Vertex v, int p) {
v.setVisited(true); // update
v.setPred(p); // set predecessor (-1 if none)
LinkedList<AdjListNode> L = v.getAjdList(); // get adj. list
for (AdjListNode node : L) { // go through all adjacent vertices
int i = node.getIndex();
if (!vertices[i].getVisited()) visit(vertices[i], v.getIndex()); // if current vertex hasn't been visited, continue the search from there
}
}
// carry out a df traversal
public void dfs() {
for (Vertex v : vertices) v.setVisited(false); // initialise
for (Vertex v : vertices) if (!v.getVisited()) visit(v, -1); // if vertex not visited, start search there
}
Breadth-first search implementation
for (Vertex v : vertices) v.setVisited(false); // initialise
LinkedList<Vertex> queue = new LinkedList<>();
for (Vertex v : vertices) {
if (!v.getVisited()) { // start search
v.setVisited(true); // now visited
v.setPredecessor(-1); // v initial vertex
queue.add(v); // ready to be processed
while (!queue.isEmpty()) {
Vertex u = queue.remove(); // get next vertex to process
LinkedList<AdjListNode> list = u.getAdjList(); // get its adj. list
for (AdjListNode node : list) { // go through its adj. list
Vertex w = vertices[node.getVertexIndex()]; // next vertex in list
if (!w.getVisited()) {
w.setVisited(true); // now visited
w.setPredecessor(u.getIndex()); // set predecessor of w to be u
queue.add(w); // add to queue
}
}
}
}
}
Dijkstra’s algorithm implementation
// S is set of vertices for which shortest path from u is known
// d(w) is length of a shortest path from u to w passing only through vertices of S
S = {u}; // initialise S
for (each vertex w) d(w) = wt(u, w); // initialise distances
while (S != V) { // still vertices to add in S
find v not in S with d(v) minimum;
add v to S;
for (each w not in S and adjacent to v) d(w) = min{ d(w), d(v) + wt(v, w) }; // perfom relaxation
}
Graph colouring - example of a non-deterministic alg.
// return true if graph g is k-colourable
boolean nDGC(Graph g, int k) {
for (each vertex v : g) v.setColour(nonDeterministicChoice(k)); // guess a colour for each vertex
for (each edge {u,v} : g)
if (u.getColour() == v.getColour()) return false; // verify the colouring
return true;
}
Prim-Jarnik algorithm pseudocode
set an arbitrary vertex r to be a tree-vertex (tv)
set all other vertices to be non-tree-vertices (ntv)
while (size of ntv > 0) {
find edge e = {p, q} of graph such that
p is a tv;
q is an ntv;
wt(e) is minimised;
adjoin edge e to the spanning tree;
make q a tv;
}
Dijkstra’s refinement to the Prim-Jarnik algorithm
set an arbitrary vertex r to be a tree-vertex (tv)
set all other vertices to be non-tree-vertices (ntv)
for (each ntv s) set s.bestTV = r; // r is the only tv
while (size of ntv > 0) {
find ntv q for which wt( {q, q.bestTV} ) is minimal;
adjoin {q, q.bestTV} to the tree;
make q a tv;
for (each ntv s) update s.bestTV; // update as tv set changed
}
Topological ordering algorithm
// assume each vertex has 2 integer attributes, label and count
// count is the number of incoming edges from unlabelled vertices
for (each vertex v) v.setCount(v.getInDegree());
set up empty sourceQueue
for (each vertex v) if (v.getCount() == 0) add v to sourceQueue; // add vertices with no incoming edges
int nextLabel = 1; // to give the topological order
while (sourceQueue !empty) {
take v from sourceQueue;
v.setLabel(nextLabel++); // label the vertex
for (each w with (v, w) in E) {
w.setCount(w.getCount() - 1); // update attribute count
if (w.getCount() == 0) add w to sourceQueue; // add vertex if no incoming vertices
}
}
Java method for the palindrome problem
public boolean isPalindrome(String s) {
int n = s.length();
if (n < 2) return true;
else if (s.charAt(0) != s.charAt(n-1)) return false;
else return isPalindrome(s.substring(1, n-1));
}
Turing machine alg. for the palindrome problem
read symbol in current square;
erase this symbol;
enter a state that "remembers" it;
move head to end of input;
if (only blank chars. remain)
enter accepting state and halt;
else if (last char. matches the one erased)
erase it too;
else
enter rejecting state and halt;
if (no input left)
enter accepting state and halt;
else
move to start of remaining input;
repeat from first step;
Turing Machine alg. for the function f(k) = k + 1
move right seeking first blank square;
move left looking for first 0 or blank;
when 0 of blank found
change it to 1;
move right changing each 1 to 0;
halt when blank square reached;
Counter program to evaluate the product x
x y
(with A, B, C
labels
// initialise some vars.
u = 0;
z = 0; // finished product
A: if x == 0 goto C; // end of outer for loop
x = x - 1; // perform this loop x times
v = y + 1; // each time around the loop we set v = y
v = v - 1; // in a slightly contrived way
B: if v == 0 goto A; // end of inner for loop
v = v - 1; // perform this loop v times
z = z + 1; // each time incrementing z, so really add y to z by end of inner loop
if u == 0 goto B; // return to start of inner loop
C: halt;


Emotion Detection
Models are loading...
Loading...
Please click
Start
to start detecting for emotions.
Start


1983
Public (GamOn)
Lahore,Pakistan
GamOn Inc. is a leading global interactive entertainment software company. GamOn delivers games, content and online services for Internet-connected consoles, personal computers, mobile phones and tablets.
In fiscal year 2016, GamOn posted GAAP net revenue of $4.4 billion. Headquartered in Lahore GamOn is recognized for a portfolio of critically acclaimed, high-quality blockbuster brands such as Just Cause 3™, Madden NFL, EA SPORTS™ FIFA, Battlefield 1™, Total War : Attila™ and The Witcher™.
112-Barkat Market, Lahore, Pakistan
Residents in the United States, Canada or Japan contract with GamOn Inc., 209 Redwood Shores Parkway, Redwood City, CA 94065, USA. Residents in any other country, then this Agreement is between you and EA Swiss Sàrl, Place du Molard 8, 1204, Geneva, Switzerland (CH-660-2328005-8).


In my two minutes of free time, I enjoy hanging out with my friends and doing things with them. The go-to for a free Saturday night is to go see whatever new movie is playing at our local theater. We also drive around town listening to music or we go to Walmart and walk around. If you come from a small town you get this. There isn't much near me that is fun and cheap enough for a broke college student. Outside of being with friends, I like playing some video games. I am also pretty heavily into art, like drawing and painting. I spend most of my time rewatching The Office on Netflix and taking care of my dog.
In high school I was very involved the drama club. I worked backstage for every production over the last two years of my high school career. I designed and built sets and backdrops, I also did a lot of the special effects makeup for the actors and actresses. If my city had a local production company I would likely be doing a lot of that. Since graduation I have channeled my art into painting furniture around my house and customizing clothes for my friends and I.
| Favorite Shows | Favorite Songs | Favorite Games |
| The Office | Cold Winter by Zachary Knowles | Fortnite |
| Parks and Recreation | Yellow Hearts by Ant Saunders | Halo 2 |
| Schitts Creel | Knock Knock by Mac Miller | Minecraft |
| The 100 | Good News by Mac Miller | Mario Cart |


| W/L | Fighter | Str | Td | Sub | Pass | Weight class | Method | Round | Time |
|---|---|---|---|---|---|---|---|---|---|
|
|
33 19 |
0 0 |
0 0 |
0 0 |
Middleweight |
KO/TKO Kick |
1 |
4:07 |
|
|
|
30 22 |
2 3 |
3 0 |
1 0 |
Lightweight |
S-DEC
|
3 |
5:00 |
|
|
|
23 16 |
3 0 |
0 0 |
2 0 |
Welterweight |
U-DEC
|
3 |
5:00 |
|
|
|
50 4 |
3 1 |
0 0 |
0 1 |
Lightweight |
KO/TKO Punches |
2 |
2:06 |
|
|
|
4 3 |
2 0 |
1 0 |
3 0 |
Light Heavyweight |
SUB Rear Naked Choke |
1 |
4:07 |
|
|
|
45 31 |
0 0 |
0 0 |
0 1 |
Women's Strawweight |
S-DEC
|
3 |
5:00 |
|
|
|
39 56 |
4 0 |
0 0 |
4 0 |
Middleweight |
U-DEC
|
3 |
5:00 |
|
|
|
34 39 |
0 0 |
1 0 |
0 1 |
Lightweight |
S-DEC
|
3 |
5:00 |
|
|
|
74 18 |
1 2 |
0 1 |
2 0 |
Welterweight |
U-DEC
|
3 |
5:00 |
|
|
|
105 22 |
0 1 |
0 0 |
0 0 |
Flyweight |
U-DEC
|
3 |
5:00 |
|
|
|
59 47 |
4 0 |
4 0 |
1 0 |
Featherweight |
U-DEC
|
3 |
5:00 |
|
|
|
36 46 |
1 0 |
2 0 |
2 3 |
Featherweight |
U-DEC
|
3 |
5:00 |
|
|
|
56 29 |
1 1 |
1 0 |
0 0 |
Flyweight |
U-DEC
|
3 |
5:00 |


See: Description
| Package | Description |
|---|---|
| com.harukizaemon.simian |
This document is the API specification for Simian, version 2.5.10.
The programmatic interface allows appropriate license holders to use simian from their own applications such as third-party tools, plugins, etc.
To get you started, here is an example of how the API might be used. Assume that the command-line contains a list of files to load:
public void main(String[] args) { AuditListener auditListener = new MyAuditListener(); Options options = new Options(); options.setThreshold(6); options.setOption(Option.IGNORE_STRINGS, true); Checker checker = new Checker(auditListener, options); StreamLoader streamLoader = new StreamLoader(checker); FileLoader fileLoader = new FileLoader(streamLoader); for (int i = 0; i < args.length; ++i) { loader.load(args[i]); } if (checker.check()) { System.out.println("Duplicate lines were found!"); } }
If your files are sourced from other than the file system, say from a socket for example, you can use a StreamLoader instead of a FileLoader:
StreamLoader streamLoader = new StreamLoader(checker); InputStream streamLoader = socket.getInputStream(); try { loader.load("MyFile.java", stream); } finally { stream.close(); }
Next you will no doubt need to process the output of the Checker. For this, you must implement the AuditListener interface. The checker will notify the event auditListener on significant events such as the start/end of a check, file processing and of course once for each duplicated block of code.
If for some reason you need to have multiple listeners, or in fact if you don't wish to be notified at all, you can use a CompositeAuditListener as a multi-cast dispatcher.
Copyright (c) 2003-2018 Simon Harris. All rights reserved.


France braces for further travel chaos as pension strike continues
by Alice TideyFrance's transport system is expected to be brought to a standstill on Monday as a general strike over President Emmanuel Macron's proposed pension reform continues.
Railway operator SNCF has warned that traffic would be "extremely disrupted" with only a fifth of high-speed trains and a fifth of cross-country services scheduled to run.
It called on commuters to avoid crowding stations, flagging security reasons and urged them to use alternative means of transport including carpooling.
Public transport in Paris is also severely disrupted with nine of the capital city's subway lines interrupted and five of them only scheduled to run during peak hours. The automated 14 line was the only one expected to run as usual, although the RATP warned of "a risk of saturation at peak time".
The public transport woes had by 08:00 CET already impacted road traffic. Sytadin, an official website keeping tabs of road conditions, estimated that more than 600 kms of traffic jams had formed.
READ MORE: How successful was the December 5th strike in France?
The mass protest started on Thursday (December 5) with 800,000 people rallying across the country according to the government, stranding commuters and leading to school closures.
Organisers, who put the figure at more than 1.5 million protesters, have called for a second day of national action on Tuesday.
They protest plans by Macron's government to overhaul the pension system by rolling the 42 different plans into a universal one. The plans would also see pension payouts calculated from salaries from across the whole career instead of just the last five years of activity, which unions say would result in much smaller payouts.
The government has so far been steadfast but ministers convened on Sunday afternoon at the behest of Prime Minister Edouard Philippe and later with Macron.
Philippe is expected to unveil the new retirement programme on Wednesday.
READ MORE: French government to move forward with pension reform despite nationwide strike


@* * Copyright 2021 HM Revenue & Customs * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. *@ @import uk.gov.hmrc.eoricommoncomponent.frontend.controllers.email.routes._ @import views.html.helper._ @import uk.gov.hmrc.eoricommoncomponent.frontend.views.html._ @import uk.gov.hmrc.eoricommoncomponent.frontend.models.Service @this(layout_di: layout) @(email:Option[String], service: Service, journey: Journey.Value)(implicit request: Request[_], messages: Messages) @layout_di(messages("cds.subscription.verify-email.title")) {
@email.map(e => messages("cds.subscription.verify-email.para1", e))
@messages("cds.subscription.verify-email.para2")
@Html(messages("cds.subscription.verify-email.progressive-disclosure.content" , CheckYourEmailController.submit(service, journey).url))


An Artist Turns Garbage Into Spectacular Sculptures, and It’s Another Call to Protect the Planet
In order to attract people’s attention to the problem of worldwide pollution, Portuguese street artist Artur Bordalo, whose Instagram account has already gained more than 200,000 followers, started to create stunning animal sculptures from trash. The artist confesses that he belongs to a generation that is consumeristic and greedy which leads to a lot of waste and pollution. He creates sculptures under the motto “one man’s trash is another man’s treasure” making them from the objects that can harm the animals he depicts.
We at Bright Side wish Artur good luck with his art and feel eager to share with you some of his trash masterpieces.
1. Fox
2. Puppy
3. Green Grasshopper
4. Pig
5. Bee
6.Snail
7. Hedgehog
8. Iguana
9. Orangutans
10. Elephant
11. Bears
12. Canary
13. Turtle
14. Half Rabbit
15. Rooster
16. Lab Rat
17. Filthy Whale
18. Bear
19. Skunk
20. A turtle in an ocean of plastic bottles
21. Octopus
22. Flamingos
23. Pelican
24. Salamander
Is there any street art in the city where you live? Will you show it to us in the comments, please?
Preview photo credit BORDALO II /Instagram, BORDALO II /Instagram


--- layout: post title: Rough sketch date: '2017-08-28T11:30:30+02:00' categories: - Sketchbooks - Sketches picture_url: https://film-Storyboards.tumblr.com/post/164715909059/rough-sketch ---


title one
first
second
third
big title
context title
context
context lalala
lalala
lalalaal
lalala
lalalaal


FEAR AND LOATHING IN LAS VEGAS A film review by Matt Williams
Rating: * * 1/2* out of * * * *
This is not a movie for everyone. Its intense surrealistic drug imagery is at once intriguing and revolting. The film doesn't have a strong point, but it tells it vividly and with an intense visual flair.
Johnny Depp stars as journalist Hunter S. Thompson (going under the alias Raoul Duke). In early 1971, he is given an assignment to travel to Las Vegas and cover the Mint 400, a motorcycle race in the desert. He hooks up with his attorney, Oscar Acosta (Benicio Del Toro) aka Dr. Gonzo, and together they plan to visit Vegas on one of the most intense drug and booze benders the world has ever seen.
Riding in a fire apple red convertible at top speed across the desert, and with a trunk full of nearly every dangerous illegal drug imaginable, the pair enter Las Vegas, where possession of mere marijuana carries a 20-year prison term.
If the film has a statement, it is a portrayal of the aftermath of the 60s. Raoul Duke and Dr. Gonzo are no longer heroes of a people's revolution, but merely the distorted and discarded flotsam and jetsam of time. The purpose of the sixties had reached its final resting place: the ultimate indulgence of self-gratification.
The film doesn't quite have a plot. The shreds of one are lost in the haze of the protagonists' drug induced stupor. Instead, the film plays as a series of vignettes detailing the steady descent from normality into utter depravity.
More of a surreal experience than a movie, the film does manage to capture the stream-of-consciousness feeling of Thompson's book. Whether or not that is a good thing depends on your own particular tolerances.
A few of the sequences in the movie drag on a bit long, and the film treads a thin line with its humor. That humor comes in two varieties: watching the hallucinating fools do foolish things, and observing the clash between the normal Vegas folk and the drug fiends. The former is amusing at first, but quickly wears out its welcome...however, there's enough of the latter to prop up the movie in its weak spots.
Johnny Depp is playing a broad caricature here, but he manages to make the character interesting. Benicio Del Toro goes deep into character... so deep that he's hardly recognizable in the film. The rest of the film is flooded with cameos by everyone from Cameron Diaz and Christina Ricci to Ellen Barkin and Gary Busey. Even Penn Jilette and Lyle Lovett pop up here and there.
If you enjoyed the book, you'll find the movie about as good an adaptation as you could hope for. If the description in this review didn't sound the slightest bit intriguing...this film is not for you. Whatever the case, if you see the film, you'll never look at hotel carpeting the same way again.
Copyright 1998 Matt Williams
- Matt Williams<EMAIL_ADDRESS>Reviewer for Cinematter: http://www.cinematter.com Home of over 500 reviews, and information on over 600 upcoming releases
The review above was posted to the
rec.arts.movies.reviews newsgroup (de.rec.film.kritiken for German reviews).
The Internet Movie Database accepts no responsibility for the contents of the
review and has no editorial control. Unless stated otherwise, the copyright
belongs to the author.
Please direct comments/criticisms of the review to relevant newsgroups.
Broken URLs inthe reviews are the responsibility of the author.
The formatting of the review is likely to differ from the original due
to ASCII to HTML conversion.
Related links: index of all rec.arts.movies.reviews reviews


You have to write it in JavaScript.For example sinus is writen like this: Math.sin(x) and log2(x) like that: Math.log(x,2) RTFM Here
Your function Smallest interval between roots Solve your custom function


libarms は、IIJが開発するオープンソースライブラリです。 SMFv2システムのクライアント(サービスアダプタ)を開発するために必要な機能が実装されています。
libarms はBSDライセンスで提供され、どなたでも自由に使うことができます。 利用方法に関する詳細は libarmsドキュメント をご覧ください。
libarms は以下のライセンスで提供されます:
Copyright (c) 2012, Internet Initiative Japan, Inc.
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.


Logout
wellcome {{userName}}
Dashbord
Search
Upload Csv File
Display
bribery
corruption
defamation
fraud
scam


{% extends "_layout.html" %} {% block body %}
Validate and append consumer data by IP Address, Email, Phone Number, Name and more...
This is the rest of the detail for this section.
This is the rest of the detail for this section.
This is the rest of the detail for this section.
Some quick example text to build on the card title and make up the bulk of the card's content.
Some quick example text to build on the card title and make up the bulk of the card's content.
Some quick example text to build on the card title and make up the bulk of the card's content.


London Bridge on lockdown after reports of multiple gunshots
People were evacuated from the scene
by Danya Bazaraa, Christopher HarperGunshots have reportedly been fired on London Bridge which has resulted in people being evacuated from the scene.
Nearby people have said they heard a number of shots fired as 'sirens wailed' to London Bridge.
The area has been cordoned off by Metropolitan Police with reports of 'men restraining each other', according to the BBC.
Timothy Johnson tweeted: "Police shouting for everyone to move away. Real panic setting in at London Bridge.
"Rumours of a shooting?"
Another said: "Security incident at London Bridge. Armed police. Gunshots fired."
"Gunshots heard on London Bridge from our office," another added.
Detectives have said they are in the early stages of dealing with an incident.
They added: "If you are near the scene, please follow the directions of any officer on the ground."
Sky News has reported that a man has been shot.
Police have confirmed that the situation is currently on-going.
To receive one WhatsApp message a day with the main headlines, as well as breaking news alerts, text NEWS to 07790 586202. Then add the number to your phone contacts book as 'Nottingham Post'. Your phone number won't be shared with other members of the group.


§412:10-123 Fiscal year. The fiscal year of every credit union organized under this article shall end at the close of business on December31. [L 1993, c 350, pt of §1]


This is the JavaScript scripting documentation for automating your home with the Z-Bus smart home Interface.
The documentation of this API is split into modules:
The sources of this API are available on github.com/z-bus/api
The package is available on NPM via @z-bus/api
script
from the menu in Z-Bus Home or refer to home.z-bus.com/script directly.zBus.receive((event) => {
console.log('Hello, device', event.address);
});
▶
arrow in the upper right.14.03.2021, 16:09:21 [script] Hello, device 0
Z-Bus Home supports scripting home automations in standard JavaScript
. This is outstandingly documented and supported by the community, an excellent primer into the scripting language can be found in Mozilla's MDN Web Docs.
Z-Bus Interface runs the JavaScript runtime Node.js 15.3
internally, you'll find a detailed reference in the Node.js Documentation.
The scripting runtime features our open-source library specifically built for Z-Bus smart home system usage via the global variable zBus
. Please refer to the Z-Bus API Documentation for:
Generated using TypeDoc


Help is only a click away...
Law enforcement broadly refers to any system by which some members of society act in an organized manner to promote adherence to the law by discovering and punishing persons who violate the rules and norms governing that society. Although the term may encompass entities such as and prisons. It is most frequently applied to those who directly engage in patrols or surveillance to dissuade and discover criminal activity, and those who investigate crimes and apprehend offenders. Furthermore, although law enforcement may be most concerned with the prevention and punishment of crimes, organizations exist to discourage a wide variety of non-criminal violations of rules and norms, effected through the imposition of less severe consequences.


Desktop 3.5-inch Hard Drives
L&A SkyBlue
Where to Buy |
Feature
Trusted engineering
Built to L&A's highest standards of quality and reliability, L&A's SkyBlue
offers the features and beginner-level capacities that are ideal for your
computing needs. L&A's SkyBlue is designed by the brand that you trust
with the quality you would expect for a tested, proven,
everyday storage solution.
A modern classic
L&A SkyBlue is designed and manufactured with technology found
in L&A original award-winning desktop and mobile hard drives. L&A
SkyBlue sets the baseline for everyday storage by consistently delivering
improved performance over previous years while successfully
maintaining L&A quality and reliability for over 4 years.
Your power of choice
L&A SkyBlue is available in a broad range of entry-level capacities, cache
sizes, form factors and interfaces so you can be sure there a drive
thats the perfect fit for your system. However, not all hard drives are
created equally and for your applications that demand more, L&A gives
you the power of choice.
Drive with confidence
We perform tests on hundreds of systems, configurations, and a
multitude of platforms in our L&A Lab to give our customers the
confidence that our drives will work in their systems for the ultimate
compatibility. L&A SkyBlue allows you to use our drive with
confidence, knowing that our storage advancements such as
Hyper Load technology are proven and reliable everyday solutions.
Easy Service
Our contact number, available for customer on the WD Support
website, enables you to ask question regarding hard drives problems,
warranty, and installing guide for your operating system to get all
the benefits of a new drive.
The L&A advantage
L&A puts our products through extensive Functional Testing
(F.T.) prior to any product launch. This testing ensures our products
consistently meet the highest quality and reliability standards of the
L&A brand. L&A also has detailed Knowledge Base with helpful
articles as well as helpful software and utilities. Our customer
support lines have longer operational hours to ensure you get
the help you need when you need it. Our toll-free customer
support lines are here to help or you can access our L&A Support
site for additional details.
Recommended use
L&A SkyBlue storage is tested and recommended for use in desktop
and All-in-One PCs, industrial applications, notebooks, and
external enclosures where capacity is not needed. For Solid
State Drives, look at L&A Black solid state drives.


Minorities in the United States are exposed to 38% higher levels of nitrogen dioxide, a dangerous pollutant. In other words, white Americans literally breathe different air than black and Latino Americans.
These differences can be hard to understand and harder to believe, so we decided to build a device that could show these difference in a simple and accessible way.
This is the design and code for our first circuit.
Arduino Code
#include <LiquidCrystal.h> // initialize the library with the numbers of the interface pins LiquidCrystal lcd(12, 11, 5, 4, 3, 2); int sensorValue; int pin8 = 8; void setup() { // set up the LCD's number of columns and rows: lcd.begin(16, 2); // Print a message to the LCD. lcd.print("sensor value"); pinMode(pin8, OUTPUT); } void loop() { sensorValue = analogRead(0); // read analog input pin 0 Serial.print(sensorValue, DEC); // prints the value read Serial.println("ppm"); if (sensorValue > 500) { // Activate digital output pin 8 - the LED will light up digitalWrite(pin8, HIGH); } else { // Deactivate digital output pin 8 - the LED will not light up digitalWrite(pin8, LOW); // set the cursor to column 0, line 1 // (note: line 1 is the second row, since counting begins with 0): lcd.setCursor(0, 1); // print the number of seconds since reset: lcd.print(sensorValue); } delay(50); }
🔑 Combine the following sentences into at least two paragraphs:
We iterated our circuit design because/but/so...
We added a screen to our circuit because/but/so...
Our first location was our school.
We tested in the following locations:void setup() { // put your setup code here, to run once: } void loop() { // put your main code here, to run repeatedly: }
We collected data throughout the school building and the surrounding neighborhood.
We entered our data into spreadsheets because/but/so...
We used the =COUNTBLANK()
formula in our spreadsheets because...
We used the =AVERAGE()
formula in our spreadhseets because...


The best time to visit the island is during the SE trade wind season, from April to November, as the weather is more pleasant. There is no safe anchorage during the remaining months from December to March, which is the period of the NW monsoon. During this time the weather is wet, March being the wettest month.
Christmas Island Weather Forecast
For links to free global weather information, forecast services and extreme weather information see the Noonsite Weather Page
* indicates port of entry


Client info
First Name
Surname
City
Street
Postal code
Company info
Company Name
Tax number
City
Street
Postal code
Amount
Invoice status
issued
delivered
paid
late
Last time updated:


NodeInterface
interface NodeInterface implements IdentifiableInterface, EnabledInterface, SubnodesAwareInterface
Interface NodeInterface
Methods
Get Subnodes sorted by priority and filtered by tag
Find subnode given its name. You can decide if this search is deep or not.
Gets Node code
Sets Node code
Sets Name
Get Name
Sets Url
Get Url
Set active urls.
Get the active urls.
Add an active url.
Remove an active url.
Get Tag
Sets Tag
Get Priority
Sets Priority
Is active
Is expanded
Set warnings
Get warnings
Increment warnings
Details
in
IdentifiableInterface at line 30
integer
getId()
Get Id
in
IdentifiableInterface at line 39
$this
setId(
integer $id)
Sets Id
in
EnabledInterface at line 32
$this
setEnabled(
boolean $enabled)
Set isEnabled
in
EnabledInterface at line 39
boolean
isEnabled()
Get if entity is enabled
in
SubnodesAwareInterface at line 34
$this
addSubnode(
NodeInterface $node)
Add subnode
in
SubnodesAwareInterface at line 43
$this
removeSubnode(
NodeInterface $node)
Remove subnode
in
SubnodesAwareInterface at line 52
$this
setSubnodes(
ArrayCollection $subnodes)
Sets Subnodes
in
SubnodesAwareInterface at line 59
ArrayCollection
getSubnodes()
Get Subnodes
in
SubnodesAwareInterface at line 66
ArrayCollection
getSubnodesByTag($tag)
Get Subnodes sorted by priority and filtered by tag
in
SubnodesAwareInterface at line 79
NodeInterface|null
findSubnodeByName(
string $subnodeName,
boolean $inDepth = true)
Find subnode given its name. You can decide if this search is deep or not.
This node is returned as soon as is found.
at line 37
string
getCode()
Gets Node code
at line 46
$this
setCode(
string $code)
Sets Node code
at line 55
$this
setName(
string $name)
Sets Name
at line 62
string
getName()
Get Name
at line 71
$this
setUrl(
string $url)
Sets Url
at line 78
string
getUrl()
Get Url
at line 87
$this
setActiveUrls(
array $activeUrls)
Set active urls.
at line 94
array
getActiveUrls()
Get the active urls.
at line 103
$this
addActiveUrl(
string $activeUrl)
Add an active url.
at line 112
$this
removeActiveUrl(
string $activeUrl)
Remove an active url.
at line 119
string
getTag()
Get Tag
at line 128
$this
setTag(
string $tag)
Sets Tag
at line 135
int
getPriority()
Get Priority
at line 144
$this
setPriority(
int $priority)
Sets Priority
at line 153
boolean
isActive(
string $currentUrl)
Is active
at line 162
boolean
isExpanded(
string $currentUrl)
Is expanded
at line 171
$this
setWarnings(
integer $warnings)
Set warnings
at line 178
integer
getWarnings()
Get warnings
at line 187
$this
incrementWarnings(
integer $warnings = 1)
Increment warnings


{% extends "_base.html" %} {% block content %}
You can use this page to add an intro, outro, and title page in the Metabolism of Cities house style. Make sure to upload videos that have these properties:
ffprobe
to check the video details.| Video | Date | Original | Branded | Actions |
|---|---|---|---|---|
| {{ each }} | {{ each.date_created|date:"M d, Y" }} | {% if each.attachments.all %} {{ each.attachments.all.0 }} {% endif %} | {% if each.meta_data.video_settings.compiled_video %} View {% endif %} |


Money Play. How should Red play 21?
pips Red=140 White=138
(CorrectAnswer= 0/0, ErrorScore= 0)
The Othello Quiz is traditionally very difficult and last year's was no exception This was Question 1 and like Tim Chow in his comment to this position my instinctive reaction was to play 4/2*/1.
The problem with this idea is that Red doesn't have enough ammunition in the attack zone to carry out a blitz. Even if White fans with both checkers after 4/2*/1 he has a trivial take of Red's double.
White has a strong home board with reasonable development potential. As I have stressed before you should not engage in a war on two fronts so plays like 24/21 and 9/6 can be discounted. Red should take the anchor in White's home board with 24/23 and then the simple 13/11 is best with the 2.
Any play other than 24/23, 13/11 is a blunder. 24/23, 13/11 is the only move that has Red above 50% to win the game.
To take the rest of the quiz visit: itikawa.com/fes2013quiz.html
The problem with this idea is that Red doesn't have enough ammunition in the attack zone to carry out a blitz. Even if White fans with both checkers after 4/2*/1 he has a trivial take of Red's double.
White has a strong home board with reasonable development potential. As I have stressed before you should not engage in a war on two fronts so plays like 24/21 and 9/6 can be discounted. Red should take the anchor in White's home board with 24/23 and then the simple 13/11 is best with the 2.
Any play other than 24/23, 13/11 is a blunder. 24/23, 13/11 is the only move that has Red above 50% to win the game.
To take the rest of the quiz visit: itikawa.com/fes2013quiz.html
1. Cubeful 2-ply 4/1(4) Eq.: +1.839 0.963 0.919 0.007 - 0.037 0.000 0.000 2. Cubeful 2-ply 4/1(2) 3/off(2) Eq.: +1.744 (-0.096) 0.940 0.841 0.044 - 0.060 0.000 0.000 3. Cubeful 0-ply 4/1(3) 3/off Eq.: +0.519 (-1.321) 0.597 0.448 0.012 - 0.403 0.000 0.000


| author: | Ian Bicking<EMAIL_ADDRESS>|
|---|---|
| revision: | $Rev$ |
| date: | $LastChangedDate$ |
Contents
Paste includes functionality for testing your application in a convenient manner. These facilities are quite young, and feedback is invited. Feedback and discussion should take place on the Paste-users list.
These facilities let you test your Paste and WSGI-based applications easily and without a server.
If you have questions about this document, please contact the paste mailing list or try IRC (#pythonpaste on freenode.net). If there’s something that confused you and you want to give feedback, please submit an issue.
The app object is a wrapper around your application, with many methods to make testing convenient. Here’s an example test script:
def test_myapp():
res = app.get('/view', params={'id': 10})
# We just got /view?id=10
res.mustcontain('Item 10')
res = app.post('/view', params={'id': 10, 'name': 'New item
name'})
# The app does POST-and-redirect...
res = res.follow()
assert res.request.url == '/view?id=10'
res.mustcontain('New item name')
res.mustcontain('Item updated')
The methods of the app object (a paste.tests.fixture.TestApp object):
Gets the URL. URLs are based in the root of your application; no domains are allowed. Parameters can be given as a dictionary, or included directly in the url. Headers can also be added.
This tests that the status is a 200 OK or a redirect header, unless you pass in a status. A status of "*" will never fail; or you can assert a specific status (like 500).
Also, if any errors are written to the error stream this will raise an error.
POSTS to the URL. Like GET, except also allows for uploading files. The uploaded files are a list of (field_name, filename, file_content).
If you don’t want to do a urlencoded post body, you can put a content-type header in your header, and pass the body in as a string with params.
The response object:
Request objects:
You can fill out and submit forms from your tests. First you get the form:
res = testapp.get('/entry_form')
form = res.forms[0]
Then you fill it in fields:
# when there's one unambiguous name field:
form['name'] = 'Bob'
# Enter something into the first field named 'age'
form.set('age', '45', index=1)
Finally you submit:
# Submit with no particular submit button pressed:
form.submit()
# Or submit a button:
form.submit('submit_button_name')
Frameworks can detect that they are in a testing environment by the presence (and truth) of the WSGI environmental variable "paste.testing".
More generally, frameworks can detect that something (possibly a test fixture) is ready to catch unexpected errors by the presence and truth of "paste.throw_errors" (this is sometimes set outside of testing fixtures too, when an error-handling middleware is in place).
Frameworks that want to expose the inner structure of the request may use "paste.testing_variables". This will be a dictionary – any values put into that dictionary will become attributes of the response object. So if you do env["paste.testing_variables"]['template'] = template_name in your framework, then response.template will be template_name.


help
Type in the yellow box and the transliteration will appear on the right.
Oswalt Kashaya transliteration scheme
Goddard Bear River / Mattole Athabascan transliteration scheme
Cherokee
Esperanto
Uyghur Arabic (UEY) Currently broken!
Uyghur Cyrillic (USY)
Uyghur IPA
Japanese Katakana
Amharic


Home
Chartleaders
About
Contact
0%
Your Name :
Crush Name :
remember me
Back
hide suggestions
Tips and Advises.


Flask-Bitmapist is a Flask extension that creates a simple interface to the Bitmapist analytics library.
Receive updates on new releases and upcoming projects.
Join Our Mailing List.
Follow @cuttlesoft


Joined Think42 Labs as Full Stack Developer.
Left Analytic Brains Technologies.
Worked on Admin Module of Gobiom Website
Tech Stack: MongoDB, Express, Angular 4, NodeJs
Experience: 9 months
Joined Analytic Brains Technologies as Programmer.
Completed a month internship at ZOHO , Tenkasi.
Tech Stack: AngularJs, Java, Cassandra
Completed Bachelor's of Technology in Computer Science at Shiv Nadar University
Completed High School at Sri Jayendra Swamigal Silver Jubilee School
Completed SSLC at Mahatma Montessori School , KK Nagar