Transcript Slide 1

Lecture 1:
Introduction to Computer Algorithms
This course is intended for 3rd and/or 4th year undergraduate majors in Computer Science.
You need to be familiar with the design and use of basic data structures such as Lists, Stacks,
Queues, Trees, and Graphs.
top
back
front
Queue
Tree
List
Stack
root
cycle
parent
node
path
child
node
leaf
nodes
edge
vertex
Graph
What you Need to Know and Do
You should be able to understand and implement basic methods for searching and sorting.
You should be able to determine the worst-case order of complexity (number of operations)
required to solve a problem of size N using the best-known algorithm.
Suggest an algorithm and give a worst-case order of complexity for each of the following:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
Search an unordered list of n items to find a particular item x.
Search an ordered list of n items to find a particular item x.
Find the smallest value in an unordered list of n items.
Find the largest value in an ordered list of n items.
Determine if an unordered list contains a repeated value.
Find the kth largest value in an unordered list of n items (k<=n).
Find the kth largest value in an ordered list of n items (k<=n).
Sort an unordered list of n items into ascending order (sort by key comparison).
Find a pair of items x and y in an unordered list that are the most similar.
Find a pair of items x and y in an ordered list that are the most similar.
Find a pair of items in an ordered list that are the least similar.
Arrange a list so that the sum of the abs. differences between adj. items is a minimum.
Arrange a list so that the sum of the abs. differences between adj. items is a maximum.
Find the two pairs of points (in R2 ) whose separations are the most similar.
Try These
You should be proficient in at least one programming language.
Many of the problem sets will be in the form of a text file containing a list or matrix of floating
point values, integers, characters, or strings.
You need to build a set of software tools to perform the following operations:
Read and Write a list of integers, floats or characters to and from a text file.
Read and Write a list of points in R2 to and from a text file.
Read and Write a two-dimensional array of integers, floats or characters to and from a text file.
Search a list to find a particular item.
Sort a list into ascending or descending order.
Exchange two values in a list.
Compute the distance between two points in R2.
Find the particular value (e.g. minimum value) in a row or column of a matrix
Add (or subtract) a value to (from) every value in a row or column
Exchange two rows or two columns in a matrix.
Lists & Arrays
Reading Values from a Text File into an Indexed Array
public static int[] A;
public static void readarray()
{
string fname;
string str;
int n = 0;
Console.Write("Enter filename..... ");
fname = Console.ReadLine();
used to count the number
of values so that the Array
A[n] can be created.
TextReader sr = new StreamReader(fname);
do
{
str = sr.ReadLine();
n += 1;
}while (str != null);
sr.Close();
A = new int[n];
TextReader tr = new StreamReader(fname);
}
for (int i = 0; i < n; i++)
A[i] = Convert.ToInt32(tr.ReadLine());
tr.Close();
Reading Values from a Text File into a List
public static List<int> S = new List<int>();
public static void readlist()
{
string fname;
string str;
int s;
Console.Write("Enter filename..... ");
fname = Console.ReadLine();
TextReader tr = new StreamReader(fname);
do
{
str = tr.ReadLine();
if (str != null)
{
s = new int();
s = Convert.ToInt32(str);
S.Add(s);
}
} while (str != null);
}
tr.Close();
Searching an Unordered List
Searching an Ordered List
A Common Sort Routine
a procedural approach
ReadList(filename, n, S)
for i = 1 to n - 1
for j = i + 1 to n
if (S( i ) > S( j )) then
exchange(S( i ), S( j ))
end if
end loop
end loop
WriteList(filename,S)
// reads a list of n values from the text file, filename
// into the list S. n and S are passed back to the calling routine
// if statement implements the key comparison
// exchange swaps the position of two values in the list S
// writes the sorted list, S back to the hard drive as filename
Sorting the Values in a List
public static void sortlist()
{
int tmp;
for (int i = 0; i < S.Count() - 1; i++)
for (int j = i + 1; j<S.Count(); j++)
if (S[i] > S[j])
{
tmp = S[i];
S[i] = S[j];
S[j] = tmp;
}
}
Sorting the Values in an Indexed Array
public static void exchange(ref int a, ref int b)
{
int tmp = a;
a = b;
b = tmp;
}
public static void sortarray()
{
for (int i = 0; i < A.Length; i++)
for (int j = i + 1; j < A.Length; j++)
if (A[i] > A[j])
exchange(ref A[i], ref A[j]);
}
Algorithm Growth Rate Analysis
Best Case -- Worst Case
Recursion Hides most of the Details
function recurse(n)
deal with n
for each f(n) = m
if(m is OK)
recurse(m)
deal with n
// there is usually something to do with the incoming value
// if no m is OK then this call has reached its termination condition
// sometimes the incoming value is processed after the recursion
It is important to understand that each recursive call interrupts the for-each loop until the
call has returned
Certain values of m may be OK at beginning of for-each loop but may become not OK by
the time the loop reaches them
Regardless of the number of valid recursive calls in any for-each loop, if each value of N
can be accessed only once, the overall runtime complexity will be O(N).
Recursion goes bad (exponential run-time complexity) when each value of problem of size
N can be in more than one recursive call.
The Hazards of Recursion
There's a hole in the bucket.
Plug the hole with the cork.
Bring water from the well.
The cork is to big.
There is no water.
Trim the cork with the knife.
Wet the stone with water.
The knife is too dull.
The sharpening stone is too dry.
Sharpen the Knife.
Trees
For Example...
function foob(n)
if n>0
return foob(n-1) + foob(n-1)
function feeb(n)
if n>0
return feeb(n-1)
Sort Tree Traversals
A A
All traversals are in the same order
B
A
C
A
B
The difference is when the node is evaluated
(i.e. passed to the output)
C
Sort Trees are normally implemented using
D
B
A
D
E
B E
A
F
C
A
G
C G
A
F
H
F H
C
A
pre-order
1.eval node
2.left-child
3.right-child
ABDECFHIG
I
dynamic memory and pointers
Can you think of a practical alternative?
I
F
C
A
in-order
1.left-child
2.eval node
3.right-child
DBEAHFICG
post-order
1.left-child
2.right-child
3.eval node
DEBHIFGCA
Binary Tree Embedded in an Indexed List
1
(1) parent = child / 2
(2) left_child = 2 x parent
2
4
5
8
1
9
16
17
18
2
3
4
5
6
10
19
6
(3) right_child = 2 x parent + 1
3
11
20
21
7
8
22
7
12
23
24
13
25
26
14
27
28
15
29
30
31
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Graphs
Types of Graphs
ring
complete graph
directed acyclic graph
bipartite graph
Graph Representations
A
D
C
B
node list
A-BCDEF
B-ACEH
C-ABDEH
D-ACFGH
E-ABCFG
F-ADEGH
G-DEFH
H-BCDFG
F
H
E
G
node list - lists the nodes connected to each node
edge list - lists each of the edges as a pair of nodes
undirected edges may be listed twice XY and YX
in order to simplify algorithm implementation
adjacency matrix - for an n-node graph we build an
nxn array with 1's indicating edges and 0's no edge
the main diagonal of the matrix is unused unless a
node has an edge connected to itself. If graph is
weighted, 1's are replaced with edge weight values
A
B
C
D
E
F
G
H
adjacency matrix
A B C D E F G
- 1 1 1 1 1 0
1 - 1 0 1 0 0
1 1 - 1 1 0 0
1 0 1 - 0 1 1
1 1 1 0 - 1 1
1 0 0 1 1 - 1
0 0 0 1 1 1 0 1 1 1 0 1 1
H
0
1
1
1
0
1
1
-
edge list
AB
EA
AC
EB
AD
EC
AE
EF
AF
EG
BA
FA
BC
FD
BE
FE
BH
FG
CA
FH
CB
GD
CD
GE
CE
GF
CH
GH
DA
HB
DC
HC
DF
HD
DG
HF
DH
HG
Graph Breadth-First Traversal
Given a graph G(V,E) and a starting vertex s, perform
a breadth-first traversal (BFT) of G. such that each
reachable vertex is entered exactly once.
If all vertices are reachable, the edges traversed and
the set of vertices will represent a spanning tree
embedded in the graph G.
A
D
F
C
B
H
E
G
1) BFT suggests an iterative process (rather than a recursive one)
2) BFT vertices order of traversal can be maintained using a Queue data structure
3) The preferred representation for the graph is an adjacency matrix
4) We will need a way to keep up with which vertices have been "used" (e.g. a Boolean list)
5) Process begins by placing the starting vertex in the Queue
6) A vertex is taken from the Queue, every unused vertex adj to this vertex is added to the Queue
This operation is repeated until the Queue is empty.
8) The output (answer) is returned in the form of a list of vertices in the order they entered the Queue
Graph Depth-First Traversal
Given a graph G(V,E) and a starting vertex s, perform
a depth-first traversal (BFT) of G. such that each
reachable vertex is entered exactly once.
A
If all vertices are reachable, the edges traversed and
the set of vertices will represent a spanning tree
embedded in the graph G.
B
D
F
C
H
E
G
1) DFT suggests a recursive process (rather than an iterative one)
2) DFT vertices order of traversal are maintained automatically by the recursion process (as a Stack)
3) The preferred representation for the graph is an adjacency matrix.
4) We will need a way to keep up with which vertices have been "used" (e.g. a Boolean list)
5) Process begins by passing the starting vertex to a recursive function DFT(s)
6) For the current vertex, s DFT(s) calls itself for each adjacent, unused vertex remaining.
This operation is completed when all calls to DFT( ) are completed.
8) The output is returned as a of a list of vertices in the order they were passed to DFT( ).
Graph Depth-First Traversal (DFT) Algorithm Implementation
text file representation
Given a graph G(V,E) and a starting node vstart perform a depth-first traversal. Provide a list of the
nodes in the order they are traversed.
Graph is defined in a text file of the following format:
1st Line - # of nodes, N # of edges, E
2nd Line - List of node labels (you may assume 1 char each)
3rd Line - through N+3 Line
an N x N adjacency matrix
A
D
F
C
B
H
E
G
8
ABCDEFGH
01111100
10101001
11011001
10100111
11100110
10011011
00011101
01110110
Graph Depth-First Traversal (DFT) Algorithm Implementation
pseudo-code
DFT( node vk )
{
// deal with current node
for each node, vi
{
if (node_avail(vi)) then
DFT(vi)
}
}
node_avail( vi ) is a Boolean function that returns true if node vi is available for traversal,
which means that vi has not been traversed, and vi is adjacent to vk.
Summary
• "Stuff You Should Already Know (SYSAK)...
• Important Data Structures - lists, stacks, queues, trees, and graphs
• 13 Problems to Consider
• Reading Data from Text Files
• Searching and Sorting
• Methods for Growth-Rate Analysis
• Recursion (good and bad)
• Manipulating Lists and Matrices
• Dealing with Trees
• Working with Graphs