Net Study Material

UNIX System Programming
Processes
Objectives
look at how to program UNIX processes
fork( ), exec( ), wait( )
1. What is a Process?
A process is an executing program.
A process:
$ cat file1 file2 &
Two processes:
$ ls | wc - l
Each user can run many processes at once

(e.g. using &)
A More Precise Definition
A process is the context (the information/data) maintained for

an executing program.
Intuitively, a process is the abstraction of a physical processor.

Exists because it is difficult for the OS to otherwise coordinate many
concurrent activities, such as incoming network data, multiple users,
etc.
IMPORTANT: A process is sequential

What makes up a Process?
program code
machine registers
global data
stack
open files (file descriptors)
an environment (environment variables;
credentials for security)
Some of the Context Information
Process ID (pid) unique integer
Parent process ID (ppid)
Real User ID ID of user/process which
started this process
Effective User ID ID of user who wrote
the process program
Current directory
File descriptor table
Environment VAR=VALUE pairs
continued
Pointer to program code
Pointer to data Memory for global vars
Pointer to stack Memory for local vars
Pointer to heap Dynamically allocated
Execution priority
Signal information
Important System Processes
init Mother of all processes. init is started at
boot time and is responsible for starting other
processes.
init uses file inittab & directories: /etc/rc?.d
getty login process that manages login
sessions.
Unix Start Up Processes Diagram
OS kernel
Process 0
(sched)
Process 1
(init)
getty getty getty
login login
csh bash
Pid and Parentage
A process ID or pid is a positive integer that uniquely
identifies a running process, and is stored in a variable of
type pid_t.
You can get the process pid or parents pid

#include <sys/types>
main()
{
pid_t pid, ppid;
printf( "My PID is:%d\n\n",(pid = getpid()) );
printf( "Par PID is:%d\n\n",(ppid = getppid()) );
}
2. fork()
#include <sys/types.h>
#include <unistd.h>
pid_t fork( void );
Creates a child process by making a copy of

the parent process --- an exact duplicate.
Implicitly specifies code, registers, stack, data, files
Both the child and the parent continue

running.
fork() as a diagram
Parent
pid = fork() Child
Returns a new PID:

e.g. pid == 5 pid == 0
Shared
Program
Data
Data
Copied
Process IDs (pids revisited)
pid = fork();
In the child: pid == 0;

In the parent: pid == the process ID of the
child.
A program almost always uses this pid

difference to do different things in the parent
and child.
fork() Example (parchld.c)
#include <stdio.h>
#include <unistd.h>
int main()
{
pid_t pid; /* could be int */
int i;
pid = fork();
if( pid > 0 )
{
/* parent */
for( i=0; i < 1000; i++ )
printf(\t\t\tPARENT %d\n, i);
}
else
{
/* child */
for( i=0; I < 1000; i++ )
printf( CHILD %d\n, i );
}
return 0;
}
Possible Output
CHILD 0
CHILD 1
CHILD 2
PARENT 0
PARENT 1
PARENT 2
PARENT 3
CHILD 3
CHILD 4
PARENT 4
:
Things to Note
i is copied between parent and child.
The switching between the parent and child

depends on many factors:
machine load, system process scheduling
I/O buffering effects amount of output shown.
Output interleaving is nondeterministic

cannot determine output by looking at code
3. exec()
Family of functions for replacing processs
program with the one inside the exec() call.
e.g.
#include <unistd.h>
int execlp(char *file, char *arg0,
char *arg1, ..., (char *)0);
execlp(sort, sort, -n,

foobar, (char *)0);
Same as "sort -n foobar"

tinymenu.c
#include <stdio.h>
#include <unistd.h>
void main()
{ char *cmd[] = {who, ls, date};
int i;
printf(0=who 1=ls 2=date : );
scanf(%d, &i);
execlp( cmd[i], cmd[i], (char *)0 );

printf( execlp failed\n );
}
Execution
tinymenu
cmd[i]
execlp()
printf()
not executed
unless there
is a problem
with execlp()
exec(..) Family
There are 6 versions of the exec function,

and they all do about the same thing: they
replace the current program with the text of
the new program. Main difference is how
parameters are passed.
int execl( const char *path, const char *arg, ... );
int execlp( const char *file, const char *arg, ... );
int execle( const char *path, const char *arg
, ..., char *const envp[] );
int execv( const char *path, char *const argv[] );
int execvp( const char *file, char *const argv[] );
int execve( const char *filename, char *const argv [],
char *const envp[] );
exec(..) Family
execl() execle() execlp()
execv() execvp()
execve()
fork() and execv()
execv(new_program, argv[ ])
Initial process
Fork
fork() returns pid=0 and runs as a
Returns a cloned parent until execv is called
new PID
Original New
process new_Program
Copy of
Continues (replacement)
Parent
execv(new_program)
4. wait()
#include <sys/wait.h>
pid_t wait(int *statloc);
Suspends calling process until child has

finished. Returns the process ID of the
terminated child if ok, -1 on error.
statloc can be (int *)0 or a variable which

will be bound to status info. about the child.
wait() Actions
A process that calls wait() can:
suspend (block) if all of its children are still
running, or
return immediately with the termination

status of a child, or
return immediately with an error if there

are no child processes.
menushell.c
#include <stdio.h>
#include <unistd.h>
void main()
{
char *cmd[] = {who, ls, date};
int i;
while( 1 )
{
printf( 0=who 1=ls 2=date : );
scanf( %d, &i );
:
continued
if(fork() == 0)
{ /* child */
execlp( cmd[i], cmd[i], (char *)0 );
printf( execlp failed\n );
exit(1);
}
else
{ /* parent */
wait( (int *)0 );
printf( child finished\n );
}
} /* while */
} /* main */
Execution
menushell
fork() child
cmd[i]
wait() execlp()
Macros for wait (1)
WIFEXITED(status)
Returns true if the child exited normally.
WEXITSTATUS(status)
Evaluates to the least significant eight bits of the
return code of the child which terminated, which
may have been set as the argument to a call to
exit( ) or as the argument for a return.
This macro can only be evaluated if WIFEXITED
returned non-zero.
Macros for wait (2)
WIFSIGNALED(status)
Returns true if the child process exited because of
a signal which was not caught.
WTERMSIG(status)
Returns the signal number that caused the child
process to terminate.
This macro can only be evaluated if WIFSIGNALED
returned non-zero.
waitpid()
pid_t waitpid( pid_t pid, int *status, int opts )
waitpid - can wait for a particular child

pid < -1
Wait for any child process whose process group ID is equal to the
absolute value of pid.
pid == -1
Wait for any child process.
Same behavior which wait( ) exhibits.
pid == 0
Wait for any child process whose process group ID is equal to that
of the calling process.
pid > 0
Wait for the child whose process ID is equal to
the value of pid.
options
Zero or more of the following constants can be ORed.
WNOHANG
Return immediately if no child has exited.
WUNTRACED
Also return for children which are stopped, and whose
status has not been reported (because of signal).
Return value
The process ID of the child which exited.
-1 on error; 0 if WNOHANG was used and no child was
available.
Macros for waitpid
WIFSTOPPED(status)
Returns true if the child process which caused the
return is currently stopped.
This is only possible if the call was done using
WUNTRACED.
WSTOPSIG(status)
Returns the signal number which caused the child
to stop.
This macro can only be evaluated if WIFSTOPPED
returned non-zero.
Example: waitpid
#include <stdio.h>
int main(void)
{
pid_t pid;
int status;
if( (pid = fork() ) == 0 )

{ /* child */
printf(I am a child with pid = %d\n,
getpid());
sleep(60);
printf(child terminates\n);
exit(0);
}
else
{ /* parent */
while (1)
{
waitpid( pid, &status, WUNTRACED );
if( WIFSTOPPED(status) )
{
printf(child stopped, signal(%d)\n,
WSTOPSIG(status));
continue;
}
else if( WIFEXITED(status) )
printf(normal termination with
status(%d)\n,
WEXITSTATUS(status));
else if (WIFSIGNALED(status))
printf(abnormal termination,
signal(%d)\n,
WTERMSIG(status));
exit(0);
} /* while */
} /* parent */
} /* main */
5. Process Data
Since a child process is a copy of the

parent, it has copies of the parents data.
A change to a variable in the child will

not change that variable in the parent.
Example (globex.c)
#include <stdio.h>
#include <unistd.h>
int globvar = 6;
char buf[] = stdout write\n;
int main(void)
{
int w = 88;
pid_t pid;
continued
write( 1, buf, sizeof(buf)-1 );
printf( Before fork()\n );
if( (pid = fork()) == 0 )

{ /* child */
globvar++;
w++;
}
else if( pid > 0 ) /* parent */
sleep(2);
else
perror( fork error );
printf( pid = %d, globvar = %d, w = %d\n,

getpid(), globvar, w );
return 0;
} /* end main */
$ globex Output
stdout write /* write not buffered */
Before fork()
pid = 430, globvar = 7, w = 89
/*child chg*/
pid = 429, globvar = 6, w = 88
/* parent no chg */
$ globex > temp.out

$ cat temp.out
stdout write
Before fork()
pid = 430, globvar = 7, w = 89
Before fork() /* fully buffered */
pid = 429, globvar = 6, w = 88
6. Process File Descriptors
A child and parent have copies of the file

descriptors, but the R-W pointer is
maintained by the system:
the R-W pointer is shared
This means that a read() or write() in

one process will affect the other process
since the R-W pointer is changed.
Example: File used across
processes (shfile.c)
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
void printpos(char *msg, int fd);
void fatal(char *msg);
int main(void)
{ int fd; /* file descriptor */
pid_t pid;
char buf[10]; /* for file data */
:
continued
if ((fd=open(data-file, O_RDONLY)) < 0)
perror(open);
read(fd, buf, 10); /* move R-W ptr */
printpos( Before fork, fd );
if( (pid = fork()) == 0 )

{ /* child */
printpos( Child before read, fd );
read( fd, buf, 10 );
printpos( Child after read, fd );
}
:
continued
else if( pid > 0 )
{ /* parent */
wait((int *)0);
printpos( Parent after wait, fd );
}
else
perror( fork );
}
continued
void printpos( char *msg, int fd )
/* Print position in file */
{
long int pos;
if( (pos = lseek( fd, 0L, SEEK_CUR) ) < 0L )

perror(lseek);
printf( %s: %ld\n, msg, pos );

}
Output
$ shfile
Before fork: 10
Child before read: 10
Child after read: 20
Parent after wait: 20
what's happened?
8. Special Exit Cases
Two special cases:
1) A child exits when its parent is not currently

executing wait()
the child becomes a zombie
status data about the child is stored until the
parent does a wait()
continued
2) A parent exits when 1 or more
children are still running
children are adopted by the systems
initialization process (/etc/init)
it can then monitor/kill them
9. I/O redirection
The trick: you can change where the standard
I/O streams are going/coming from after the
fork but before the exec
Redirection of standard output
Example implement shell: ls > x.ls
program:
Open a new file x.lis
Redirect standard output to x.lis using dup command
everything sent to standard output ends in x.lis
execute ls in the process
dup2(int fin, int fout) - copies fin to fout in the file table
File table
dup2(3,1) stdin
stdin
0
0
stdout 1
1
stderr 2
2 x.lis
x.lis 3
3
4
4
Example - implement ls > x.lis
#include <unistd.h>
int main ()
{
int fileId;
fileId = creat( "x.lis",0640 );
if( fileId < 0 )
{
printf( stderr, "error creating x.lis\n );
exit (1);
}
dup2( fileId, stdout ); /* copy fileID to stdout */
close( fileId );
execl( "/bin/ls", "ls", 0 );
}
10. User and Group ID
Group ID
Real, effective
User ID
Real user ID
Identifies the user who is responsible for the running process.
Effective user ID
Used to assign ownership of newly created files, to check file
access permissions, and to check permission to send signals to
processes.
To change euid: executes a setuid-program that has the set-uid bit
set or invokes the setuid( ) system call.
The setuid(uid) system call: if euid is not superuser, uid must be
the real uid or the saved uid (the kernel also resets euid to uid).
Real and effective uid: inherit (fork), maintain (exec).
Read IDs
pid_t getuid(void);
Returns the real user ID of the current process
pid_t geteuid(void);
Returns the effective user ID of the current process
gid_t getgid(void);
Returns the real group ID of the current process
gid_t getegid(void);
Returns the effective group ID of the current process
Change UID and GID (1)
#include <unistd.h>
int setuid( uid_t uid )
Int setgid( gid_t gid )
Sets the effective user ID of the current process.

Superuser process resets the real effective user IDs to uid.
Non-superuser process can set effective user ID to uid, only when

uid equals real user ID or the saved set-user ID (set by executing a
setuid-program in exec).
In any other cases, setuid returns error.

exec setuid(uid)
ID
suid bit off suid bit on superuser other users
real-uid unchanged unchanged uid unchanged

effective-uid unchanged set from user uid uid
ID of program
file
saved set-uid copied from copied from uid unchanged
euid euid
#include <unistd.h>
int setreuid( uid_t ruid, uid_t euid )
Sets real and effective user IDs of the current process.

Un-privileged users may change the real user ID to the
effective user ID and vice-versa.
It is also possible to set the effective user ID from the saved
user ID.
Supplying a value of -1 for either the real or effective user ID
forces the system to leave that ID unchanged.
If the real user ID is changed or the effective user ID is set to
a value not equal to the previous real user ID, the saved user
ID will be set to the new effective user ID.
int seteuid(uid_t euid);
seteuid(euid) is functionally equivalent to setreuid(-1, euid).
Setuid-root program wishing to temporarily drop root
privileges, assume the identity of a non-root user, and
then regain root privileges afterwards cannot use setuid,
because setuid issued by the superuser changes all
three IDs. One can accomplish this with seteuid.
int setregid(gid_t rgid, gid_t egid);
int setegid(gid_t egid);
11. Environment
extern char **environ;
int main( int argc, char *argv[ ], char *envp[ ] )
environment environment environment
pointer list strings
environ: HOME=/home/stevens\0
PATH=:/bin:/usr/bin\0
SHELL=/bin/sh\0
USER=stevens\0
LOGNAME=stevens\0
NULL
Example: environ
#include <stdio.h>
void main( int argc, char *argv[], char *envp[] )

{
int i;
extern char **environ;
printf( from argument envp\n );
for( i = 0; envp[i]; i++ )

puts( envp[i] );
printf(\nFrom global variable environ\n);
for( i = 0; environ[i]; i++ )

puts(environ[i]);
}
getenv
#include <stdlib.h>
char *getenv(const char *name);
Searches the environment list for a string that
matches the string pointed to by name.
Returns a pointer to the value in the environment,
or NULL if there is no match.
putenv
#include <stdlib.h>
int putenv(const char *string);
Adds or changes the value of environment
variables.
The argument string is of the form name=value.
If name does not already exist in the
environment, then string is added to the
environment.
If name does exist, then the value of name in
the environment is changed to value.
Returns zero on success, or -1 if an error occurs.
Example : getenv, putenv
#include <stdio.h>
#include <stdlib.h>
void main(void)
{
printf(Home directory is %s\n, getenv(HOME));
putenv(HOME=/);
printf(New home directory is %s\n, getenv(HOME));

}
Announcements
PS3 Due Thursday
PS4 Available today, due 4/17.
Quiz 2 4/24.
Information on Stereo
Forsyth and Ponce Chapter 11
For DP algorithm in lecture and problem set see: ``A
Maximum Likelihood Stereo Algorithm, by Cox,
Hingorani, Rao, and Maggs, from the journal
Computer Vision and Image Understanding, 63, 3,
pp. 542-567.
On Reserve in CS Library 3rd Floor AV Williams.
Many slides taken from Octavia Camps and Steve
Seitz
Main Points
Stereo allows depth by triangulation
Two parts:
Finding corresponding points.
Computing depth (easy part).
Constraints:
Geometry, epipolar constraint.
Photometric: Brightness constancy, only partly true.
Ordering: only partly true.
Smoothness of objects: only partly true.
Main Points (continued)
Algorithms:
What you compare: points, regions, features.
How you optimize.
Local greedy matches.
1D search.
2D search.
Why Stereo Vision?
2D images project 3D points into 2D:
P
P=Q
3D Points on the same viewing line have the

same 2D image:
2D imaging results in depth information loss
(Camps)
Stereo
Assumes (two) cameras.
Known positions.
Recover depth.
Recovering Depth Information:
Q
P1 P2=Q2
Q1
O2
O1
Depth can be recovered with two images and triangulation.
(Camps)
So Stereo has two steps
Finding matching points in the images
Then using them to compute depth.
Epipolar Constraint
Most powerful correspondence constraint.
Simplifies discussion of depth recovery.
Stereo correspondence
Determine Pixel Correspondence

Pairs of points that correspond to same scene
point
epipolar line epipolar line

epipolar plane
Epipolar Constraint
Reduces correspondence problem to 1D
search along conjugate epipolar lines
(Seitz)
Simplest Case
Image planes of cameras are parallel.
Focal points are at same height.
Focal lengths same.
Then, epipolar lines are horizontal scan lines.
blackboard
We can always achieve this
geometry with image
rectification
Image Reprojection
reproject image planes onto common
plane parallel to line between optical
centers
Notice, only focal point of camera really matters
(Seitz)
Lets discuss reconstruction with this geometry before
correspondence, because its much easier. blackboard
P
T x x T T
Z f
r l
Z f Z x x
Z
l r
xl xr
Disparity: d x x l r
f pl pr
Ol Or
T
Then given Z, we can compute X and Y.
T is the stereo baseline

d measures the difference in retinal position between corresponding points
(Camps)
Correspondence: What should we
match?
Objects?
Edges?
Pixels?
Collections of pixels?
Julesz: had huge impact because it showed that recognition not needed for
stereo.
Correspondence: Epipolar constraint.
Correspondence: Photometric
constraint
Same world point has same intensity in both
images.
Lambertian fronto-parallel
Issues:
Noise
Specularity
Foreshortening
Using these constraints we can use
matching for stereo
For each epipolar line

For each pixel in the left image
compare with every pixel on same epipolar line in right image
pick pixel with minimum match cost
This will never work, so:
Improvement: match windows

(Seitz)
?
=
Comparing Windows:
f g
Most
popular
For each window, match to closest window on epipolar line in other image.
(Camps)
Window size
W=3 W = 20
Effect of window size

Better results with adaptive window
T. Kanade and M. Okutomi, A Stereo Matching
Algorithm with an Adaptive Window: Theory and
Experiment,, Proc. International Conference on
Robotics and Automation, 1991.
D. Scharstein and R. Szeliski. Stereo matching with
nonlinear diffusion. International Journal of
Computer Vision, 28(2):155-174, July 1998
(Seitz)
Stereo results
Data from University of Tsukuba
Scene Ground truth
(Seitz)
Results with window correlation
Window-based matching Ground truth

(best window size)
(Seitz)
Results with better method
State of the art method Ground truth

Boykov et al., Fast Approximate Energy Minimization via Graph Cuts,
International Conference on Computer Vision, September 1999.
(Seitz)
Ordering constraint
Usually, order of points in two images is same.
blackboard
This enables dynamic programming.
If we match pixel i in image 1 to pixel j in
image 2, no matches that follow will affect
which are the best preceding matches.
Example with pixels (a la Cox et al.).
How well does this work? See problem set.
Other constraints
Smoothness: disparity usually doesnt change
too quickly.
Unfortunately, this makes the problem 2D again.
Solved with a host of graph algorithms, Markov
Random Fields, Belief Propagation, .
Occlusion and disparity are connected.
Summary
First, we understand constraints that make the
problem solvable.
Some are hard, like epipolar constraint.
Ordering isnt a hard constraint, but most useful when treated like
one.
Some are soft, like pixel intensities are similar, disparities
usually change slowly.
Then we find optimization method.
Which ones we can use depend on which constraints we
pick.
Topic: Trees and Graphs
Graphs (roadmap)
TREES
Static Dynamic
Spatial Game Priority Queues

Search Trees Graphs
Trees Trees and Heaps
(Computer Graphics)
Binary
Search 2-3 Trees Huffman Tree Other ()
Trees
Self-Balancing
AVL Trees Red Black Trees

TREES
Static Dynamic
Spatial Game Priority Queues

Search Trees Graphs
Trees Trees and Heaps
(Computer Graphics)
Binary
Search 2-3 Trees Huffman Tree Other ()
Trees
Self-Balancing
AVL Trees Red Black Trees

Graphs
Definitions, terminology, applications
Data Structures
Traversals
Minimum Spanning Tree
Shortest Path
Reachability, Transitive closure, Directed
Acyclic Graphs
Graphs
Data Structures
Traversals
Shortest Path
Acyclic Graphs
Graphs
Data Structures
Traversals
Shortest Path
Acyclic Graphs
0 1 2 3 4
0 0 1 0 1 0
1 1 0 1 1 0
2 0 1 0 1 1
3 1 1 1 0 0
4 0 0 1 0 0
0 1 3
1 0 2 3
2 1 3 4
3 0 1 2
4 2
Graphs
Data Structures
Traversals
Shortest Path
Acyclic Graphs
Graphs
Data Structures
Traversals
Shortest Path
Acyclic Graphs
Graphs
Data Structures
Traversals
Shortest Path
Acyclic Graphs
41 0
0
29
1
29
5 1
5 51
45 21 32 4
38
4 2 3
36 32
3 2
50
Graphs
Data Structures
Traversals
Shortest Path
Acyclic Graphs
Welcome to
CS 620
Theory of Computation
Fall 2009
Instructor: Marc Pomplun
September 8, 2009 109
Lecture 1: Introduction and Preliminaries
Instructor Marc Pomplun
Office: S-3-171
Lab: S-3-135
Office Hours: Tuesdays 17:30 - 19:00
Thursdays 14:30 - 16:00
Phone: 287-6443 (office)
287-6485 (lab)
E-Mail: marc@cs.umb.edu
Homepage: www.cs.umb.edu/~marc/cs620/
Modeling of Brain Functions
layer l +1 unit and connection
in the interpretive network
unit and connection
in the gating network
unit and connection

in the top-down bias network
layer l
layer l -1
What is so interesting about the
Theory of Computation?
Theory of Computation is the most fundamental subject
in computer science.
What you learn in this course applies to all computers
and all programming languages that will ever exist.
You will understand the capabilities of algorithms in
general.
For example, you will learn about problems that cannot
be solved algorithmically.
Preliminaries
Sets and n-tuples

Functions
Alphabets and Strings
Predicates
Quantifiers
Proof by Contradiction
Mathematical Induction
Set Theory
Set: Collection of objects (elements)

aA a is an element of A
a is a member of A
aA a is not an element of A
A = {a1, a2, , an} A contains
Order of elements is meaningless
It does not matter how often the same element is
listed.
Cartesian Product
The ordered n-tuple (a1, a2, a3, , an) is an ordered
collection of objects.
Two ordered n-tuples (a1, a2, a3, , an) and
(b1, b2, b3, , bn) are equal if and only if they contain
exactly the same elements in the same order, i.e. ai = bi
for 1 i n.
The Cartesian product of two sets is defined as:

AB = {(a, b) | aA bB}
Example: A = {x, y}, B = {a, b, c}
AB = {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)}
Cartesian Product
Note that:
A =
A =
For non-empty sets A and B: AB AB BA
|AB| = |A||B|
The Cartesian product of two or more sets is defined

