Lab1 - 4 Slides Per Page

Lecture Overview
Programming Techniques
Lab 1
Note on invariants
The Dutch national flag problem
Star proximity
Profiling
Debugging
Invariants
The assert( ) function can be disabled during

compiling so you should never put commands that
are part of the algorithm in the assertion!!!
Programmers can eliminate the assertions without
changing the source code: if the macro NDEBUG is
defined before the inclusion of <assert.h>, or the
source code is compiled with the -DNDEBUG flag the
assert() macro is defined simply as:
#define assert(ignore)((void) 0)
e.g. assert( myPointer = malloc(sizeof*myPointer ); //broken

code
Problem Statement
Assume we have an unordered array with

red and blue elements
How do we separate the red from the blue
elements
Remember red >< blue
The dutch national flag problem
The dutch national flag problem (1st attempt)

Count and reconstruct
#of:
Red:
Blue:

Count and reconstruct
Create a new array with the number of red and

blue elements counted before
#of:
Red: 5
Blue: 5
The dutch national flag problem (2nd attempt)

Compare and swap
Red found!
Swap!
Red found!
Swap!
Red found!
Swap!
Reached end of array. Return.
Optimizations might complicate things
The dutch national flag problem
Method comparison
Method comparison
Without optimizations enabled

70
60
50
40
30
20
10
0
-O3 optimizations
30
25
20
Time (ms)
Which approach renders better results?

What is the complexity of this problem?
In what directions can we exam the problem?
Time (ms)
15
10
5
0
4096
1024
65536
16384
1048576
16777216
262144
4194304
Traverse and Reconstruct
4096
1024
65536
16384
1048576
16777216
262144
4194304
Input Size
Input size
Compare and Swap
Traverse and Reconstruct
Compare and Swap
Same experiment run with optimization disabled (left) and with optimization (-O3
flag) enabled (right). The red blue is represented by 0 and 1, respectively, in an
array of integers.
Object size affects the result

Method Comparison
Method Comparison
-O3 optimization
60
60
50
50
40
40
Time (ms)
Time (ms)
Without any optimization
30
20
10
30
The original dutch flag problem has three colours!!
20
10
0
2048
2048
1024
8192
4096
32768
16384
131072
524288
65536
262144
1024
8192
4096
32768
131072
524288
16384
65536
262144
Input Size
Input Size
Count and Reconstruct
Compare and Swap
The dutch national flag problem (original)
Count and Reconstruct
Compare and Swap
Same experiment run with optimization disabled (left) and with optimization (-O3
flag) enabled (right). The red blue is represented by a struct of 808 bytes.
Problem invariants:
All the cells to the left of red marker are red!
All the cells to the right of blue marker are blue!
Rules of the game
Start transparent marker.

If red element is found, swap the element pointed by the transparent
marker with the one pointed by the red one and increment both
markers.
If a white element is found, increment only the transparent marker.
If a blue element is found, swap the element pointed by the transparent
marker with the one pointed by the blue one and decrement the blue
marker only.
Star proximity
Task: Find all the pairs of
points that are closer than
a given distance d, (d<1 ).
The dutch national flag problem is credited to Dijkstra.

It is the idea behind the 3-way partitioning in quick-sort
Quicksort goes quadratic unless partitioning stops on equal keys.
Star proximity (brute force)
Star proximity (2nd attempt)

Point under examination
Intuitively, we would like
to find all the points within
a radius of d from each
point.
Thus, we could first filter
out all the points that have
|x0-xi|>d, then filter out all
those points with |y 0-yi|>d
and from this considerably
smaller subset calculate
the distance formula.
We could compare the distance

of every pair of points i, j using
the known formula:
d i , j = ( x i x j )2 +( y i y j )2
But, we will end up with a vast
amount of comparisons! Since
we have N dots and we compare
each one of them with the
remaining N-1 dots, we end up
with
N*(N-1)/2
~
O(N 2)
calculations.
This
problem
becomes infeasible for large N.
Vertical band of points with|x0-xi|<=d
Sort points first
An upgrade to the previous idea would be

to sort the points lexicographically
(according to their abscissa and in the case
of a tie according to their ordinate)
point i < point j iff:
xi < xj
or
xi = xj and yi < yj
The problem with this

approach is that we have
to re-calculate the two
bands by examining the
whole search space and
then re-calculate the
circle for every point
Sort points first
Issue 1: We need a range search, not a specific

point
e.g. for point (5.1, 3.2) and radius 0.9, we would

like to get all the points with
2.3 y i 4.1
4.2x i6.0 and
What if no point with abscissa 4.2 exist in the
dataset?
We can modify the search function and return the

last index even in the case of failure
Sort points first
Modify search function to

return either 1 or 2 instead
of -1
4.0
2.1
4.0
5.7
4.3
0.1
4.4
1.6
5.3
3.2
5.5
3.1
5.5
3.3
5.5
9.1
5.5
13.3
7.0
4.0
Sort points first
Search returns this index.

We need to traverse the list
linearly to confirm that this
is the last point with
abscissa equal to 6.0
4.0
2.1
4.0
5.7
4.3
0.1
4.4
5.3
1.6
3.2
6.0
3.1
6.0
3.3
6.0
9.1
6.0
13.3
7.0
4.0
Sort points first
Issue 2: Duplicate numbers in the list !!!
e.g. for point (5.1, 3.2) and radius 0.9, we would

like to get all the points with
2.3 y i4.1
4.2x i6.0 and
Assume that we actually find a point with abscissa
equal to 4.2.
Is it the first within this range i.e. the one with the
least ordinate? We need a linear search to
confirm, so there goes the linearithmic complexity
of our solution...
Star proximity(3rd attempt)

d
Since d<1
We could divide
the big grid into a
linked list of
smaller grids
Each sub-grid
covers an area of
d2
All the points in
one grid will look
only for the points
in adjacent grids
We managed to decrease
the complexity to O(d 2N2)
(Since d<1
d 2N2< N2 )
Star proximity
int main(int argc, char *argv[])
{ int i, j, N = atoi(argv[1]);
d = atof(argv[2]);
G = 1/d;
grid = malloc2d(G+2, G+2);
for (i = 0; i < G+2; i++)
for (j = 0; j < G+2; j++)
grid[i][j] = NULL;
for (i = 0; i < N; i++)
gridinsert(randFloat(), randFloat());
printf("%d edges shorter than %f\n", cnt, d);
return 0;
}
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "Point.h"
typedef struct node* link;
struct node { point p; link next; };
link **grid; int G; float d; int cnt = 0;
gridinsert(float x, float y)
{ int i, j; link s;
int X = x*G +1;
int Y = y*G+1;
link t = malloc(sizeof *t);
t->p.x = x;
t->p.y = y;
for (i = X-1; i <= X+1; i++)
for (j = Y-1; j <= Y+1; j++)
for (s = grid[i][j]; s != NULL; s = s->next)
if (distance(s->p, t->p) < d) cnt++;
t->next = grid[X][Y]; grid[X][Y] = t;
}

Lab1 - 4 Slides Per Page

Uploaded by

Copyright:

Available Formats

Lab1 - 4 Slides Per Page

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lab1 - 4 Slides Per Page

Uploaded by

Copyright:

Available Formats

Lecture Overview

The Dutch national flag problem

The assert( ) function can be disabled during

e.g. assert( myPointer = malloc(sizeof*myPointer ); //broken

Assume we have an unordered array with

The dutch national flag problem

The dutch national flag problem (1st attempt)

The dutch national flag problem (1st attempt)

The dutch national flag problem (1st attempt)

Create a new array with the number of red and

The dutch national flag problem (2nd attempt)

The dutch national flag problem (2nd attempt)

The dutch national flag problem (2nd attempt)

The dutch national flag problem (2nd attempt)

The dutch national flag problem (2nd attempt)

The dutch national flag problem (2nd attempt)

The dutch national flag problem (2nd attempt)

The dutch national flag problem (2nd attempt)

Reached end of array. Return.

Optimizations might complicate things

The dutch national flag problem

Without optimizations enabled

Which approach renders better results?

Traverse and Reconstruct

Compare and Swap

Traverse and Reconstruct

Compare and Swap

Object size affects the result

Without any optimization

The original dutch flag problem has three colours!!

Count and Reconstruct

Compare and Swap

The dutch national flag problem (original)

Count and Reconstruct

Compare and Swap

The dutch national flag problem (original)

Rules of the game

The dutch national flag problem (original)

Start transparent marker.

The dutch national flag problem is credited to Dijkstra.

Star proximity (brute force)

Star proximity (2nd attempt)

We could compare the distance

Vertical band of points with|x0-xi|<=d

Sort points first

An upgrade to the previous idea would be

point i < point j iff:

The problem with this

Sort points first

Issue 1: We need a range search, not a specific

e.g. for point (5.1, 3.2) and radius 0.9, we would

We can modify the search function and return the

Sort points first

Modify search function to

Sort points first

Search returns this index.

Sort points first

Issue 2: Duplicate numbers in the list !!!

e.g. for point (5.1, 3.2) and radius 0.9, we would