as:
A1A2An = {(a1, a2, , an) | aiAi for 1 i n}
Set Operations
Union: AB = {x | xA xB}
Example: A = {a, b}, B = {b, c, d}

AB = {a, b, c, d}
Intersection: AB = {x | xA xB}
Example: A = {a, b}, B = {b, c, d}

AB = {b}
Set Operations
Two sets are called disjoint if their intersection is

empty, that is, they share no elements:
AB =
The difference between two sets A and B contains

exactly those elements of A that are not in B:
A-B = {x | xA xB}
Example: A = {a, b}, B = {b, c, d}, A-B = {a}
Set Operations
The complement of a set A contains exactly those
elements under consideration that are not in A:
-A = U-A
Example: U = N, B = {250, 251, 252, }

-B = {0, 1, 2, , 248, 249}
Functions
A function f from a set A to a set B is an assignment of
exactly one element of B to each element of A.
We write
f(a) = b
if b is the unique element of B assigned by the function f
to the element a of A.
If f is a function from A to B, we write
f: AB
(note: Here, has nothing to do with if then)
Functions
If f:AB, we say that A is the domain of f and B is the
codomain of f.
If f(a) = b, we say that b is the image of a and a is the pre-

image of b.
The range of f:AB is the set of all images of elements of

A.
We say that f:AB maps A to B.
An alphabet is a finite, nonempty set A of objects called
symbols.
A word (string) on A is an n-tuple of symbols of A.
Instead of using the notation (a1, a2, , an) we can just
write a1a2an.
The set of all words on A is written A*.
Any subset of A* is called a language on A.
Concatenation of strings:
Let string u = monkey, v = business
uv = monkeybusiness
vu = businessmonkey
Propositional Functions
Propositional function (open sentence):
statement involving one or more variables,
e.g.: x-3 > 5.
Let us call this propositional function P(x), where P is
the predicate and x is the variable.
What is the truth value of P(2) ? false
What is the truth value of P(8) ? false
What is the truth value of P(9) ? true
Propositional Functions
Let us consider the propositional function
Q(x, y, z) defined as:
x + y = z.
Here, Q is the predicate and x, y, and z are the
variables.
What is the truth value of Q(2, 3, 5) ? true
What is the truth value of Q(0, 1, 2) ? false
What is the truth value of Q(9, -9, 0) ? true
Universal Quantification
Let P(x) be a propositional function.
Universally quantified sentence:

For all x in the universe of discourse P(x) is true.
Using the universal quantifier :

x P(x) for all x P(x) or for every x P(x)
(Note: x P(x) is either true or false, so it is a

proposition, not a propositional function.)
Universal Quantification
Example:
S(x): x is a UMB student.
G(x): x is a genius.
What does x (S(x) G(x)) mean ?
If x is a UMB student, then x is a genius.

or
All UMB students are geniuses.
Existential Quantification
Existentially quantified sentence:
There exists an x in the universe of discourse for which
P(x) is true.
Using the existential quantifier :

x P(x) There is an x such that P(x).
There is at least one x such that P(x).
(Note: x P(x) is either true or false, so it is a

proposition, but no propositional function.)
Existential Quantification
Example:
P(x): x is a UMB professor.
G(x): x is a genius.
What does x (P(x) G(x)) mean ?
There is an x such that x is a UMB professor and x is a

genius.
or
At least one UMB professor is a genius.
Disproof by Counterexample
A counterexample to x P(x) is an object c so that P(c)
is false.
Statements such as x (P(x) Q(x)) can be disproved

by simply providing a counterexample.
Statement: All birds can fly.

Disproved by counterexample: Penguin.
Induction
The principle of mathematical induction is a useful
tool for proving that a certain predicate is true for all
natural numbers.
It cannot be used to discover theorems, but only to

prove them.
Induction
If we have a propositional function P(n), and we want
to prove that P(n) is true for any natural number n, we
do the following:
Show that P(0) is true.

(basis step)
Show that if P(n) then P(n + 1) for any nN.
(inductive step)
Then P(n) must be true for any nN.
(conclusion)
Induction
Example (Gauss):
1 + 2 + + n = n (n + 1)/2
1. Show that P(0) is true.

(basis step)
For n = 0 we get 0 = 0. True.
Induction
2. Show that if P(n) then P(n + 1) for any nN.
(inductive step)
1+2++n = n (n + 1)/2
1 + 2 + + n + (n + 1) = n (n + 1)/2 + (n + 1)
= (n + 1) (n/2 + 1)
= (n + 1) (n + 2)/2
= (n + 1) ((n + 1) + 1)/2
Induction
3. Then P(n) must be true for any nN. (conclusion)
1 + 2 + + n = n (n + 1)/2 is true for all nN.
End of proof.
End of first lecture!
Topic 11
Sorting and Searching
"There's nothing in your head the
sorting hat can't see. So try me on
and I will tell you where you ought
to be."
-The Sorting Hat, Harry Potter and
the Sorcerer's Stone
CS 307 Fundamentals of Computer

136
Science Sorting and Searching
Sorting and Searching
Fundamental problems in computer science
and programming
Sorting done to make searching easier
Multiple different algorithms to solve the
same problem
How do we know which algorithm is "better"?
Look at searching first
Examples will use arrays of ints to illustrate
algorithms
137
Searching
Given a list of data find the location of a
particular value or report that value is not
present
linear search
intuitive approach
start at first item
is it the one I am looking for?
if not go to next item
repeat until found or all items checked
If items not sorted or unsortable this
approach is necessary
138
/* pre: list != null Linear Search
post: return the index of the first occurrence
of target in list or -1 if target not present in
list
*/
public int linearSearch(int[] list, int target) {
for(int i = 0; i < list.length; i++)
if( list[i] == target )
return i;
return -1;
}

139
/* Linear Search, Generic
pre: list != null, target != null
post: return the index of the first occurrence
of target in list or -1 if target not present in
list
*/
public int linearSearch(Object[] list, Object target) {
if( list[i] != null && list[i].equals(target) )
return i;
return -1;
}
T(N)? Big O? Best case, worst case, average case?

140
Attendance Question 1
What is the average case Big O of linear search
in an array with N items, if an item is present?
A. O(N)
B. O(N2)
C. O(1)
D. O(logN)
E. O(NlogN)

141
If itemsSearching inwe
are sorted then a Sorted
can divideList
and conquer
dividing your work in half with each step
generally a good thing
The Binary Search on List in Ascending order
Start at middle of list
is that the item?
If not is it less than or greater than the item?
less than, move to second half of list
greater than, move to first half of list
repeat until found or sub list size = 0

142
Binary Search
list
low item middle item high item

Is middle item what we are looking for? If not is it
more or less than the target item? (Assume lower)
list
low middle high

item item item
and so forth

143
Binary Search in Action
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
public static int bsearch(int[] list, int target)
{ int result = -1;
int low = 0;
int high = list.length - 1;
int mid;
while( result == -1 && low <= high )
{ mid = low + ((high - low) / 2);
if( list[mid] == target )
result = mid;
else if( list[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return result;
}
// mid = ( low + high ) / 2; // may overflow!!!
// or mid = (low + high) >>> 1; using bitwise op
144
Trace When Key == 3
Trace When Key == 30
Variables of Interest?

145
What is the worst case Big O of binary search in an array with N items, if an
item is present?
A. O(N)
B. O(N2)
C. O(1)
D. O(logN)
E. O(NlogN)

146
Generic Binary Search
public static int bsearch(Comparable[] list, Comparable target)
{ int result = -1;
int low = 0;
int high = list.length - 1;
int mid;
while( result == -1 && low <= high )
{ mid = low + ((high - low) / 2);
if( target.equals(list[mid]) )
result = mid;
else if(target.compareTo(list[mid]) > 0)
low = mid + 1;
else
high = mid - 1;
}
return result;
}

147
Recursive Binary Search
public static int bsearch(int[] list, int target){
return bsearch(list, target, 0, list.length 1);
}
public static int bsearch(int[] list, int target,

int first, int last){
if( first <= last ){
int mid = low + ((high - low) / 2);
if( list[mid] == target )
return mid;
else if( list[mid] > target )
return bsearch(list, target, first, mid 1);
else
return bsearch(list, target, mid + 1, last);
}
return -1;
}

148
Other Searching Algorithms
Interpolation Search
more like what people really do
Indexed Searching
Binary Search Trees
Hash Table Searching
Grover's Algorithm (Waiting for
quantum computers to be built)
best-first
A*
149
Sorting

150
Sorting Fun
Why Not Bubble Sort?

151
Sortingfor computers
A fundamental application
Done to make finding data (searching) faster
Many different algorithms for sorting
One of the difficulties with sorting is working
with a fixed size storage container (array)
if resize, that is expensive (slow)
The "simple" sorts run in quadratic time O(N2)
bubble sort
selection sort
insertion sort

152
Stable Sorting
A property of sorts
If a sort guarantees the relative order of equal
items stays the same then it is a stable sort
[71, 6, 72, 5, 1, 2, 73, -5]
subscripts added for clarity
[-5, 1, 2, 5, 6, 71, 72, 73]
result of stable sort
Real world example:
sort a table in Wikipedia by one criteria, then another
sort by country, then by major wins
153
Algorithm
Selection sort
Search through the list and find the smallest element
swap the smallest element with the first element
repeat starting at second element and find the second
smallest element
public static void selectionSort(int[] list)
{ int min;
int temp;
for(int i = 0; i < list.length - 1; i++) {
min = i;
for(int j = i + 1; j < list.length; j++)
if( list[j] < list[min] )
min = j;
temp = list[i];
list[i] = list[min];
list[min] = temp;
}
}
154
Selection Sort in Practice
44 68 191 119 119 37 83 82 191 45 158 130 76 153 39 25
What is the T(N), actual number of statements executed, of the selection

sort code, given a list of N elements? What is the Big O?

155
public
Generic Selection Sort
void selectionSort(Comparable[] list)
{ int min; Comparable temp;
for(int i = 0; i < list.length - 1; i++) {
{ min = i;
for(int j = i + 1; j < list.length; j++)
if( list[min].compareTo(list[j]) > 0 )
min = j;
temp = list[i];
list[i] = list[min];
list[min] = temp;
}
}
Best case, worst case, average case Big O?

156
Is selection sort always stable?
A. Yes
B. No

157
Insertion Sort
Another of the O(N^2) sorts
The first item is sorted
Compare the second item to the first
if smaller swap
Third item, compare to item next to it
need to swap
after swap compare again
And so forth
158
Insertion Sort Code
public void insertionSort(int[] list)
{ int temp, j;
{ temp = list[i];
j = i;
while( j > 0 && temp < list[j - 1])
{ // swap elements
list[j] = list[j - 1];
list[j - 1] = temp;
j--;
}
}
}
Best case, worst case, average case Big O?
159
Is the version of insertion sort shown always
stable?
A. Yes
B. No

160
Comparing Algorithms
Which algorithm do you think will be faster
given random data, selection sort or insertion
sort?
Why?

161
Sub Quadratic
Sorting Algorithms
Sub Quadratic means having a Big O
better than O(N2)

162
ShellSort
Created by Donald Shell in 1959
Wanted to stop moving data small distances
(in the case of insertion sort and bubble sort)
and stop making swaps that are not helpful (in
the case of selection sort)
Start with sub arrays created by looking at
data that is far apart and then reduce the gap
size
163
ShellSort in practice
46 2 83 41 102 5 17 31 64 49 18
Gap of five. Sort sub array with 46, 5, and 18
5 2 83 41 102 18 17 31 64 49 46
Gap still five. Sort sub array with 2 and 17
5 2 83 41 102 18 17 31 64 49 46
5 2 31 41 102 18 17 83 64 49 46
Gap still five Sort sub array with 41 and 64
5 2 31 41 102 18 17 83 64 49 46
5 2 31 41 49 18 17 83 64 102 46
Continued on next slide:

164
Completed Shellsort
5 2 31 41 49 18 17 83 64 102 46
Gap now 2: Sort sub array with 5 31 49 17 64 46
5 2 17 41 31 18 46 83 49 102 64
Gap still 2: Sort sub array with 2 41 18 83 102
5 2 17 18 31 41 46 83 49 102 64
Gap of 1 (Insertion sort)
2 5 17 18 31 41 46 49 64 83 102
Array sorted

165
0 1 2 Shellsort on Another Data Set
3 4 5 6 7 8 9 10 11 12 13 14 15
44 68 191 119 119 37 83 82 191 45 158 130 76 153 39 25
Initial gap = length / 2 = 16 / 2 = 8

initial sub arrays indices:
{0, 8}, {1, 9}, {2, 10}, {3, 11}, {4, 12}, {5, 13}, {6, 14}, {7, 15}
next gap = 8 / 2 = 4
{0, 4, 8, 12}, {1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15}
next gap = 4 / 2 = 2
{0, 2, 4, 6, 8, 10, 12, 14}, {1, 3, 5, 7, 9, 11, 13, 15}
final gap = 2 / 2 = 1

166
ShellSort Code
public static void shellsort(Comparable[] list)
{ Comparable temp; boolean swap;
for(int gap = list.length / 2; gap > 0; gap /= 2)
for(int i = gap; i < list.length; i++)
{ Comparable tmp = list[i];
int j = i;
for( ; j >= gap &&
tmp.compareTo( list[j - gap] ) < 0;
j -= gap )
list[ j ] = list[ j - gap ];
list[ j ] = tmp;
}
}

167
Num Items
Comparison
Selection
of Various
Insertion
Sorts
Shellsort Quicksort
1000 16 5 0 0
2000 59 49 0 6
4000 271 175 6 5
8000 1056 686 11 0
16000 4203 2754 32 11
32000 16852 11039 37 45
64000 expected? expected? 100 68
times in milliseconds
168

Quicksort
Invented by C.A.R. (Tony) Hoare
A divide and conquer approach
that uses recursion
1. If the list has 0 or 1 elements it is sorted
2. otherwise, pick any element p in the list. This is called
the pivot value
3. Partition the list minus the pivot into two sub lists
according to values less than or greater than the pivot.
(equal values go to either)
4. return the quicksort of the first list followed by the
quicksort of the second list
169
Quicksort in Action
39 23 17 90 33 72 46 79 11 52 64 5 71
Pick middle element as pivot: 46
Partition list
23 17 5 33 39 11 46 79 72 52 64 90 71
quick sort the less than list
23 17 5 11 33 39
quicksort the less than list, pivot now 5
{} 5 23 17 11
quicksort the less than list, base case
quicksort the greater than list
and so on.

170
0 1 2 Quicksort on Another Data Set
3 4 5 6 7 8 9 10 11 12 13 14 15
44 68 191 119 119 37 83 82 191 45 158 130 76 153 39 25
Big O of Quicksort?

171
public static void swapReferences( Object[] a, int index1, int index2 )
{ Object tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
public void quicksort( Comparable[] list, int start, int stop )
{ if(start >= stop)
return; //base case list of 0 or 1 elements
int pivotIndex = (start + stop) / 2;
// Place pivot at start position
swapReferences(list, pivotIndex, start);
Comparable pivot = list[start];
// Begin partitioning
int i, j = start;
// from first to j are elements less than or equal to pivot
// from j to i are elements greater than pivot
// elements beyond i have not been checked yet
for(i = start + 1; i <= stop; i++ )
{ //is current element less than or equal to pivot
if(list[i].compareTo(pivot) <= 0)
{ // if so move it to the less than or equal portion
j++;
swapReferences(list, i, j);
}
}
//restore pivot to correct spot
swapReferences(list, start, j);
quicksort( list, start, j - 1 ); // Sort small elements
quicksort( list, j + 1, stop ); // Sort large elements
}
172
What is the best case and worst case Big O of
quicksort?
Best Worst
A. O(NlogN) O(N2)
B. O(N2) O(N2)
C. O(N2) O(N!)
D. O(NlogN) O(NlogN)
E. O(N) O(NlogN)
173
Quicksort Caveats
Average case Big O?
Worst case Big O?
Coding the partition step is usually the hardest
part

174
You have 1,000,000 items that you will be
searching. How many searches need to be
performed before the data is changed to make
sorting worthwhile?
A. 10
B. 40
C. 1,000
D. 10,000
E. 500,000
175
Merge Sort Algorithm
Don Knuth cites John von Neumann as the creator
of this algorithm
1. If a list has 1 element or 0

elements it is sorted
2. If a list has more than 2 split into
into 2 separate lists
3. Perform this algorithm on each of
those smaller lists
4. Take the 2 sorted lists and merge
them together
176
Merge Sort
When implementing
one temporary array
is used instead of
multiple temporary
arrays.
Why?

177
/**
Merge Sort code
* perform a merge sort on the data in c
* @param c c != null, all elements of c
* are the same data type
*/
public static void mergeSort(Comparable[] c)
{ Comparable[] temp = new Comparable[ c.length ];
sort(c, temp, 0, c.length - 1);
}
private static void sort(Comparable[] list, Comparable[] temp,

int low, int high)
{ if( low < high){
int center = (low + high) / 2;
sort(list, temp, low, center);
sort(list, temp, center + 1, high);
merge(list, temp, low, center + 1, high);
}
}

178
Merge Sort Code
private static void merge( Comparable[] list, Comparable[] temp,
int leftPos, int rightPos, int rightEnd){
int leftEnd = rightPos - 1;
int tempPos = leftPos;
int numElements = rightEnd - leftPos + 1;
//main loop
while( leftPos <= leftEnd && rightPos <= rightEnd){
if( list[ leftPos ].compareTo(list[rightPos]) <= 0){
temp[ tempPos ] = list[ leftPos ];
leftPos++;
}
else{
temp[ tempPos ] = list[ rightPos ];
rightPos++;
}
tempPos++;
}
//copy rest of left half
while( leftPos <= leftEnd){
temp[ tempPos ] = list[ leftPos ];
tempPos++;
leftPos++;
}
//copy rest of right half
while( rightPos <= rightEnd){
temp[ tempPos ] = list[ rightPos ];
tempPos++;
rightPos++;
}
//Copy temp back into list
for(int i = 0; i < numElements; i++, rightEnd--)
list[ rightEnd ] = temp[ rightEnd ];
}

179
Final Comments
Language libraries often have sorting
algorithms in them
Java Arrays and Collections classes
C++ Standard Template Library
Python sort and sorted functions
Hybrid sorts
when size of unsorted list or portion of array is
small use insertion sort, otherwise use
O(N log N) sort like Quicksort of Mergesort
Many other sorting algorithms exist.
180
Introduction to UNIX
(and Linux)
181
Operating Systems
An operating system (OS) is a software that:

manages the resources of a computer: CPU, memory, devices
provides programmers and users with an interface to access
those resources.
may support/provide: multi-tasking, multi-users, GUI, security,
etc.
Interfaces:
Application Program OS Hardware

Users User Interface User Interface Kernal
Shell: a user interface based on a command-line
interpreter.
182
The Unix OS
Unix: multi-user, multi-tasking OS;
open source.
History:
1969 Initial version by
Thompson & Ritchie at AT&T Bell Labs.
70s Rewritten in C (enables portability).
80s System-V (AT&T) and BSD (Berkeley) versions.
90s Linux by Linus Torvalds.
For basic introduction and commands -
see course web-page (unix.doc)
183
Basic commands in Unix shells
Command Short explanation
ls -l prints the content of a directory
pwd prints the name of the current
directory
cd change directory
mkdir creates a new directory
cp copies a file
mv moves a file/directory
rm removes (deletes) a file
rmdir removes an empty directory
man help (manual) on a command 184
Additional Unix commands
cat concatenate files and print to standard output
cat file1
cat file1 file2 file3
less file viewer (less is better than more)
which locate a command
groups prints the groups the user in (permission...)
grep prints lines matching to a pattern
grep i .*lib.* foo.bar
find search for a file in a directory
find . name *.txt print
find ~/ name *.o -exec rm {} \;
clear clears the terminal screen
finger prints information about a user
who shows who is logged in
whoami identifies the current user
185
File and directory permissions in
Unix
permissions group
permissions = bits 2-10 (bit 1: d=directory, - = file)
bit 1 = whether is a directory (d) or not (-)
bits 2-4: owner permissions
bits 5-7: group permissions
bits 8-10: other permissions
rwx:
r read permission
w write permission
x execute (file)/ can cd (directory)
changing permissions: chmod
chmod go+rx a.out
chmod R 755 mydir
186
Editing text files in Unix
Common text editors:
pico - simple but very basic, similar to notepad
vi, vim
emacs, xemacs (GUI) - see course webpage for a
simple tutorial
More info: man pico, man vi, man vim
man emacs
187
Pipes and redirections to/from files
Pipe: prog1 | prog2 the output of prog1 is redirected to
the input of prog2
Example: ls l | less
Output redirection to file
prog > foo.out :may cause an error if foo.out exists
prog >! foo.out :truncates foo.out if exists
prog >> foo.out :may cause error if foo.out does NOT exist
prog >>! foo.out :does not check whether foo.out exists
Input redirection (read from file)
prog < foo.in
188
Comparing files (program tests)
prog <1.in >! my1.out : reading from 1.in and

writing to 1.out
diff my1.out 1.out compares files line by line
Ignoring all whitespaces:
diff w my1.out 1.out
189
Basic tools in UNIX
190
Compiling and linking
Compiling and linking
gcc hello.c o hello
Only compiling (creating hello.o)
gcc c hello.c
Only linking
gcc hello.o o hello
Additional common flags to gcc:
-g allows debugging
-l<library-name> - linking with external libraries
191
Make and makefiles (in short)
makefile: a collection of rules to make targets
make: a utility that executes makefiles
all: hello
target name clean:
-rm hello.o hello rule
hello: hello.o
dependencies gcc -g hello.o -o hello
command hello.o: hello.c
gcc -c -g hello.c
Makefiles will be
covered later in
the course. In the
meanwhile,
makefiles will be
supplied
192
[ Section 8.3 ]
Heaps
- complete binary trees with the heap property
- complete: for every k < (depth of the tree), there are 2k (i.e. maximum possible) nodes
at depth k. For the last level (equivalent to the depth), the nodes are arranged from left
to right with no gaps
- heap property: for every non-leaf node v, the key at v is smaller than or equal to the
keys of all its children
[ Section 8.3 ]
Heaps
Height of a heap with n keys:
[ Section 8.3 ]
Heaps
Convenient array representation:
[ Section 8.3 ]
Priority queues via heaps
- used for implementation of the priority queue data type [see also Section 8.1]
- priority queue: supports insert(x), removeMin()
[ Section 8.3 ]
How to implement insert(x) ?
What is the running time ?

[ Section 8.3 ]
How to implement removeMin() ?
What is the running time ?

[ Section 8.3 ]
HeapSort
- a sort that uses the heap datastructure
Running time:
[ Section 13.1 ]
Graphs
Generalization of trees, can include cycles. Formally,
G = (V,E) where V = set of nodes, E VV = set of edges
(undirected or directed edges)
Notation: n = |V|, m = |E|

[ Section 13.1 ]
Graphs
Typical graph properties/terminology:
- path (directed path)
- cycle
- subgraph
- connected
- connected component
- spanning tree
[ Section 13.2 ]
Graph representations
- edge list
- adjacency lists
- adjacency matrix
[ Section 13.3 ]
Graph traversals
- BFS (breadth first search)
- DFS (depth first search)
[ Section 13.3 ]
Graph traversals
BFS (breadth first search) pseudocode
Running time:
[ Section 13.3 ]
Graph traversals
DFS (breadth first search) pseudocode
Running time:
[ Section 13.4.3 ]
Topological sort
Given is a directed acyclic graph, find an order of the nodes such that every edge goes
from an earlier node to a later node.
[ Section 13.4.3 ]
Topological sort
Topological sort via DFS with time-stamps
Running time:
What is a Network?
A network consists of 2 or more computers
connected together, and they can
communicate and share resources (e.g.
information)
208
Why Networking?
Sharing information i.e. data
communication
Do you prefer these?
Or this?
209
Sharing hardware or software
E.g. print document
Centralize administration and support

E.g. Internet-based, so everyone can access the same administrative
or support application from their PCs
210
How many kinds of Networks?
Depending on ones perspective, we can
classify networks in different ways
Based on transmission media: Wired (UTP, coaxial cables, fiber-
optic cables) and Wireless
Based on network size: LAN and WAN (and MAN)
Based on management method: Peer-to-peer and Client/Server
Based on topology (connectivity): Bus, Star, Ring
:
:
211
Transmission Media
Two main categories:
Guided wires, cables
Unguided wireless transmission, e.g. radio,
microwave, infrared, sound, sonar
We will concentrate on guided media here:
Twisted-Pair cables:
Unshielded Twisted-Pair (UTP) cables
Shielded Twisted-Pair (STP) cables
Coaxial cables
Fiber-optic cables
212
Twisted-Pair Cables
If the pair of wires are not twisted, electromagnetic
noises from, e.g., motors, will affect the closer wire more
than the further one, thereby causing errors
213
Unshielded Twisted-Pair (UTP)
Typically wrapped inside a plastic cover (for mechanical
protection)
A sample UTP cable with 5 unshielded twisted pairs of wires
Insulator Metal
214
Shielded Twisted-Pair (STP)
STP cables are similar to UTP cables, except there is a
metal foil or braided-metal-mesh cover that encases each
pair of insulated wires
215
Categories of UTP Cables
EIA classifies UTP cables according to the quality:
Category 1 the lowest quality, only good for voice, mainly
found in very old buildings, not recommended now
Category 2 good for voice and low data rates (up to 4Mbps
for low-speed token ring networks)
Category 3 at least 3 twists per foot, for up to 10 Mbps
(common in phone networks in residential buildings)
Category 4 up to 16 Mbps (mainly for token rings)
Category 5 (or 5e) up to 100 Mbps (common for networks
targeted for high-speed data communications)
Category 6 more twists than Cat 5, up to 1 Gbps
216
Coaxial Cables
In general, coaxial cables, or coax, carry signals of higher freq
(100KHz500MHz) than UTP cables
Outer metallic wrapping serves both as a shield against noise
and as the second conductor that completes the circuit
217
Fiber-Optic Cables
Light travels at 3108 ms-1 in free space and is the fastest
possible speed in the Universe
Light slows down in denser media, e.g. glass
Refraction occurs at interface, with light bending away from
the normal when it enters a less dense medium
Beyond the critical angle total internal reflection

218
An optical fiber consists of a core (denser material) and a
cladding (less dense material)
Simplest one is a multimode step-index optical fiber
Multimode = multiple paths, whereas step-index = refractive
index follows a step-function profile (i.e. an abrupt change
of refractive index between the core and the cladding)
Light bounces back and forth along the core
Common light sources: LEDs and lasers
219
Advantages and Disadvantages
Noise resistance external light is blocked by outer jacket
Less signal attenuation a signal can run for miles without
regeneration (currently, the lowest measured loss is about
~4% or 0.16dB per km)
Higher bandwidth currently, limits on data rates come from
the signal generation/reception technology, not the fiber itself
Cost Optical fibers are expensive
Installation/maintenance any crack in the core will degrade
the signal, and all connections must be perfectly aligned
220
LAN and WAN
Local Area Network (LAN)
Small network, short distance
A room, a floor, a building
Limited by no. of computers and distance covered
Usually one kind of technology throughout the LAN
Serve a department within an organization
Examples:
Network inside the Student Computer Room
Network inside CF502
Network inside your home
221
Wide Area Network (WAN)
A network that uses long-range telecommunication links to connect
2 or more LANs/computers housed in different places far apart.
Towns, states, countries
Examples:
Network of our Campus Your home
Internet
USA
WAN
Student Computer
Centre
222
Example WAN technologies:
ISDN Integrated Service Digital Network
Basic rate: 192 Kbps Primary rate: 1.544Mbps
T-Carriers basically digital phone lines
T1: 1.544Mbps T3: 28T1
Frame relay
Each link offers 1.544Mbps or even higher
ATM Asynchronous Transfer Mode
Support B-ISDN: 155Mbps or 622Mbps or higher
SONET Synchronous Optical Network
Basic rate OC1: 51.84Mbps
Support OC12 and up to OC192 (9953.28Mbps) or even higher in
the future
223
Example of WAN: Broadband Cable Network
Cable TV services have been extensively developed in most modern
cities
Cable TV companies try to make use of their coaxial cable installed
(that are supposed to carry TV signals) to deliver broadband data
services
Many cable network wiring has been replaced with hybrid fiber-coax
(HFC) i.e. use of fiber-optic cable to connect to the subscribers
buildings, and then the original coaxial cable to connect to each
household
224
The connection is shared by a number of
subscribers, hence may raise
performance and security problems
PC
TV
Cable
Drop
Coaxial Cable company
Cable
225
Cable is an asymmetrical technology
Downstream: max 36 Mbps
Upstream: max 10 Mbps
May be reduced to 3 10 Mbps downstream

and 2 Mbps upstream, depending on no. of
subscribers
Need a special cable modem Ethernet
link to PC
Teryon Cable Modem Coaxial link

from cable TV
socket
226
Peer-to-Peer Networks
Peer-to-peer network is also called
workgroup
No hierarchy among computers all are
equal
No administrator responsible for the network
Peer-to-peer
227
Advantages of peer-to-peer networks:
Low cost
Simple to configure
User has full accessibility of the computer
Disadvantages of peer-to-peer networks:

May have duplication in resources
Difficult to uphold security policy
Difficult to handle uneven loading
Where peer-to-peer network is appropriate:

10 or less users
No specialized services required
Security is not an issue
Only limited growth in the foreseeable future
228
Clients and Servers
Network Clients (Workstation)
Computers that request network resources or services
Network Servers
Computers that manage and provide network resources and services
to clients
Usually have more processing power, memory and hard disk
space than clients
Run Network Operating System that can manage not only data,
but also users, groups, security, and applications on the network
Servers often have a more stringent requirement on its
performance and reliability
229
Advantages of client/server networks
Facilitate resource sharing centrally administrate and control
Facilitate system backup and improve fault tolerance
Enhance security only administrator can have access to Server
Support more users difficult to achieve with peer-to-peer
networks
Disadvantages of client/server networks

High cost for Servers
Need expert to configure the network
Introduce a single point of failure to the system
230
Topology 3 basic types
How so many computers are connected
together?
Bus Topology Ring
Topology
Star Topology
Hub
231
Bus Topology
Simple and low-cost
A single cable called a trunk (backbone, segment)
Only one computer can send messages at a time
Passive topology - computer only listen for, not regenerate data
Star Topology
Each computer has a cable connected to a single point
More cabling, hence higher cost
All signals transmission through the hub; if down, entire network
down
Depending on the intelligence of hub, two or more computers may
send message at the same time
232
How to construct a network
with Bus / Star Topology?
Bus Topology
Coaxia
l cable
Star Topology
BNC T-Connector
233
Network Card
Ring Topology
Every computer serves as Ack T T
a repeater to boost signals T
Typical way to send data:
T dat T dat
Token passing
a a
only the computer who
gets the token can send T
data T
T Ack
Disadvantages T Ack
dat
Difficult to add computers a
More expensive T
If one computer fails, whole network fails T Ack
234
CT
Seeram
Chapter 2:
Introduction
to Computers
Electronic Computer Technology
Vacuum tubes
Discrete Semiconductors
Integrated Circuits
Early Computers
1951-1958
Vacuum tube memory
Input / Output
Punch cards
Magnetic Tape
Electronic Computer Technology
Warm-up
Ran hot
tube filaments required
constant heating
computers required air
conditioning
Frequent failures
Computers after Vacuum Tubes
1959-1963
Transistor & magnetic
core memory
Smaller
Less power needed
Discrete Semiconductor Components
in Computers
transistors
magnetic memory cores
Space requirements
large
but
smaller than vacuum tubes
Ran much cooler than vacuum tubes
Computers: The Big Jump
Integrated Circuits
millions of semiconductor components in tiny
package
lower production costs
Extremely small
Extremely fast
Run very cool
Very reliable
Categories of Computers
Super computers
Mainframes
Minicomputers
Microcomputers
5th Generation:
Supercomputers
Large (even today)

Expensive
Found only in major research sites
Applications
weather
scientific modeling
oil exploration
other research
Mainframe Computers
Large
$$$
Requires teams of experts
Large # of users
Applications
large corporations
government
hospitals
Microcomputer
PC
Rapidly changing
technology
Low cost
Non-proprietary
First common in
1980s
Minicomputers
First seen in 1970s
Much less expensive than mainframes
Medium-sized
Proprietary ($$$)
parts
operating systems
Computer used for CT
Appropriate
Size
price
Applications
imaging, reconstruction
archiving
Basics
Input Processing Output

Input
Manual Other
keyboard Voice
mouse recognition
Electronic
CT detectors
CR Plates

Analog to Digital Conversion
(A to D)
Analog
(continuously varying)
Digital
(discretely varying)
Analog to Digital Conversion
(A to D)
Many real world inputs are analog voltages
CT detector intensity
Analog values must be converted to a # to use in a
computer
0.8
0.6
Input
analog
voltage 0.4
0.2
Digital conversion to
computer 1 2 3 4
Processing
Central Processing Unit (CPU)
Arithmetic
Logic
Internal Memory
Scratchpad

Output
Hard copy Storage
printer disk
Soft copy tape
CRT

Hardcopy Devices
Do not lose
information when
power is shut off
Printers
impact (dot
matrix)
noisy
multi-copy
non-impact (quiet)
ink jet
laser
Softcopy Devices
Lose all information
when power shut off
Flat-panel monitors
Digital to Analog Conversion
(D to A)
Computer reconstructs digital image
set of numbers
Computer displays analog image
125 25 311 111 182 222 176
199 192 85 69 133 149 112
77 103 118 139 154 125 120
145 301 256 223 287 256 225
178 322 325 299 353 333 300

Computer System Elements
Hardware Software
People
Hardware
Computer
Peripherals
keyboard Hardware Software
printer
People
Hardware
Examples
Disk Drive
Memory
Random Access
(RAM)
Read only
(ROM)
Mouse Hardware Software
Keyboard
People
Cables
Software
Instructions to computer
Operating System
Applications
Hardware Software
People
Operating System
Fundamental instructions to hardware

What to do when computer first turned on
How to interact with hardware
CRT
Keyboard
Mouse
Modem
Hardware Software
People
Operating System
Computer face presented to users
Windows
DOS
MAC OS
Dictates how users
interact with
computer to
run application
software
Hardware Software
People
Application Software
Computer instructions which perform

some desired task
Balance checkbook
Play a game
Calculate (reconstruct)
a CT image
Hardware Software
People
Application Software
Usually a quasi-
English language Forms![FDoSurvey]![FExpsSub].Form![KVEff] = Val(Mid$(MyData, 2, 10))
Forms![FDoSurvey]![FExpsSub].Form![KVAVG] = Val(Mid$(MyData, 12, 10))
Forms![FDoSurvey]![FExpsSub].Form![MRMEAS] = Val(Mid$(MyData, 22, 10))
Basic Forms![FDoSurvey]![FExpsSub].Form![TIMEMEAS] = Val(Mid$(MyData, 32, 10))
DumText = Mid$(MyData, 42, 3)
Fortran 'MsgBox$ (DumText)
If Right$(DumText, 1) = "+" Then
COBOL DumText = Left$(DumText, 2)
Else
C DumText = Left$(DumText, 1)
End If
Languages provide 'MsgBox (DumText)

MyData = Right$(MyData, Len(MyData) - Len(DumText) - 41)
tools to software 'MsgBox (MyData)

NKvs = Val(DumText)
developers to 'MsgBox (NKvs)

KVMAX = 0
efficiently design If NKvs > 0 Then

For DumNum = 1 To NKvs
application software 'MsgBox (Val(Mid$(MyData, 10 * (DumNum - 1) + 1, 10)))
If (Val(Mid$(MyData, 10 * (DumNum - 1) + 1, 10))) > KVMAX Then
KVMAX = (Val(Mid$(MyData, 10 * (DumNum - 1) + 1, 10)))
End If
Next
Forms![FDoSurvey]![FExpsSub].Form![KVMAX] = KVMAX
End If
DoCmd.Close acForm, "FNeroExp"
End Sub
People
Designers
hardware
software
Users
run applications
provide input
use output
Meaningless Slide
Storage Hardware
Random vs. Sequential
Direct (random) access
any data can be accessed at any time
disks
Sequential access
data only accessed in serial fashion
must pass through unwanted data to reach
target data
tapes
information encoded magnetically
Data Storage Technologies
(constantly changing)
Disks
Technologies
Formats
Magnetic (disks & tape)
Hard re-writable
removable optical (disks & CDs)
non-
re-writable
removable
write once
Floppy
CD
CD-RW
CD-R
Tape
lots of data
serial access
Data Communication
Data
transmission between
computers
Features
speed
cost
topology
wiring
scheme
Data Communication Technologies
Telephone lines
twisted pair wires
Coaxial cable
Fiber optic cable
Microwaves
Satellites
Radio waves
Networks
LAN (Local area network)
computers connected in one area
LANs can be connected together
WAN (Wide area network)
computers connected together over large
distances
Communications protocols
Ethernet
uses bus technology
Internet
File Server
Special computer which handles functions
for connected computers
disk access
printing
Incorporates security
may limit user to selected files or directories
may limit # of connections per user
may limit times when network available
Typical Lan
Network
Gateway
Other
Networks
Radiology Computer Systems
Insurance
Hospital Carrier Voice to Text
Admission/Discharge Dictation
Billing PACS
Reports
Web
RIS Digital Spot Film
Server
Digital Dictation
Professional
Billing Angio /
Digital
CT Subtraction
Mammography MRI
CR
The Computerization of
Nuc
Radiology Digital Digital
CT CR MRI
Med Fluoro Angio
Web Browser
3D Laser
Workstation RIS PACS
Printer
Dictation Admin
Radiologist Radiologist Radiologist

Workstation Workstation Workstation
The Internet
Network connecting all computers
Originally developed for security
Single bomb cant destroy all U.S. computing facilities
Can connect large number of computers in many
locations
Communicates in finite packets
Each packet has specific destination (address)
Packets can be
E-mail
Web site
Allows linking of information
IV054
INTRODUCTION
Transmission of classical information in time

and space is nowadays very easy (through
noiseless channel).
It took centuries, and many ingenious
developments and discoveries(writing, book
printing, photography, movies, radio
transmissions,TV,sounds recording) and the idea
of the digitalization of all forms of information
to discover fully this property of information.
Basics of coding theory 276
IV054
HISTORY OF CRYPTOGRAPHY
The history of cryptography is the story of centuries-old battles

between codemakers and codebreakers, an intellectual arms race that
has had a dramatic impact on the course of history.
The ongoing battle between codemakers and codebreakers has

inspired a whole series of remarkable scientific breakthroughts.
History is full of codes. They have decided the outcomes of battles

and led to the deaths of kings and queens.

IV054
CHAPTER 1: Basics of coding theory
ABSTRACT
Coding theory - theory of error correcting codes

- is one of the most interesting and applied part
of mathematics and informatics.
All real systems that work with digitally
represented data, as CD players, TV, fax
machines, internet, satelites, mobiles, require to
use error correcting codes because all real
channels are, to some extent, noisy.
IV054
Coding - basic concepts
Without coding theory and error-correcting
codes there would be no deep-space travel and
pictures, no satelite TV, no compact disc, no
no no .
Error-correctingError
codes areframework
correcting used to correct
messages when they are transmitted through
Example
noisy channels.
A code C over an alphabet S is a subset of S* - (C S*).
A q -nary code is a code over an alphabet of q -symbols.
A binary code is a code over the alphabet {0,1}.
Examples of codes C1 = {00, 01, 10, 11} C2 = {000, 010, 101, 100}
C3 = {00000, 01101, 10111, 11011}
IV054
CHANNEL
is the physical medium through which

information is transmitted.
NOISE
(Telephone
may lineslighting,
be caused by sunpots, andmeteor
the showers,
atmosphere
random radioare
disturbance,
poor typing, poor hearing, .
examples of channels.)
TRANSMISSION GOALS
1. Fast encoding of information.
2. Easy transmission of encoded messages.
3. Fast decoding of received messages.
4. Reliable correction of errors introduced in the channel.
5. Maximum transfer of information per unit time.
METHOD OF FIGHTING ERRORS: REDUNDANCY!!!

0 is encoded as 00000 and 1 is encoded as 11111.

BASIC IDEA
The details of techniques used to protect information
against noise in practice are sometimes rather complicated,
but basic principles are easily understood.
The key idea is that in order to protect a message against a

noise, we should encode the message by adding some
redundant information to the message.
In such a case, even if the message is corrupted by a noise,

there will be enough redundancy in the encoded message
to recover, or to decode the message completely.
EXAMPLE
In case of: the encoding
1
2
0000 1 111
the probability of the bit error p , and the

3 p (1 p) p 3 p 2 p p
2 3 2 3
majority voting decoding
000, 001, 010, 100 000, 111, 110, 101,

011 111
IV054EXAMPLE: Codings of a path avoiding an enemy territory
Story Alice and Bob share an identical map (Fig.

1) gridded as shown in Fig.1. Only Alice knows
theNNWNNWWSSWWNNNNWWN
route through which Bob can reach her
avoiding the enemy territory.
Three ways to encode the safe route from
Alice wants to
send
Bob Bob
to Alice are: the following information about the
1. C = {00, 01, 10, 11}
safe route
Any error
1
heword
in the code should take.
000001000001011111010100000000010100
would be a disaster.
2. C2 = {000, 011, 101, 110}
A single error in encoding each of symbols N, W, S, E could be detected.
3. C3 = {00000, 01101, 10110, 11011}
A single error in decoding each of symbols N, W, S, E could be corrected.
IV054
Basic terminology
Block code - a code with all words of the same

length.
Basic assumptions about channels
Codewords - words of some code.
1. Code length preservation Each output codeword of a channel has the same
length as the input codeword.
2. Independence of errors The probability of any one symbol being affected in
transmissions is the same.
Basic strategy for decoding

For decoding we use the so-called maximal likehood principle, or nearest neighbor
decoding strategy, which says that the receiver should decode a word w' as that
codeword w that is the closest one to w'.

IV054
Hamming distance
The intuitive concept of closeness'' of two words is well formalized through Hamming distance h(x, y)
of words x, y.
For two words x, y
h(x, y) = the number of symbols x and y differ.
Example: h(10101, 01100) = 3, h(fourth, eighth) = 4
Properties of Hamming distance

(1) h(x, y) = 0 x = y
(2) h(x, y) = h(y, x)
(3) h(x, z) h(x, y) + h(y, z) triangle inequality
An important parameter of codes C is their minimal distance.
h(C) = min {h(x, y) | x,y C, x y},
because it gives the smallest number of errors needed to change one codeword into anther.
Theorem Basic error correcting theorem
(1) A code C can detected up to s errors if h(C) s + 1.
(2) A code C can correct up to t errors if h(C) 2t + 1.
Proof (1) Trivial.
(2) Suppose h(C) 2t + 1. Let a codeword x is transmitted and a word y is recceived with h(x,
y) t. If x' x is a codeword, then h(x y) t + 1 because otherwise h(x', y) < t + 1 and
therefore h(x, x') h(x, y) + h(y, x') < 2t + 1 what contradicts the assumption h(C) 2t + 1.

IV054
Binary symmetric channel
Consider a transmition of binary symbols such

that each symbol has probability of error p <
1/2.
pt 1 p .
n t n
t
Binary symmetric
channel
If n symbols are transmitted, then the

probability of t errors is
In the case of binary symmetric channels the

nearest neighbour decoding strategy is also
IV054
Addition of one parity-check bit
Example Let all 211 of binary words of length 11

be codewords.
Let the probability of an
11 p1 p
error
11
.
be 10 -8.
10
8
10
Let bits be
0.transmitted
1
11
108
107
11 at the rate 107 bits per

second.
The probability that a word is transmitted
incorrectly1 is
1 approximately
p 121 p p 1 p p
12 11 66
12
2
10 2
1016
1012 5.5 10 9
7
66
1016
Therefore of words per second are

transmitted incorrectly.
IV054
TWO-DIMENSIONAL PARITY CODE
The two-dimensional parity code arranges the data into a two-dimensional array and
then to each row (column) parity bit is attached.
Example Binary string
10001011000100101111
is represented and encoded as follows
1 0 0 0 1 0
1 0 0 0 1
0 1 1 0 0 0
0 1 1 0 0
0 1 0 0 1 0
0 1 0 0 1
0 1 1 1 1 0
0 1 1 1 1
1 1 0 1 1 0
Question How much better is two-dimensional encoding than one-dimensional

encoding?

IV054
Notation and Examples
Notation: An (n,M,d) - code C is a code such that

n - is the length of codewords.
M - is the number of codewords.
d - is the minimum distance in C.
Example:
C1 = {00, 01, 10, 11} is a (2,4,1)-code.
C2 = {000, 011, 101, 110} is a (3,4,2)-code.
C3 = {00000, 01101, 10110, 11011} is a (5,4,3)-code.
Comment: A good (n,M,d) code has small n and large M and d.

IV054
Notation and Examples
Example (Transmission of photographs from the deep space)

In 1965-69 Mariner 4-5 took the first photographs of another planet - 22
photos. Each photo was divided into 200 200 elementary squares - pixels.
Each pixel was assigned 6 bits representing 64 levels of brightness. Hadamard
code was used.
Transmission rate: 8.3 bits per second.
In 1970-72 Mariners 6-8 took such photographs that each picture was
broken into 700 832 squares. Reed-Muller (32,64,16) code was used.
Transmission rate was 16200 bits per second. (Much better pictures)

IV054
HADAMARD CODE
In Mariner 5, 6-bit pixels were encoded using 32-bit long Hadamard code
that could correct up to 7 errors.
Hadamard code had 64 codewords. 32 of them were represented by the 32

32 matrix H = {hIJ}, where 0 i, j h 4and
1a b a b ...a b
0 0 1 1 4 4
ij
where i and j have binary representations

i = a4a3a2a1a0, j = b4b3b2b1b0.
The remaing 32 codewords were represented by the matrix -H.

Decoding was quite simple.

IV054
CODE RATE
For q-nary (n,M,d)-code we define codelgrate,

q M or information rate, R, by
R .
n
The code rate represents the ratio of the number of input data symbols to
the number of transmitted code symbols.
Code rate (6/12 for Hadamard code), is an important parameter for real
implementations, because it shows what fraction of the bandwidth is being
used to transmit actual data.

IV054
The ISBN-code
Each recent book has International Standard

Book Number which is a 10-digit codeword
produced by the publisher with the following
10
structure: ix 0 mod 11 i 1
i
l p m w = x x 1 10
language publisher number weighted check sum

0 07 709503 0
Single error detection
such that
Let X = x x be a correct code and let
1 10
Y = x1 xJ-1 yJ xJ+1 x10 with yJ = xJ + a, a 0
In such a case:
The publisherhas
iy to
ix put
ja 0Xmod
10
into11the 10-th
i
10
i
i 1 i 1
position if x10 = 10.
IV054
The ISBN-code
Transposition detection
Let xJ and xk be exchanged.

10 10
iy ix k j x j k x
i 1
i
i 1
i j k
k j x x 0 mod 11
j k if k j and x j xk .

IV054
Equivalence of codes
Definition Two q -ary codes are called

equivalent if one can be obtained from the
other by a combination of operations of the
following type:
(a) a permutation of the positions of the code.
(b) a permutation ofofsymbols
Examples appering in a
equivalent codes
fixed position.
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 2
0 0 0 1 1 0 1 1 0 1
1

Question: Let a code be displayed as an M n
1 1 1 1 1

1 0 1 1 1

2 1 1 1 1 2
2 2 2 2 0 1
0
1 1 0 0 0 1 1 0 1 0
matrix. To what correspond operations (a) and
Lemma Any q -ary (n,M,d) -code over an alphabet {0,1,,q -1} is equivalent to an
(b)?
(n,M,d) -code which contains the all-zero codeword 000.
Proof Trivial.
Claim: Distances between codewords are
IV054
The main coding theory problem
A good (n,M,d) -code has small n, large M and large d.

The main coding theory problem is to optimize one of the parameters n, M, d for
given values of the other two.
Notation: Aq (n,d) is the largest M such that there is an q -nary (n,M,d) -code.
Theorem (a) Aq (n,1) = qn;
(b) Aq (n,n) = q.
Proof
(a) obvios;
(b) Let C be an q -nary (n,M,n) -code. Any two distinct codewords of C differ in all n
positions. Hence symbols in any fixed position of M codewords have to be different
Aq (n,n) q. Since the q -nary repetition code is (n,q,n) -code, we get Aq (n,n) q.

IV054
Example Proof that A2 (5,3) = 4.

(a) Code C3 is a (5,4,3) -code, hence A2 (5,3) 4.
(b) Let C be a (5,M,3) -code with M 4.
By previous lemma we can assume that 00000 C.

C contains at most one codeword with at least four 1's. (otherwise d (x,y) 2 for
two such codewords x, y)
Since 00000 C there can be no codeword in C with one or two 1.
Since d = 3 C cannot contain three codewords with three 1's.
Since M 4 there have to be in C two codewords with three 1's. (say 11100, 00111),
the only possible codeword with four or five 1's is then 11011.

IV054
Theorem Suppose d is odd. Then a binary (n,M,d) -code exists iff a binary (n
+1,M,d +1) -code exists.
Proof Only if case: Let

CC bex1a
...binary
xn xn1 code
x1... xn(n,M,d) iLet
C, xn-code.
1
n
x mod 2
1 i

Since parity of all codewords in C is even, d(x,y) is even for all
x,y C.
Hence d(C) is even. Since d d(C) d +1 and d is odd,
d(C) = d +1.
Hence C is an (n +1,M,d +1) -code.
If case: Let D be an (n +1,M,d +1) -code. Choose code words x, y of D such that d(x,y)
= d +1.
Find a position in which x, y differ and delete this position from all codewords of D.
Resulting code is an (n,M,d) -code.
IV054
Corollary:
If d is odd, then A2 (n,d) = A2 (n +1,d +1).
If d} is even, then A2 (n,d) = A2 (n -1,d -1).
Example A2 (5,3) = 4 A2 (6,4) = 4

(5,4,3) -code (6,4,4) code
00000
01101
10110 by adding check.
11011

IV054
A general upper bound on Aq (n,d)
Notation Fqn is a set of all words of length n over alphabet {0,1,2,,q -1}
Definition For any codeword u Fqn and any integer r 0 the sphere of radius r and
centre u is denoted by
S (u,r) = {v Fqn | d (u,v) r }.
Theorem A sphere of radius r in Fqn, 0 r n contains
q 1 q 1
n
0
n
1
n
2
2
... q 1
n
r
r
words.
Proof Let u be a fixed word in Fqn. The number of words that differ from u in m
position is
n

m q 1 .
m

IV054
Theorem (The sphere-packing or Hamming bound)
If C is a q -nary (n,M,2t +1) -code, then
M q 1 ... q 1 q
n
0
n
1
n
t
t n
(1)
Proof Any two spheres of radius t centered on distinct codewords have no

codeword in common. Hence the total number of words in M spheres of radius
t centered on M codewords is given by the left side (1). This number has to be
less or equal to q n.
A code which achieves the sphere-packing bound from (1), i.e. such that
equality holds in (1), is called a perfect code.

IV054
Example An (7,M,3)M -code is perfect if

2 7 7 7
0 1
i.e. M = 16
An example of such a code:
C4 = {0000000, 1111111, 1000101, 1100010,
n
5
6
d=3
4
8
d=5
2
2
d=7
-
-
0110001, 1011000, 0101100, 7

8 0010110,
16
20
2
4
2
2
9 40 6 2
0001011, 0111010, 0011101, 1001110,
10
11
72-79
144-158
12
24
2
4
12 256 32 4
0100111, 1010011, 1101001, 1110100}
13
14
512
1024
64
128
8
16
Table of A2(n,d) from 1981

15 2048 256 32
16 2560-3276 256-340 36-37

IV054
LOWER BOUND for Aq (n,d)
The following lower bound for Aq (n,d) is known as Gilbert-Varshanov bound:
Theorem Given d n, there exists M q n -code with

a q-ary (n,M,d)
j 0 j q 1
d 1 n j
qn
and therefore Aq n, d
q 1
d 1 n j
j 0 j

IV054
General coding problem
The basic problems of information theory are

how to define formally such concepts as
S X to
information and how pstore
x lg px or transmit
x
information efficiently.
Let X be a random variable (source) which
takes a value x with probability p(x). The
entropy of X is defined by
and it is considered to be the information

content of X.
The maximum information which can be stored
IV054
Shannon's noisless coding theorem
In a simple form Shannon's noisless coding

theorem says that in order to transmit n values
of X we need nS(X) bits.
More exactly, we cannot do better and we can
reach the bound nS(X) as close as desirable.
Example Let a source X produce the value 1
with probability p =
Let the source X produce the value 0
with probability 1 - p =
Assume we want to encode blocks of the
outputs of X of length 4.
IV054
Design of Huffman code
Given a sequence of n objects, x1,,xn with

probabilities p1 pn.
Stage 1 - shrinking of the sequence.
Replace x n -1, x n with a new object y n -1 with
probability p n -1 + p n and rearrange sequence
so one has again nonincreasing probabilities.
Keep doing the above step till the sequence
Stage 2 - extending the code - Apply again and again the following method.
shrinks to two objects.
If C = {c1,,cr} is a prefix optimal code for a source S r, then C' = {c'1,,c'r +1} is an
optimal code for Sr +1, where
c'i = ci 1ir1
c'r = cr1
Basics of coding theory
c'r+1 = cr0. 306
IV054
Design of Huffman code
Stage 2 Apply again and again the following method:
If C = {c1,,cr} is a prefix optimal code for a source S r, then C' = {c'1,,c'r +1} is an
optimal code for Sr +1, where
c'i = ci 1ir1
c'r = cr1
c'r+1 = cr0.

IV054
A BIT OF HISTORY
The subject of error-correcting codes arose originally as a response to

practical problems in the reliable communication of digitally encoded
information.
The discipline was initiated in the paper
Claude Shannon: A mathematical theory of communication, Bell Syst.Tech.

Journal V27, 1948, 379-423, 623-656
Shannon's paper started the scientific discipline information theory and

error-corecting codes are its part.
Originally, information theory was a part of electrical engineering.

Nowadays, it is an important part of mathematics and also of informatics.

IV054
A BIT OF HISTORY
SHANNON's VIEW
In the introduction to his seminal paper A mathematical theory of communication
Shannon wrote:
The fundamental problem of communication is that of reproducing at one

point either exactly or approximately a message selected at another point.

The UNIX File System
Harry Chen
Department of CSEE
University of MD Baltimore County
Introduction
What is File System?
The abstraction used by kernel to represent and
organize the storage resources.
UNIX File System in general
File system is organized in tree structure.
File tree can be arbitrarily deep.
File name must NOT LONGER than 256 chars.
Single path name must NOT LONGER than 1023
chars.
Creating File System
Mounting File System
File tree is composed of File System
Use mount command to map a directory within
the existing file tree (mount point) to the root of
the new file system.
mount /dev/hda2 /usr
Use umount command to detach the file system.
Detaching will fail if the file system is busy.
Organizing of The File System
The UNIX file system has never been very
well organized. -- Page 58
incompatible naming convention
e.g. ATT & BSD startup script naming
e.g. log file naming
Organizing of The File System
(cont.)
/ The root directory
/bin or /sbin Commands for basic
system operation
/dev Device entries
/etc Critical startup and
configuration files.
/lib Library for the C
compiler
/tmp Temporary files
/var/adm or /var/log Accounting file, log
files
Types of Files
Regular Files
binary
GIF, JPEG, Executable etc.
text
scripts, program source code, documentation
Supports sequential and random access
Types of Files (cont.)
Directory
Can contain ANY kind of files
what is . and ..??
Device File
Allows programs to communicate with hardware.
Kernel modules handles device management.
Device Files (cont.)
Character Device
Accepts a stream of characters, without regard to any
block structure.
It is not addressable, therefore no seek operation
Block Device
Information stored in fixed-sized block
It is addressable, therefore seek operation is possible.
UNIX Domain Sockets (BSD)
sockets that are local to a particular host and are
referenced through a file system object rather
than a network port.
X windows
Named Pipe
Allow processes to communicate with each other.
Hard links
Linking files by reference
System maintains a count of the number of links
Does not work across file systems.
Soft links
Linking files by name
No counter is maintained
Work across file system
File Permissions
The Setuid and Setgid bits
Setuid with octal value 4000
Setgid with octal value 2000
These bits allow programs to access files that
processes that would otherwise off limits to the
user that runs them.
Sticky Bit
Not very popular in todays system
If a directory has sticky bit set, then only the
owner can remove file from the directory.
/tmp is a good example.
The Permission Bit
9 permission bits used to determine 3 types of
accesses, READ, WRITE, EXECUTE.
Permission can be set based on GROUP, OWNER,
ANYONE ELSE.
Use chmod command to change permission
Binary 001 for EXECUTE
Binary 010 for WRITE
Binary 100 for READ
INODES
Kernel maintains file information in a structure
called inode.
Creation, modification time stamps
Ownership, file size etc.
Commonly used INODE information can be found
by using ls command
Group information and be modified by using chgrp
command.
Summary
All UNIX file system are very similar.
All file system have this concept of file tree.
Transparent to user even mount point is mapped
to a remote file system.
To communicate with devices, special device
files are used.
More information check out the man pages.
Computer Vision & Image
John Hulskamp
processing
E-mail:
john@hulskamp.com.au
Consultant
john@hulskamp.com.au 325
Introduction
Introducing the new subject 31049 Computer
Vision & Image Processing
Guest Lecturer with previous experience in

teaching & research in the area
Osteons
Compact bone is comprised of many units called osteons: they consist of a central canal surrounded by closely packed
concentric layers called lamallae.
This is an image of some osteons, specimen is from a 32yo male. Image is a ~2.8x3.5mm portion of a contact micro-
radiograph taken from a 100micrometre thick, un-embedded, hard-ground section. Black areas are voids, white = high
mineral density (maybe a couple of grains of carborundum can be seen).
Attribution: David Thomas, Dental Sciences, University of Melbourne
Near IR Imaging
Hot strip mill temperature measurement
Near IR Imaging (2)
Thermal Map
Attribution: C. Lampe: A Multi-Processor temperature profiling system for real time control in a hot strip
rolling mill M.Eng. Thesis RMIT 1995
Topics for Discussion Today
Subject objectives
Fundamental Issues
Applications
Towards image understanding
CV & IP Tools
A Simple Beginning
Conclusions
Subject objectives
adequate background knowledge about computer vision and image
processing
practical knowledge and skills about computer vision and image

processing tools
necessary knowledge to design and implement a prototype of a

computer vision application
Fundamental Issues
An imaging system
Fundamental Issues (2)
Resolution - the smallest feature size on your object that the imaging system
can distinguish
Field of view - the area of inspection that the camera can acquire
Working distance - the distance from the front of the camera lens to the object
under inspection
Sensor size - the size of a sensor's active area
Depth of field - the maximum object depth that remains in focus
Resolution
Resolution indicates the amount of object detail that the imaging system can
reproduce. You can determine the required resolution of your imaging system by
measuring in real-world units the size of the smallest feature you need to detect in the
image.
To make accurate measurements, a minimum of two pixels should represent the
smallest feature you want to detect in the digitized image. In the picture , the
narrowest vertical bar (w) should be at least two pixels wide in the image. This
information can assist to select the appropriate camera and lens for the imaging
application.
Sensor resolution is the number of columns and rows of CCD pixels in the camera sensor. To compute the
sensor resolution, you need to know the field of view (FOV).
The FOV is the area under inspection that the camera can acquire. The horizontal and vertical dimensions of the
inspection area determine the FOV. Make sure the FOV encloses the object you want to inspect.
Once you know the FOV, you can use the following equation to determine your required sensor resolution:
sensor resolution = (FOV/resolution) x 2

= (FOV/size of smallest feature) x 2
Determine the focal length of your lens.
A lens is primarily defined by its focal length. This picture illustrates the relationship between the focal length of the
lens, field of view, sensor size, and working distance which is the distance from the front of the lens to the object
under inspection.
focal length = sensor size x working distance / FOV
Lighting issues
One of the most important aspects of setting up your imaging environment is proper
illumination. Images acquired under proper lighting conditions make your image
processing software development easier and overall processing time faster. One
objective of lighting is to separate the feature or part you want to inspect from the
surrounding background by as many gray levels as possible. Another goal is to control
the light in the scene. Set up your lighting devices so that changes in ambient
illumination-such as sunlight changing with the weather or time of day-do not
compromise image analysis and processing.
Backlighting is another lighting technique that can help improve the performance of your vision system.
If you can solve your application by looking at only the shape of the object, you may want to create a
silhouette of the object by placing the light source behind the object you are imaging. By lighting the
object from behind, you create sharp contrasts which make finding edges and measuring distances fast
and easy. This picture shows a stamped metal part acquired in a setup using backlighting.
Perspective
Perspective errors occur when the camera axis is not perpendicular to the object under inspection. The figures show both an
ideal camera position (I.e. vertical) and a camera imaging an object from an angle.
Perspective and Distortion Errors
Try to position your camera perpendicular to the object under inspection to reduce perspective errors.
Integration constraints may prevent you from mounting the camera perpendicular to the scene. Under
these constraints, you can still take precise measurements by correcting the perspective errors with
spatial calibration techniques.
Examples of Vision Applications
Attribution: National Instruments IMAQ Vision Product Demonstration (www.ni.com/vision)
Examples:
Battery Clamp
Spark Plug Gap Measurement
Blister Pack Inspection
PCB Inspection
Examples of Vision Applications (2)
Battery Clamp
Spark Plug Gap Measurement
Blister Pack Inspection: Ensuring that blister packs contain the correct number
and type of pills before they reach pharmacies, ensuring the integrity of the product
and increase the yield of production by automating the inspection of blister pack
contents.
Acquire colour images of the blister packs. Use colour location to count the number of
green areas in the image. With colour location, you create a model or template that
represents the colours that you are searching. Then the machine vision application
searches for the model in each acquired image and calculates a score for each
match. The surface area of each pill in the pack must be at least 50% green to pass
inspection.
Blister Pack Inspection (contd)
PCB Inspection
To ensure that components are present and at the correct orientation on a PCB.
PCB Inspection (contd): Colour information simplifies a monochrome problem by improving contrast or
separation of the components from the background. Colour pattern matching can distinguish objects from the
background more efficiently than grayscale pattern matching.
This example uses rotation-invariant pattern matching because it can detect the components regardless of their
orientations. You can use the orientation information to determine the correct placement of orientation-sensitive
components, such as capacitors or diodes.
Towards image understanding
Computer Vision: making useful decisions about real physical objects and scenes based on sensed images
To get to that understanding we need to process images: hence Image Processing is a step towards this
understanding
Image Processing issues:

Image Statistics & Histograms
Image Enhancement
Image Restoration
Image Analysis: Edge Detection & Feature extraction
Representation & Description
Pattern Recognition
Histograms
The cumulative histogram of a grey-level image f(w,h) is a function
H(k) which provides the total number pixels (number of
occurrences) that have grey-level less than the value k.
H (k ) card { f ( w, h) | f ( w, h) k}
k [0, k max ]
( w, h) [(0,0), (W 1, H 1)]
Where card stands for the cardinality (i.e. number of pixels) of a

set.
The histogram of a grey-level image f(w,h) is a table h(k) which is
the discrete difference of the cumulative histogram. It provides the
total number pixels (number of occurrences) that have a specific
grey-level value k.
Attribution: www.khoral.com
h(k ) H (k ) H (k 1)
Histograms (2)
Histogram Equalisation
CV & IP Tools
NIH Image is a public domain image processing and analysis program for the Macintosh. It was developed
at the Research Services Branch (RSB) of the National Institute of Mental Health (NIMH), part of the
National Institutes of Health (NIH). A free PC version of Image, called Scion Image for Windows, is
available from Scion Corporation. Image can acquire, display, edit, enhance, analyse and animate images.
It reads and writes TIFF, PICT, PICS and MacPaint files, providing compatibility with many other
applications, including programs for scanning, processing, editing, publishing and analysing images. It
supports many standard image processing functions, including contrast enhancement, density profiling,
smoothing, sharpening, edge detection, median filtering, and spatial convolution with user defined
kernels.
Image can be used to measure area, mean, centroid, perimeter, etc. of user defined regions of interest. It
also performs automated particle analysis and provides tools for measuring path lengths and angles.
Spatial calibration is supported to provide real world area and length measurements. Density calibration
can be done against radiation or optical density standards using user specified units. Results can be
printed, exported to text files, or copied to the Clipboard.
CV & IP Tools (2)
Khoral Inc:It started out as Khoros about 10 years ago, for UNIX-based X-
systems, has become available for the Windows platform as well. Costs
money today!
Their online DIP course is very good:
http://www.khoral.com/contrib/contrib/dip2001/index.html
CV & IP Tools (3)
UTHSCSA ImageTool
UTHSCSA ImageTool (IT) is a free image processing and analysis program for
Microsoft Windows 9x, Windows ME or Windows NT. IT can acquire, display,
edit, analyse, process, compress, save and print gray scale and colour
images.IT can read and write over 22 common file formats including BMP,
PCX, TIF, GIF and JPEG. Image analysis functions include dimensional
(distance, angle, perimeter, area) and gray scale measurements (point, line
and area histogram with statistics). ImageTool supports standard image
processing functions such as contrast manipulation, sharpening, smoothing,
edge detection, median filtering and spatial convolutions with user-defined
convolution masks.
ImageTool was designed with an open architecture that provides
extensibility via a variety of plug-ins. Support for image acquisition using
either Adobe Photoshop plug-ins or Twain scanners is built-in. Custom
analysis and processing plug-ins can be developed using the software
development kit (SDK) provided (with source code). This approach makes it
possible to solve almost any data acquisition or analysis problem with IT.
CV & IP Tools (4)
Intel open source computer vision library OpenCV
CVIPtools: is a UNIX/Win32-based software package developed \ under the continuing direction of Dr.
Scott E Umbaugh One of the primary purposes of the CVIPtools development is to allow students, faculty,
and other researchers to explore the power of computer processing of digital images.
CVIPtools is a collection of computer imaging tools providing services to the users at three layers. At the
bottom level are the CVIPtools libraries (the application programming interface). Based on the CVIPtools
libraries are the cviptcl and cvipwish shells. The cviptcl shell is an extension of Tcl with additional CVIP
capabilities. With cviptcl, the user can either use the command line for interactive image processing, or
write cviptcl shell scripts for batch processing. The cvipwish shell is the extension of cviptcl with the added
functionality for building a graphical user interface (GUI) which allows even the casual computer users to
experiment with many of the sophisticated tools available to computer imaging specialists without the
need for any knowledge of computer programming.
Topics in Course
Image formation. Human vision. Computer vision.
Image representation. Analog and digital images. Common image and video formats. Image compression.
JPEG and MPEG.
Image acquisition. Image acquisition systems. Cameras and frame grabbers.
Image processing. Image enhancement. Convolution. Filtering. Edge detection. Texture analysis. Labelling.
Contour tracing. Image morphology. Image segmentation.
Image analysis. Feature extraction. Geometrical features. Hough transform.
Image sequences. Motion detection. Optical flow. Background subtraction. Feature tracking.
Pattern recognition. Object classification. Statistical, neural networks, symbolic classifiers.
Computer Vision. Model-based vision. Applications in industrial quality inspection, video surveillance,
robotics, medicine, multimedia .
A Simple Beginning
Paradigm for an image processing code:
Declarations
File In: Bring in image into Array I[r,c]
Processing on Array I[r,c] to produce

Array O[r,c]
File Out: Output Array O[r,c] as image
Conclusions
An overview of what is ahead for you in this
exciting field.
You might like to experiment with the above
simple code to attempt to gain the histogram
for an image, and try out histogram
equalisation
Data Structures - Graph
Graphs are simply a collection of nodes (points) and edges

connecting the nodes.
Typical notation lookslike this G = { N, E }.

G = the graph.
N = node set
E = edge set
Nodes represent items under consideration - can be anything.
Edges represent relationships between the items - can be

anything.
Edges can be undirected, meaning the relationship holds both ways
between nodes.
Edges can be directed, meaning the relationship is only one way.
Name Graph
Definition A set of nodes (data elements) connected by edges in an

arbitrary manner.
Std Functions None
Non-Std None
Functions
The most versatile data structure (linked lists, trees and
Notes heaps are special instances of graphs).
Standard Problems:
Graph Coloring: Coloring the nodes of a graph such that
adjacent nodes do not have the same color.
Traveling Salesman: Visiting each node in the graph exactly
once for the least cost (start and stop at the same node).
Maximum Flow: Determine the amount of flow through a
network.
THESE ARE ALL GRAPHS.

Graph Problems
There are literally thousands of graph problems, but we will focus

on three that are occur very commonly and show the diversity of
the graph structure:
The Traveling Salesman Problem.
Graph Coloring Problem.
Maximum Flow Problem.
At least one of these problems is solved by you every day without

you realizing it (until now).
The fact that the nodes and edges can represent anything means
that the graph structure is very versatile and virtually any problem
can be mapped to a graph problem.
Example Graph Problem - Puzzle
This is an old puzzle and has many variants: A man is returning

home from market with a wolf, bag of corn, and goose. He has to
cross a lttle river on the way and the only way is to use a little
boat. The boats holds him and one other item.
He cannot leave the wolf and goose alone, as the wolf eats the goose.
He cannot leave the corn and goose alone as the goose eats the corn.
He can leave the corn and wolf alone.
How does he get everything across the river and bring everything
home (uneaten)?
Build a graph:
N = the set of possible arrangements of man, wolf, goose, corn, and
river.
E = Possible transitions due to one boat trip.
Example Graph Problem - Puzzle
mwgc| wgc| m
mwg|c wg|mc
mwc| g wc| mg
mgc| w gc| mw
mc| wg c| mwg
mg| wc g| mwc
mw|gc w|mgc
m| wgc | mwgc
Example Graph Problem - Puzzle Solved
mwgc| wgc| m
mwg|c wg|mc
mwc| g wc| mg
mgc| w gc| mw
mc| wg c| mwg
mg| wc g| mwc
mw|gc w|mgc
m| wgc | mwgc
Graph Problems
There are literally thousands of graph problems, but we will focus on three
that are occur very commonly and show the diversity of the graph
structure:
The Traveling Salesman Problem.
Graph Coloring Problem.
Maximum Flow Problem.
Each problem has a decision form and an optimization form. The decision
form asks "Can we do it?" and the optimization form asks "How well can
we do it?"
At least one of these problems is solved by you every day without you
realizing it (until now).
The fact that the nodes and edges can represent anything means that the
graph structure is very versatile and virtually any problem can be mapped
to a graph problem.
Graph Problems - Traveling Salesman
Description: Given a graph, G = {N, E}, where

N = a set of cities.
E = travel routes between the cities, each having a cost associated
with it.
One special node, s.
You must begin at city sand travel to each of the other cities exactly
once and then return to city s. Thus you make a complete cycle of all
cities in the graph.
Decision form of the problem: Can a route be found where the

total cost of the trip is less than X? (Answer is yes or no).
Optimization form of the problem: What is the absolute lowest

cost?
Graph Problems - Graph Coloring

N = a set of nodes.
E = edges between the nodes.
The object is to color the graph such that no nodes connecte by an
edge have the same color.
Decision form of the problem: Can the graph be colored with X or

less colors? (Answer is yes or no).
Optimization form of the problem: What is the fewest number of

colors required to color the graph?
Graph Problems - Maximum Flow

N = a set of nodes.
E = edges representing pipes, each assigned a given capacity.
Two special nodes. Node s is a source node that can potentially spit
out an infinite amount of material. Node f is a sink node that can
potentially absorb an infinite amount of material.
The object is to determine the maximum amount of material that can
flow through the network for the source to the sink.
Decision form of the problem: Can X amount of material be

pushed through the network from the source to the sink?
(Answer is yes or no).
Optimization form of the problem: What is the maximum amount

of material that can flow through the material from the source to
the sink?
Cost of Graph Problems
Name Description Cost * Comments

Traveling Does a route exist O(n!) Hard to solve, easy to verify.
Salesman with cost less than
Decision X?
Traveling What is the least O(n!) Hard to solve, hard to verify.
Salesman cost route.
Optimization
Graph Coloring Can a graph be O(n!) Hard to solve, easy to verify.
Decision colored properly
using X colors?
Graph Coloring What is the least O(n!) Hard to solve, hard to verify.
Optimization number of colrs
required to properly
color a graph?
Maximum Flow What is the most O(n3) Polynomial solution time means easy to solve,
material that can be easy to verify.
pushed through a
network?
Data Structures - Tree
Name Tree
Definition A graph with directed edges connecting parent to child such

that there is exactly one node with no parents and all other
nodes have exactly one parent.
Std Functions None
Non-Std None
Functions
The first element in the tree is the root node, which has no
Notes parents, and from which all others can be reached.
Nodes with no children are "leaf" nodes.
If nodes a and b are connected by an edge, then:
a is a child of b if b is closer to the root than a.
a is a parent of b if a is closer to the root than b
Useful in making decisions and categorizing data.

Data Structures - Tree
ROOT - has no parent,

only one in the tree.
LEAVES - have no children.

Data Structures - Heap
Name Heap
Definition A tree in which a parent node has a value larger than all its
children.
Std Functions Heap(a, H) Add new node a to heap H.
Unheap(H) Remove the root element from heap H and re-
establish the heap.
Non-Std None
Functions
Flexible data structure useful for sorting elements as they
Notes arrive. This allows sorting on lists whoses size change
constantly.
Used in priority queues or other situations where

maintaining and accessing a maximum element is important.
THESE ARE TREES (ABOVE). ARE THEY HEAPS?
THESE ARE NOT TREES (ABOVE). ARE THEY HEAPS?

Data Structures
Topic #11
Todays Agenda
Complete our discussion of trees
Learn about heaps
walk through the deletion algorithms for:
AVL
2-3, 2-3-4
Learn about graphs
Heaps
A heap is a data structure similar to a binary
search tree.
However, heaps are not sorted as binary
search trees are.
And, heaps are always complete binary trees.
Therefore, we always know what the
maximum size of a heap is.
Heaps
Unlike a binary search tree, the value of
each node in a heap is greater than or
equal to the value in each of its children.
In addition, there is no relationship
between the values of the children; you
don't know which child contains the
larger value.
Heaps are used to implement priority
queues.
Heaps
A priority queue is an Abstract Data Type!
Which, can be implemented using heaps.
Think of a To-Do lists; each item has a
priority value which reflects the urgency
with which each item needed to be
addressed.
Heaps
By preparing a priority queue, we can
determine which item is the next highest
priority.
A priority queue maintains items sorted in
descending order of their priority value --
so that the item with the highest priority
value is always at the beginning of the list.
Heaps
Priority Queue ADT operations can be
implemented using heaps...
which is a weaker binary tree but sufficient
for the efficient performance of priority
queue operations.
Let's look at heap: 10
9 6
3 2 5
Heaps
To remove an item from a heap, we remove the
largest item (or the item with the highest priority).
Because the value of every node is greater than or
equal to that of either of its children, the largest
value must be the root of the tree.
A remove operation is simply to remove the item
at the root and return it to the calling routine.
Heaps
Once you have removed the largest value,
you are left with two disjoint heaps:
Therefore, you need to transform the nodes
Move the last node and place it in the root
Then take that value and trickle it down the tree
until it reaches a node in which it will not be out
of place. 5 9
10
9 6 5 6
9 6
3 2 3 2
3 2 5
Step 1 Step 2
Heaps
To insert an item, we use just the opposite
strategy.
We insert at the bottom of the tree and trickle the
number upward to be in the proper place.
With insert, the number of swaps cannot exceed the
height of the tree -- so that is the worst case!
Which, since we are dealing with a binary tree, this is
always approximately log2(N) which is very efficient.
Heaps
9 9 9
5 6 5 6 5 15
3 2 3 2 15 3 2 6
Step 1:insert 15 Step 2 Step 3
15
5 9
3 2 6
Step 5
Heaps
The real advantage of a heap is that it is
always balanced.
It makes a heap more efficient for
implementing a priority queue than a binary
search tree because the operations that keep a
binary search tree balanced are far more
complex than the heap operations.
However, heaps are not useful if you want to
try to traverse a heap in sorted order -- or
retrieve a particular item.
Heapsort
A heapsort uses a heap to sort a list of
items that are not in any particular order.
The first step of the algorithm transforms
the array into a heap.
We do this by inserting the numbers into
the heap and having them trickle up...one
number at a time.
Heapsort
A better approach is to put all of the
numbers in a binary tree -- in the order you
received them.
Then, perform the algorithm we used to
adjust the heap after deleting an item.
This will cause the smaller numbers to
trickle down to the bottom.
Heapsort
6 6
3 5 3 5
9 2 10 9 2 10
Step 1 Step 2: compare 6 with 3 & 5;
no swaps
6
9 5
3 2 10
Step 3: compare 3 with 9 and 2; swap 3 and 9;

this means that 3 & 2 are now in their correct
sorted locations
Heapsort
6
9 10
3 2 5
Step 4: compare 5 with 10; swap;
this means that 5 is now in its correct
sorted location; Level 3 is sorted.
10
9 6
3 2 5
Pass 2: start again. Compare 6 with 3 and 10; swap
6 and 10. 3 and 6 are now in the correc t sorted locations;
Level 2 is sorted.
Deletion Algorithms
In class, take 5 minutes and practice creating
the following trees:
insert: 30, 50, 70, 10, 20, 60, 15, 25, 85
create: BST, AVL, 2-3, 2-3-4, red-black
create: a heap
now, delete a leaf in each tree
now, delete an internal node
Moving from Trees to Graphs
Trees are useful when there is an inherent
hierarchical relationship between our data
sorting data by a key can build such a relationship
But, not all problems are so simple
Maybe there are complex relationships
between nodes ... not just hierarchical!
this is where graphs become important
Graphs
Graphs can be used as data structures and as
the last ADT we will learn about;
to represent how data can be related to one
another...setting up an inherent structure.
Graphs consist of vertices (nodes) and edges
which connect the vertices.
A path is a sequence of edges that can be
taken to get from one vertex to another.
Graphs
Paths may pass through the same vertex more
than once but simple paths may not.
A cycle is a path that starts and ends at the
same vertex but does not pass through other
vertices more than once.
Graphs are considered to be connected if
there is a path between every pair of vertices.
Graphs
A graph is complete if there is an edge
between every pair of vertices.
Edges can have labels - or numeric values -
which create a weighted graph.
Weights can label the distances between
cities.
connected disconnected complete

graph graph graph
Graphs
ADT Graph operations might include:
create an empty graph
determine if the graph is empty
insert a vertex
insert an edge between two vertices
delete a vertex
delete an edge between two vertices
retrieve the value of the data at a vertex
replace the data at a particular vertex
determine if an edge is between vertices
Graphs
One common way of implementing a graph is
to use an adjacency list.
Using this approach, imagine that the vertices
are numbered 1,2, thru N.
This type of implementation consists of N
linked lists.
There is a node in the ith linked list for the
vertex j if and only if there is an edge from
vertex i to vertex j.
Graphs
9
1 3 6
2 7
3 7
8 4 5
5 6
6 4 8
4 7
6
8 3 9
9
5
3
1
7 2
A directed graph
Graphs
Two common operations are to find an edge
between two vertices and to find all vertices
adjacent to a given vertex.
Using an adjacency list to determine whether
there is an edge from one vertex to another,
we must traverse the linked list associated
with one of the vertices to determine
whether the other vertex is present.
Graphs
To determine all vertices adjacent to a given
vertex, we only need to traverse the linked
list associated with the specified vertex.
What about traversing a graph?
Graph-traversal starts at a specified vertex and
does not stop until it has visited all of the vertices
that it can reach.
It visits all vertices that have a path between the
specified vertex and the next.
Graphs
Notice how different this is than tree
traversal.
with tree traversal, we always visit all of the nodes
in the tree
with graph traversal we do not necessarily visit all
of the vertices in the graph unless the graph is
connected.
If a graph is not connected, then a graph traversal
that begins at a vertex will only visit a subset of the
graphs vertices.
Graphs
There are two basic graph-traversal
algorithms that we will discuss.
These algorithms visit the vertices in
different orders,
but if they both start at the same vertex,
they will visit the same set of vertices.
Depth first search
Breadth first search
Graphs
Depth-First Search
This algorithm starts at a specified vertex and
goes as deep into the graph as it can before
backtracking.
This means that after visiting the starting vertex,
it goes to an unvisited vertex that is adjacent to
the one just visited.
The algorithm continues from this way until it
has gotten as far as possible before returning to
visit the next unvisited vertex adjacent to the
starting place.
Graphs
Depth-First Search
This traversal algorithm does not completely
specify the order in which you should visit the
vertices adjacent to a particular vertex.
One possibility is to visit the vertices in sorted
order.
This only works - of course - when our nodes in
each linked list of an adjacency list are in sorted
order.
Graphs
b
c
Depth-First Search a
e
h
i g
f
Because the graph is connected, DFS will visit
every vertex. In fact, the traversal could visit the
vertices in this order:
a bcdgefhi
Notice a stack of vertices can be used to
implement this approach -- where the last one
visited is
Graphs
Breadth-First Search
This starts at a specified vertex and visits every vertex
adjacent to that vertex before embarking from any of
those vertices to the next set.
It does not embark from any of these vertices adjacent
to the starting vertex until it has visited all possible
vertices adjacent.
Notice that this is a first visited -- first explored strategy.
Therefore, it should be obvious that a queue of vertices
can be used
Graphs
b
c
Breadth-First Search a
e
h
i g
The the above graph, starting at vertex a we

could traverse the vertices in the following
order:
abfi ce g d h
FUZZY LOGIC
Shane Warren
Brittney Ballard
OVERVIEW
What is Fuzzy Logic?
Where did it begin?
Fuzzy Logic vs. Neural Networks
Fuzzy Logic in Control Systems
Fuzzy Logic in Other Fields
Future
WHAT IS FUZZY LOGIC?
Definition of fuzzy
Fuzzy not clear, distinct, or precise; blurred
Definition of fuzzy logic

A form of knowledge representation suitable for notions
that cannot be defined precisely, but which depend upon
their contexts.
TRADITIONAL REPRESENTATION OF
LOGIC
Slow Fast
Speed = 0 Speed = 1
bool speed;
get the speed
if ( speed == 0) {
// speed is slow
}
else {
// speed is fast
}
FUZZY LOGIC REPRESENTATION
Slowest
For every problem
[ 0.0 0.25 ]
must represent in
terms of fuzzy sets.
Slow
What are fuzzy sets? [ 0.25 0.50 ]
Fast
[ 0.50 0.75 ]
Fastest
[ 0.75 1.00 ]
FUZZY LOGIC REPRESENTATION
CONT.
Slowest Slow Fast Fastest

float speed;
get the speed
if ((speed >= 0.0)&&(speed < 0.25)) {
// speed is slowest
}
else if ((speed >= 0.25)&&(speed < 0.5))
{
// speed is slow
}
else if ((speed >= 0.5)&&(speed < 0.75))
{
// speed is fast
}
else // speed >= 0.75 && speed < 1.0
{
// speed is fastest
}
ORIGINS OF FUZZY LOGIC
Traces back to Ancient Greece
Lotfi Asker Zadeh ( 1965 )

First to publish ideas of fuzzy logic.
Professor Toshire Terano ( 1972 )

Organized the world's first working group on fuzzy
systems.
F.L. Smidth & Co. ( 1980 )

First to market fuzzy expert systems.
FUZZY LOGIC VS. NEURAL NETWORKS
How does a Neural Network work?
Both model the human brain.

Fuzzy Logic
Neural Networks
Both used to create behavioral
systems.
FUZZY LOGIC IN CONTROL SYSTEMS
Fuzzy Logic provides a more efficient and

resourceful way to solve Control Systems.
Some Examples
Temperature Controller
Anti Lock Break System ( ABS )

TEMPERATURE CONTROLLER
The problem
Change the speed of a heater fan, based off the room
temperature and humidity.
A temperature control system has four settings
Cold, Cool, Warm, and Hot
Humidity can be defined by:
Low, Medium, and High
Using this we can define
the fuzzy set.
BENEFITS OF USING FUZZY LOGIC
ANTI LOCK BREAK SYSTEM ( ABS )
Nonlinear and dynamic in nature
Inputs for Intel Fuzzy ABS are derived from
Brake
4 WD
Feedback
Wheel speed
Ignition
Outputs
Pulsewidth
Error lamp
FUZZY LOGIC IN OTHER FIELDS
Business
Hybrid Modeling
Expert Systems
CONCLUSION
Fuzzy logic provides an alternative way to

represent linguistic and subjective attributes of the
real world in computing.
It is able to be applied to control systems and other

applications in order to improve the efficiency and
simplicity of the design process.
Chapter 19
Searching, Sorting and Big O
Java How to Program, 9/e
Copyright 1992-2012 by Pearson Education, Inc. All

Rights Reserved.
Copyright 1992-2012 by Pearson
Education, Inc. All Rights Reserved.
19.1 Introduction
Searching data involves determining whether a value
(referred to as the search key) is present in the data and, if
so, finding its location.
Two popular search algorithms are the simple linear search and the
faster but more complex binary search.
Sorting places data in ascending or descending order, based
on one or more sort keys.
This chapter introduces two simple sorting algorithms, the selection
sort and the insertion sort, along with the more efficient but more
complex merge sort.
Figure 19.1 summarizes the searching and sorting
algorithms discussed in the examples and exercises of this
book.
19.2 Searching Algorithms
The next two subsections discuss two common

search algorithmsone that is easy to program
yet relatively inefficient and one that is
relatively efficient but more complex and
difficult to program.

19.2.1 Linear Search
The linear search algorithm searches each element in an
array sequentially.
If the search key does not match an element in the array, the
algorithm tests each element, and when the end of the array is
reached, informs the user that the search key is not present.
If the search key is in the array, the algorithm tests each element
until it finds one that matches the search key and returns the index
of that element.
If there are duplicate values in the array, linear search
returns the index of the first element in the array that
matches the search key.
Arrays static method toString returna a String
representation of an array.
19.2.1 Linear Search (cont.)
Searching algorithms all accomplish the same

goalfinding an element that matches a given
search key, if such an element does, in fact,
exist.
The major difference is the amount of effort
they require to complete the search.
Big O notation indicates the worst-case run
time for an algorithmthat is, how hard an
algorithm may have to work to solve a
problem. Copyright 1992-2012 by Pearson
If an algorithm is completely independent of the number of

elements in the array, it is said to have a constant run time,
which is represented in Big O notation as O(1).
An algorithm that is O(1) does not necessarily require only one
comparison.
O(1) just means that the number of comparisons is constantit
does not grow as the size of the array increases.
An algorithm that requires a total of n 1 comparisons is
said to be O(n).
An O(n) algorithm is referred to as having a linear run time.
O(n) is often pronounced on the order of n or simply order n.

Constant factors are omitted in Big O notation.
Big O is concerned with how an algorithms run time grows in
relation to the number of items processed.
O(n2) is referred to as quadratic run time and pronounced
on the order of n-squared or more simply order n-squared.
When n is small, O(n2) algorithms (running on todays computers) will
not noticeably affect performance.
But as n grows, youll start to notice the performance degradation.
An O(n2) algorithm running on a million-element array would require
a trillion operations (where each could actually require several
machine instructions to execute).
A billion-element array would require a quintillion operations.
Youll also see algorithms with more favorable Big O measures.

The linear search algorithm runs in O(n) time.
The worst case in this algorithm is that every element must be
checked to determine whether the search item exists in the array.
If the size of the array is doubled, the number of comparisons that
the algorithm must perform is also doubled.
Linear search can provide outstanding performance if the
element matching the search key happens to be at or near
the front of the array.
We seek algorithms that perform well, on average, across all
searches, including those where the element matching the search
key is near the end of the array.
If a program needs to perform many searches on large
arrays, its better to implement a more efficient algorithm,
such as the binary search.

19.2.1 Binary Search
The binary search algorithm is more efficient than linear
search, but it requires that the array be sorted.
The first iteration tests the middle element in the array. If this
matches the search key, the algorithm ends.
If the search key is less than the middle element, the algorithm
continues with only the first half of the array.
If the search key is greater than the middle element, the algorithm
continues with only the second half.
Each iteration tests the middle value of the remaining portion of the
array.
If the search key does not match the element, the algorithm
eliminates half of the remaining elements.
The algorithm ends by either finding an element that matches the
search key or reducing the subarray to zero size.
19.2.2 Binary Search
The sort method is a static method of

class Arrays that sorts the elements in an
array in ascending order by default; an
overloaded version of this method allows you
to change the sorting order.

19.2.2 Binary Search (cont.)
In the worst-case scenario, searching a sorted array of 1023
elements takes only 10 comparisons when using a binary
search.
The number 1023 (210 1) is divided by 2 only 10 times to get the
value 0, which indicates that there are no more elements to test.
Dividing by 2 is equivalent to one comparison in the binary search
algorithm.
Thus, an array of 1,048,575 (220 1) elements takes a
maximum of 20 comparisons to find the key, and an array of
over one billion elements takes a maximum of 30
comparisons to find the key.
A difference between an average of 500 million comparisons for the
linear search and a maximum of only 30 comparisons for the binary
search!

19.2.2 Binary Search (cont.)
The maximum number of comparisons needed

for the binary search of any sorted array is the
exponent of the first power of 2 greater than
the number of elements in the array, which is
represented as log2 n.
All logarithms grow at roughly the same rate,
so in big O notation the base can be omitted.
This results in a big O of O(log n) for a binary
search, which is also known as logarithmic run
time. Copyright 1992-2012 by Pearson
19.3 Sorting Algorithms
Sorting data (i.e., placing the data into some particular order,
such as ascending or descending) is one of the most important
computing applications.
An important item to understand about sorting is that the end
resultthe sorted arraywill be the same no matter which
algorithm you use to sort the array.
The choice of algorithm affects only the run time and memory
use of the program.
The rest of this chapter introduces three common sorting
algorithms.
The first twoselection sort and insertion sortare easy to program
but inefficient.
The last algorithmmerge sortis much faster than selection sort and
insertion sort but harder to program.

19.3.1 Selection Sort
Selection sort
simple, but inefficient, sorting algorithm
Its first iteration selects the smallest element in the array and swaps it
with the first element.
The second iteration selects the second-smallest item (which is the
smallest item of the remaining elements) and swaps it with the second
element.
The algorithm continues until the last iteration selects the second-
largest element and swaps it with the second-to-last index, leaving the
largest element in the last index.
After the ith iteration, the smallest i items of the array will be sorted
into increasing order in the first i elements of the array.
After the first iteration, the smallest element is in the first position.
After the second iteration, the two smallest elements are in order in the
first two positions, etc.
The selection sort algorithm runs in O(n2) time.
19.3.2 Insertion Sort
Insertion sort
another simple, but inefficient, sorting algorithm
The first iteration takes the second element in
the array and, if its less than the first element,
swaps it with the first element.
The second iteration looks at the third element
and inserts it into the correct position with
respect to the first two, so all three elements
are in order.
At the ith iteration of this algorithm, the first i
elements in the original array will be sorted.
19.3.3 Merge Sort
Merge sort
efficient sorting algorithm
conceptually more complex than selection sort and insertion sort
Sorts an array by splitting it into two equal-sized subarrays,
sorting each subarray, then merging them into one larger
array.
The implementation of merge sort in this example is
recursive.
The base case is an array with one element, which is, of course,
sorted, so the merge sort immediately returns in this case.
The recursion step splits the array into two approximately equal
pieces, recursively sorts them, then merges the two sorted arrays
into one larger, sorted array.
Merge sort has an efficiency of O(n log n).
CS6382 Theory of Computation
Ding-Zhu Du
Office: ECSS 3-611, M 3:15-4:30
Lecture: ECSS 2.311, MW 12:30-1:45
Part I
Theory of Deterministic
Computation
Lecture 1
Deterministic Turing Machine (DTM)
tape
head
Finite Control
a l p h a B e
The tape has the left end but infinite to the

right. It is divided into cells. Each cell contains
a symbol in an alphabet . There exists a
special symbol B which represents the empty
cell.
a
The head scans at a cell on the tape and can

read, erase, and write a symbol on the cell. In
each move, the head can move to the right
cell or to the left cell (or stay in the same cell).
The finite control has finitely many states
which form a set Q. For each move, the state is
changed according to the evaluation of a
transition function
: Q x Q x x {R, L}.
a b
q p
(q, a) = (p, b, L) means that if the head reads

symbol a and the finite control is in the state
q, then the next state should be p, the symbol
a should be changed to b, and the head moves
one cell to the left.
a b
q p
(q, a) = (p, b, R) means that if the head reads

q, then the next state should be p, the symbol
a should be changed to b, and the head moves
one cell to the right.
s
There are some special states: an initial state s

and an final states h.
Initially, the DTM is in the initial state and the
head scans the leftmost cell. The tape holds an
input string.
x
When the DTM is in the final state, the DTM

stops. An input string x is accepted by the DTM
if the DTM reaches the final state h.
Otherwise, the input string is rejected.
The DTM can be represented by
M = (Q, , , , s)
where is the alphabet of input symbols.
The set of all strings accepted by a DTM M is
denoted by L(M). We also say that the
language L(M) is accepted by M.
The transition diagram of a DTM is an alternative
way to represent the DTM.
For M = (Q, , , , s), the transition diagram of M is a
symbol-labeled digraph G=(V, E) satisfying the
following:
V = Q (s = ,h= )
E={p q | (p, a) = (q, b, D)}.

a/b,D
1/1,R 0/0,R; 1/1,R
0/0,R 0/0,R B/B,R

s p q h
1/1,R
M=(Q, , , , s) where Q = {s, p, q, h},

= {0, 1}, = {0, 1, B}.
0 1 B
s (p, 0, R) (s, 1, R) -
p (q, 0, R) (s, 1, R) -
q (q, 0, R) (q, 1, R) (h, B, R)
L(M) = (0+1)*00(0+1)*.
Theorem. Every regular set can be
accepted by a DTM.
Proof.
Every regular set can be accepted a
deterministic finite automata (DFA).
Every DFA can be simulated by a DTM.
Review on Regular Set
Regular sets on an alphabet is defined
recursively as follows
(1) The empty set is a regular set.
(2) For every symbol a in , {a} is a
regular set.
(3) If A and B are regular sets, then
A B, A U B, and A* are all regular
sets.
Review on DFA
tape
a b c d e f
head
finite control
The tape is divided into cells. Each cell contains
a symbol in an alphabet .
The head scans at a cell on the tape and can

read symbol from the cell. It can also move
from left to right, one cell per move.
The finite control has finitely many states
which form a set Q. For each move, the state
is changed according to the evaluation of a
function : Q x Q. If the head reads
q, then the next state is p = (q, a).
There are some special states: an initial state s
and some final states which form a set F.
The DFA can be represented by M = (Q,
, , s, F).
Initially, the DFA is in the initial state and the
head scans the leftmost cell. The tape holds
an input string x. When the head moves off
the tape, the DFA stops. An input string is
accepted by the DFA if the DFA stops in a final
state. Otherwise, the input string is rejected.
Simulate DFA by DTM
Given a DFA M = (Q, , , s, F), we can
construct a DTM M = (Q, , , , s) to
simulate M as follows:
Q = Q U {h}, = U {B},
If (q, a) = p, then (q, a) = (p, a, R). (q, B)

= (h, B, R) for q in F.
1/1,R 0/0,R; 1/1,R
0/0,R 0/0,R B/B,R

s p q h
1/1,R
1 0, 1
0 0
s p q
1
L(M) = (0+1)*00(0+1)*.
Turing acceptable languages
Regular
languages
Why DTM can accept more languages than
DFA?
Because
The head can move in two directions. (No!)
The head can erase. (No!)
The head can write and move in two directions.
(Yes!)
Examples of DTM
Configurat ion (q, x1 ... xi 1 xixi 1... xn )

represents DTM at an time that
the final control is in state q, the tape
holds string x1...xn, and the head reads xi.
If (q,a ) = ( p,b,R), then writ e
(q,x a cy ) ( p,xbc y ).
If (q,a ) = ( p,b,L), then writ e
(q,xca y ) ( p,xcby ).
Example 1. Construct DTM
starting from configurat ion
( s, x1x 2 ... xn) and ending with
(h, Bx1... xn B).
(s, 0110B)
(q0, B110B)
(q1, B010B)
(q1, B010B)
(q0, B011B)
(h, B0110B)
Remark
We may assume that every

DTM has initial configurat ion
( s, Bx 1 xn B).
Turing-acceptable
Consider DTM M = (Q, , , , s)
An input string x is accepted
by M if ( s, Bx B ) * (h, ).
L( M ) { x | x is accepted by M }
{ww R| w (0+1)*} is Turing-acceptable.
(s, B0110B) (q, B0110B) (q0, B011BB)

* (q0, B011B) (p0, B011B) (ok, BB11B)
* (ok, B11B) (q, B11B) (q1, B1BB)
(q1, B1B) (p1, B1B) (ok, BBB)
(q, BBB) (h, BBB)
?? Could we do (ok, BBB) (h, BBB) ?

R
L= {ww | w in (0+1)*}
Turing-Computable Functions
A total function f: * * is Turing-
computable if there exists a DTM M such that
for every x in *,
(s, BxB) * (h, Bf(x)B).
A partial f: * is Turing-computable if
there exists a DTM M such that L(M)= and
for every x in ,
(s, BxB) * (h, Bf(x)B).
The following function f is Turing-computable:
R
f(x) = w, if x = ww ;
, otherwise
(s, B0110B) (q, B0110B) (q0, B011BB)

* (q0, B011B) (p0, B011B) (ok, B011B)
* (ok, B011B) (q, B011B) (q1, B01BB)
(q1, B01B) (p1, B01B) (ok, B01B)
(q, B01B) (r, B01B) * (r, B01B)
(o, B01B) * (o, B01B) (k, B01BB)
(h, B01B)
f(x) = w if x = ww ; , otherwise
R
Turing-decidable
A language A is Turing-decidable if its characteristic
function is Turing-computable.
1, if x A
(x) = {
A 0, otherwise
{ ww R| w (0+1)*} is Turing-decidable.
(s, B0110B) (q, B0110B) (q0, B011BB)

* (q0, B011B) (p0, B011B) (ok, B$11B)
* (ok, B$11B) (q, B$11B) (q1, B$1BB)
(q1, B$1B) (p1, B$1B) (ok, B$$B)
(q, B$$B) (r, B$BB) * (r, BBB)
(o, BBB) * (h, B1B)
Theorem
A language A is Turing-acceptable iff there
exists a total Turing-computable function f
such that A = { f(x) | x (0+1)*}.
If we look at each natural number as a 0-1
string, then f can be also a total Turing-
computable function defined on N, the set of
all natural numbers, that is,
A = { f(1), f(2), f(3), }
Therefore, Turing-acceptable is also called
recursively enumerable (r.e.).
Theorem
A language A is Turing-decidable iff A and its
complement are Turing-acceptable.
Proof. Suppose L(M) = A and L(M) = .

Construct M* to simulate M and M
simultaneously
Turing-decidable
(recursive)
Turing-acceptable
(r.e.)
regular
Various TMs
Allow the head not move
Theorem. If the head is allowed to stay at the
cell in each move, then every function
computed by the DTM is still Turing-
computable.
Proof. Consider DTM M=(Q,,,,s) where
: Q x Q x x {R, L, H} and H means
that the head stays at the current cell. We
construct M=(Q U Q, , , ,s) as follows:
Q = {q | q Q}
For q Q,
(q, a) = (p, b, R) if (q, a) = (p, b, R)
(q, a) = (p, b, L) if (q, a) = (p, b, L)
(q, a) = (p, b, R) if (q, a) = (p, b, H)
For p Q,
(p, a) = (p, a, L).
M and M compute the same function.

Corollary. A language is accepted by a DTM,
which allows the head not to move, iff it is
Turing-acceptable.
Why this is a corollary?
Because every language accepted by a DTM is
the definition domain of a function
computable by a DTM of the same type.
Corollary. A language is decided by a DTM, which
allows the head not to move, iff it is Turing-
decidable.
Two-way DTM
Theorem. Every function computed by a two-
way DTM is Turing-computable.
$
Consider a two-way DTM M=(Q, , , ,s).
Construct a DTM M = (Q U Q,,,,s) to
simulate M as follows:
Q={q | q Q}
={(a, b) | a, b } U { (B, $) }
={(a, B) | a }
For q Q,
(q, $) = (q,$,R)
(q, (a, c)) = (p,(b,c),D) if (q,a)=(p,b,D)
For q Q,
(q, $) = (q, $, R)
(q,(c,a)) = (p,(c,b),R) if (q,a)=(p,b,L)
(q,(c,a)) = (p,(c,b),L) if (q,a)=(p,b,R)
(q,(c,a)) = (p,(c,b),H) if (q,a)=(p,b,H)
Multi-tape DTM
Input tape
(read only)
Storage
tapes
Output tape
(possibly, write only)

Theorem. A function can be computed by a
multitape DTM iff it isTuring-computable.
Proof.
tape
X head
tape
X head
tape
X head
To simulate a move of the multitape DTM, the one-tape
DTM needs two trips:
Trip 1: read all symbols at heads.
Trip 2: erase and write at cells scaned by heads.
Questions:
How many moves does one-tape DTM needs to
simulate t moves of a multitape DTM?
How many states does one-tape DTM needs to
simulate a multitape DTM?
Church-Turing Thesis
Any reasonably computable function
is a Turing-computable function.
Theorem. A language A is Turing-decidable iff both A
and its complement A are Turing-acceptable.
Proof. The forward direction is easy.
For the backward direction, suppose one-tape DTMs
M and M accept A and A respectively. Construct 4-
tape DTM M* as follows:
Use a storage tape to simulate M
and another storage tape to simulate M.
M* halts iff M or M halts.
If M halts, then M* outputs 1.
If M halts, then M* outputs 0.
School of Continuing Studies
CS 351: Introduction to
Computer Graphics
CS 351
What is Computer Graphics?
Creation, Manipulation, and Storage of
geometric objects (modeling) and their
images (rendering)
Display those images on screens or
hardcopy devices
Image processing
Others: GUI, Haptics, Displays (VR)...
What drives computer graphics?
Movie Industry
Leaders in quality and artistry
Not slaves to conceptual purity
Big budgets and tight schedules
Reminder that there is more to
CG than technology
Hey, How'd they do that?
Defines our expectations
Slide information from Leonard

McMillian's slides
Game Industry
The newest driving force in CG
Why? Volume and Profit
This is why we have commodity GPUs
Focus on interactivity
Cost effective solutions
Avoiding computating and other tricks
Games drive the baseline

McMillian's slides
Medical Imaging and Scientific Visualization
Tools for teaching and diagnosis
No cheating or tricks allowed
New data representations and modalities
Drive issues of precision and correctness
Focus on presentation and interpretation of
data
Construction of models from acquired data
Nanomanipulator, UNC
Joe Kniss, Utah Gordon Kindelman, Ut
Computer Aided Design
Mechanical, Electronic, Architecture,...
Drives the high end of the hardware market
Integration of computing and display resources
Reduced design cyles == faster systems, sooner
ProEngineer, www.ptc.com
Graphic User Interfaces (GUI)
www.webpagesthatsuck.com

McMillian's slides
What is Computer Graphics?
Look at 5 areas
Hardware
Rendering
Interaction
Modeling
Scientific Visualization
Slide information from

Hardware: Amazing Changes
Fundamental architecture shift
Dual computing engines:
CPU and GPU
More in GPU than CPU
Fast, cheap GPUs
~$300
Cheap memory
Displays at low cost
How many monitors do you have/use?
Wired -> Unwired
World of Access
Hardware... some not so good
Devices
3D displays
Etc
Hardware
How old is Nvidia
How big is Nvidia
QED
Rendering
Many think/thought graphics synonymous
with rendering
Well researched
Working on second and third order effects
Fundamentals largely in place
Rendering
Major areas:
Ealiest: PhotoRealism
Recent: Non-Photorealistic Graphics (NPR)
Recent: Image-based Rendering (IBR)
Rendering
Ray Tracing has become practical
Extremely high quality images
Photorealism, animation, special effects
Accurate rendering, not just pretty
Rendering Realism
Morning Evening
a preetham, e
Rendering Realism
Cornel Measurement Lab

Rendering Realism
Real Synthetic
Shirley, et. al., cornell

Is this real?
m fajaro, usc
Terrain Modeling:
Snow and Trees Added
s premoze, et.al., utah

Growth Models
o deusson,
Rendering/Modeling Hair
QuickTime and a QuickTime and a

Photo decompressor Video decompressor
are needed to see this picture. are needed to see this picture.
http://www.rhythm.com/~ivan/hairRender.html
Humans
Final Fantasy (Sony) Jensen et al.

Is Photorealism Everything?
Is Photorealism Everything?
Non-Photorealistic Rendering
b gooch, et.al., utah

Tone Shading
a gooch, et. al., utah

NonPhotorealistic Rendering
Image Based Rendering
Model light field
Do not have to model geometry
Good for complex 3D scenes
Can leave holes where no data is available
3D Scene Capture
Fuchs et.al., UNC UNC and UVA

3D Scene Recreation
Faugeras et. al
360o Scan
p willemsen, et. al., utah

Interaction
Way behind rest of graphic's spectacular
advances
Still doing WIMP:
Windows, icons, menus, pull-downs/pointing
Once viewed as soft research
Turns out to be one of hardest problems
Interaction still needs...
Better input devices
Better output devices
Better interaction paradigms
Better understanding of HCI
Bring in psychologists
Modeling
Many model reps
Bezier, B-spline, box splines, simplex splines,
polyhedral splines, quadrics, super-quadrics,
implicit, parametric, subdivision, fractal, level
sets, etc (not to mention polygonal)
Modeling
Physically based
Newton
Behavior as well as geometry
Materials
Metal, cloth, organic forms, fluids, etc
Procedural (growth) models
Modeling... is hard
Complexity
Shape
Specifying
Realistic constraints
Detail vs concept
Tedious, slow
s drake, et. al., utah

Modeling is hard
Mathematical challenge
Computational challenge
Interaction challenge
Display challenge (want 3D)
Domain knowledge, constraints
Computer Graphics
One of the central components of three-dimensional
graphics has been a basic system that renders objects
represented by a set of polygons
One approach to rendering three-dimensional objects is to
build a basic renderer then add on enhancements
The basic renderer may be one which incorporates a local
reflection model, such as the Phong model, into a Phong
incremental shader
Computer Graphics
Advantages gained by this approach include:
Modeling objects using polygons is straighforward
Piecewise linearities are rendered invisible by the shading
technique
Geometric information is only stored at the polygonal
vertices - information required for the reflection model
that evaluates a shade at each pixel is interpolated from
this information
This allows fast, hardware-based shading
Computer Graphics
More accurate representations made up of a set
of bicubic patches can be converted to a
polygon representation and fed to such a
renderer
One drawback of using polygons to model
objects is that a large number of polygons are
required to achieve much detail for complex
objects
Computer Graphics
The main steps in rendering a polygonal object are:
1. Polygons representing an object are extracted from the database
and transformed into the world coordinate system using linear
transformations such as translation and scaling
2. A scene constructed in this way is transformed into a coordinate

system based on a view point or view direction.
3. The polygons are then subjected to a visibility test. This is called

backface elimination or culling and removes those polygons that
face away from the viewer.
Computer Graphics
The main steps in rendering a polygonal object are:
4. Unculled polygons are clipped against a three-dimensional view
volume.
5. Clipped polygons are then projected onto a view plane or image

plane
6. Projected polygons are then shaded by an incremental shading

algorithm. First, the polygon is rasterized, or those pixels that the
edges of the polygon contain are determined. Second, a depth for
each pixel is evaluated and a hidden surface calculation is
performed. Third, the polygon is shaded.
Polygonal representation of three-
dimensional objects
Objects that possess curved surfaces have
these surfaces approximated by polygonal
facets
The error introduced by this representation
may be visually diminished by using
interpolative shading algorithms
Polygonal Representation of Curved
Objects
dimensional objects
For complex objects, a number of polygons in
excess of 100,000 is not uncommon
Another problem occurs when objects are
scaled up
An object adequately represented at one size
may degrade when the object is enlarged
This has been called geometric aliasing
dimensional objects
Polygonal representations can be generated
manually from a designers abstraction, or
automatically from real objects by using devices
such as laser rangers in conjunction with the
appropriate software
Complete information necessary to shade a
polygon is usually stored in a hierarchical data
structure - objects; surfaces; vertices and normals
Coordinate systems and rendering
One view of the geometric part of the rendering process is
that it consists of the application of a series of coordinate
transformations that takes an object database through a
series of coordinate systems
For ease of modeling and application of local
transformations, it makes sense to store the vertices of an
object with respect to some point conveniently located in
or near the the object
This is called the local coordinate system
Once an object has been modeled, the next stage is to
place it in the scene that we wish to render
The global coordinate system of the scene is known as the
world coordinate system
All the objects have to be placed into this common space
in order to have their relative spatial relationships defined
The act of placing an object in a scene defines the transformation required to
take the object from local space to global space
If this object is being animated, then the animation provides a time-varying
transformation that takes the object into world space on a frame-by-frame basis
The scene is lit in world space
Light sources are specified
The eye or camera coordinate system is a a
space used to establish viewing parameters and
view volume
A virtual camera can be positioned anywhere
in the world space and can point in any
direction
The scene is projected on a view plane
Backface elimination and culling
This operation removes entire polygons that face away
from the viewer
When dealing with a single convex object, culling completely solves the hidden
surface problem
If an object contains a concavity, or if we have multiple objects in a scene, a
general hidden surface removal algorithm is needed as well as culling
We can determine whether a polygon is visible from a
view point by a simple geometric test
The geometric normal to the polygon is calculated and the angle between this
and the line-of-sight vector is determined. (The line-of-sight vector is the
vector from the polygon to the view point)
If this angle is greater than 90 degrees, then the polygon is invisible.
Screen space
The fundamental transformation that takes us
into screen space is the perspective
transformation which takes a point in the
scene and projects it onto a view plane
positioned at disance D away from the view
point and oriented normal to the viewing
direction
Perspective Transformation
View plane
P(xe, ye, ze)
P'(xs,ys, D)
C
(0,0,D)
D
Screen Space
Screen space is defined to act within a closed
volume called the viewing frustum that
delineates the volume of space which is to be
rendered
Objects that lie outside the viewing frustum
are not rendered
View Frustum
Homogeneous Coordinates
A point in three dimensional space requires 3 coordinates
- x, y and z - to describe its location
In homoegeneous coordinates, an extra coordinate (which
can be thought of as a scaling term) is added
By using homogeneous coordinates, we are able to
represent transformations as matrix multiplications
Then in order to compute the transformation of some
object, we need only perform matrix multiplications for
the vertices of the polygons making up the objects
representation
The transformations we are most interested in
are scaling, translation and rotation
These can be defined as follows
Scaling Transformation
Scaling Transformation
Translation Transformation
Translation Transformation
Rotation About the X-Axis
Rotation About the X-Axis
Rotations about the y and z axis are similar
A series of operations can be combined by
performing a series of multiplications
If the scaling factor is greater than one, the
resulting coordinates must be divided by that
number at the end of the operation
The near plane is the view plane at distance D. The far
plane is at distance F
If the height of the view plane is 2h, then the perspective
transformation can be given by the following matrix:
1 0 0 0
0 1 0 1
0 0 hF/(D(F-D)) h/D
0 0 -hF/(F-D) 0
This transformation can simply be
concatenated with all of the other
transformations in the rendering pipeline
Clipping is performed against the viewing
frustum
Objects lying completely outside the frustum are
discarded
Objects inside the frustum are transformed into
screen space and then rendered
Objects intersecting the frustum are clipped and
then transformed into screen space
Pixel-Level Processes
Once the objects in a scene have been
translated into screen space, the processing is
oriented towards pixels rather than polygons
Rasterization, hidden-surface removal and
shading are all pixel-level processes
Rasterization
Rasterization is the process of finding out which pixels a
polygon projects onto in screen space
Calculate, for each scan line within a polygon, by linear
interpolation, the x values of the edge pixels, xstart and xend
This results in a span of pixels between two edges that
have to be rendered
Care must be taken in these calculations, otherwise we
will have aliasing problems (e.g. a straight line may
appear to be a series of steps)
Most of these problems are caused by rounding errors in the interpolation of
polygon edges
Hidden Surface Removal
We now know which pixels contain which
objects, however since some pixels may
contain two or more objects we must calculate
which of these objects is visible and which are
hidden
Hidden surface removal is generally
accomplished using the Z-buffer algorithm
In this algorithm, we set aside a two-dimensional array of
memory (the Z-buffer) of the same size as the screen (#rows x
#columns)
This is in addition to the buffer we will use to store the values
of pixels which will be displayed (color values)
The Z-buffer will hold values which are depths (or z-values)
The buffer is initialized so that each element has the value of
the far clipping plane (the largest possible z-value after
clipping has been performed)
The other buffer is initialized so that each element contains a
value which is the background color
Now for each polygon we have a set of pixel values
which that polygon covers
For each one of these pixels, we compare its interpolated
depth (z-value) with the value of the corresponding
element already stored in the Z-buffer
If this value is less than the previously stored value, the pixel is nearer the
viewer than previously encountered pixels
Replace the old value of the Z- buffer with the new, interpolated value and
replace the old value of the other buffer with the value (color) of the pixel
Repeat for all polygons in the image
Interpolative or Incremental Shading
A major reason for the growth of popularity of
polygon-based renderers is the existence of
two interpolative or incremental shading
algorithms usually known as Gouraud shading
and Phong shading
Gouraud shading is faster than the other
method, but cannot produce accurate
highlights. It is usually used in applications
where speed is important
Phong shading gives higher quality images,
but is more expensive
Gouraud shading calculates intensities at
polygon vertices only, using a local reflection
model, and interpolates these for pixels within
the polygon
Phong shading interpolates vertex normals and
applies a local reflection model at each pixel
The motivation of both schemes is efficiency
and the convincing rendering of polygonal
objects
This means that as well as giving an
impression of solidity or three-dimensionality
to the model, the shared edges in adjacent
polygons that approximate a curved surface,
are made invisible
Gouraud Shading
Generally, the intensity of light at a polygon vertex is
described as a function of the orientation of vertex
normals with respect to both the light source and the eye
This function is called a reflection model
Gouraud shading applies a local reflection model at each
vertex of a polygon to calculate a set of vertex intensities
These intensities are linearly interpolated across the
polygon interior on a scan line basis
Phong Shading
In Phong shading, the vertex normals
(calculated exactly as in Gouraud shading) are
linearly interpolated
The local reflection model is then applied at
each pixel using the interpolated normal
This solves the highlight problem and Mach
banding, but is more computationally
expensive

Net Study Material

Uploaded by

Copyright:

Available Formats

Net Study Material

Uploaded by

Document Information

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

Net Study Material

Uploaded by

Copyright:

Available Formats

UNIX System Programming

Each user can run many processes at once

A process is the context (the information/data) maintained for

Intuitively, a process is the abstraction of a physical processor.

IMPORTANT: A process is sequential

getty getty getty

You can get the process pid or parents pid

Creates a child process by making a copy of

Both the child and the parent continue

pid = fork() Child

Returns a new PID:

In the child: pid == 0;

A program almost always uses this pid

The switching between the parent and child

I/O buffering effects amount of output shown.

Output interleaving is nondeterministic

execlp(sort, sort, -n,

Same as "sort -n foobar"

execlp( cmd[i], cmd[i], (char *)0 );

There are 6 versions of the exec function,

execl() execle() execlp()

Suspends calling process until child has

statloc can be (int *)0 or a variable which

return immediately with the termination

return immediately with an error if there

waitpid - can wait for a particular child

if( (pid = fork() ) == 0 )

Since a child process is a copy of the

A change to a variable in the child will

if( (pid = fork()) == 0 )

printf( pid = %d, globvar = %d, w = %d\n,

$ globex > temp.out

A child and parent have copies of the file

This means that a read() or write() in

read(fd, buf, 10); /* move R-W ptr */

printpos( Before fork, fd );

if( (pid = fork()) == 0 )

if( (pos = lseek( fd, 0L, SEEK_CUR) ) < 0L )

printf( %s: %ld\n, msg, pos );

1) A child exits when its parent is not currently

Sets the effective user ID of the current process.

Non-superuser process can set effective user ID to uid, only when

In any other cases, setuid returns error.

real-uid unchanged unchanged uid unchanged

Sets real and effective user IDs of the current process.

void main( int argc, char *argv[], char *envp[] )

printf( from argument envp\n );

for( i = 0; envp[i]; i++ )

printf(\nFrom global variable environ\n);

for( i = 0; environ[i]; i++ )

printf(New home directory is %s\n, getenv(HOME));

3D Points on the same viewing line have the

Depth can be recovered with two images and triangulation.

Determine Pixel Correspondence

epipolar line epipolar line

T is the stereo baseline

For each epipolar line

Improvement: match windows

Effect of window size

Scene Ground truth

void main( int argc, char argv[], char envp[] )