CoE 163

Computing Architectures and Algorithms

01a: Algorithms Review

REMEMBER EEE 121?

Data structures and

algorithms are key in solving
any computer engineering
problem.
Knowledge of these basic
concepts enable you to solve
large real-world problems.

2
BASIC DATA
STRUCTURES
◦ Basic
◦ Numbers
◦ Strings
◦ Sets
◦ Linear
◦ Arrays, linked lists
◦ Stacks, queues
◦ Graph
◦ Adjacency matrix
◦ Adjacency list
◦ Disjoint set

3
BASIC DATA
STRUCTURES
◦ Trees, heaps
◦ Binary tree (AVL, red-black)
◦ String trees (trie)
◦ Geometry
◦ Point pairs
◦ Polygon list

4
DATA STRUCTURES: LINEAR
Array: elements of usually same type arranged linearly

A B C D E

Linked list: a loosely-connected array

A B C D E

5
DATA STRUCTURES: LINEAR
Stack: last in, first out; single-ended array
in
A B C D E
out

Queue: first in, first out; double-ended array

in A B C D E out

6
DATA STRUCTURES:
LINEAR
◦ Arrays are useful for fixed and
arranged things
◦ AA battery chargers
◦ Piano keys
◦ Linked lists are useful for things
where middle elements can change
◦ Clinic appointments with
cancellations
◦ Word editing (letter
insertion/deletion)

7
DATA STRUCTURES:
LINEAR
◦ Stacks are useful for things that
need stacking - usually vertical
◦ Box stacking in warehouses
◦ Tetris
◦ Queues are useful for things that fall
in line - usually horizontal
◦ Queueing systems in fast food
◦ Groceries sorted by expiry
date
◦ A stack and a queue in one is called
a deque (double-ended queue)

8
DATA STRUCTURES: GRAPH
Adjacency matrix: 2D array with indices as the two nodes and
value the weight or interconnection flag
destination
node 0 node 1 node 2 ● Rows correspond to origin
node 0 0 0 1 node and columns the
destination node

origin
node 1 1 0 1 ○ Can be reversed
depending on how you
node 2 1 0 0 code the graph
○ An undirected graph
can be represented as
a symmetric matrix
0 1
● If an element along the
diagonal is nonzero, there is an
edge to the element itself

9
DATA STRUCTURES: GRAPH
Adjacency list: Array of variable-length arrays listing neighbors of
a node

neighbors
● Saves space as it does
node 0 2 not allocate a vxv matrix (v
the number of nodes)

node
node 1 0 2
● An edge to a node itself
node 2 0 can be represented by
listing itself in its
adjacency list
0 1

10
DATA STRUCTURES: GRAPH
Disjoint set: Array with indices as node labels and value denoting
which node is its parent
node
node 0 node 1 node 2
● This is actually a set data
parent 2 0 -1 structure, but usually
comes up in graphs
● Disjoint sets do not have
cycles and have only one
parent
● Traversal is recursive and
0 1 can be implemented
efficiently if paths are
compressed

11
DATA STRUCTURES:
GRAPH
◦ Adjacency matrices are useful for
dense and small graphs
◦ “Flow Free” game
◦ Adjacency lists are useful for sparse
and large graphs
◦ Road networks
◦ Disjoint sets are useful for
child-parent-like relationships
◦ Family trees

12
DATA STRUCTURES: TREE
Binary tree: Tree that has at most two children

node
0 1 2 3 4
● There are different kinds of
A C D E B binary trees
○ AVL, red-black, splay…
● Balancing is important to
ensure efficient traversal and
mutation
A
● Implement as a graph, linked
“list”, or 1D array
○ Linked “list” consists of
C D nodes, with each
tracking the left and
right subtrees
E B ○ 1D array arranged as
breadth-first traversal
13
DATA STRUCTURES: TREE
Heap: Tree that satisfies the heap property (parent root has
higher/lower value than children)
node
0 1 2 3 4
● Max heap has the
10 4 8 2 3 highest-valued node at
the root
● Can be stored as a 1D
array the same as a binary
10
tree
● Balancing is important to
maintain the heap
4 8
property

2 3

14
DATA STRUCTURES: TREE
Trie (Prefix tree): Tree that locates specific keys within a set

node
0 1 2 3 4
● A node is defined by its
d i o r parent prefix and its value
concatenated
● Can be stored as a 1D
array with the suffix as
value
● Children of leaf nodes
need to be represented
d i
with a symbol to denote
end of trie
do dr

15
DATA STRUCTURES:
TREE
◦ Binary trees are useful for balanced
matching and searching
◦ Parentheses matching
◦ Heaps are useful for maintaining
order while mutating data
◦ Senior citizen lane in groceries
◦ Tries are useful for matching and
finding
◦ String searching

16
BASIC ALGORITHMS

◦ Graph theory
◦ Traversal and shortest paths
◦ Minimum spanning tree
◦ Problem solving paradigms
◦ Complete search and
recursion
◦ Divide and conquer
◦ Dynamic programming/greedy

17
BASIC ALGORITHMS

◦ Math and geometry

◦ Probability and statistics
◦ Plane/analytic/spherical
geometry
◦ String processing
◦ String matching
◦ Trees, tries, and arrays
◦ Data processing
◦ Sorting
◦ Filter and transformation

18
ALGORITHMS: GRAPH
TRAVERSAL
Graph traversal: Search by visiting a node and its neighbors
systematically

Traversal order ● Depth-first search (DFS): visit

● DFS: A-C-E-B-D the deepest part of a path,
then backtrack
● BFS: A-C-D-E-B
○ Uses a stack to track
nodes being visited
● Breadth-first search (BFS): visit
A
by layer
○ Uses a queue to track
nodes being visited
C D ● Traversal can be modified to
determine shortest path
between two nodes
E B

19
ALGORITHMS: SHORTEST PATH
Shortest path: Find path between two nodes that has the
minimum weight

Some shortest paths ● Dijkstra’s: visit and “relax”

● A to D: costs 3 (A-D) edges to find
minimum-weighted path
● A to E: costs 5 (A-C-E)
○ A priority queue can be
used to pick which
8 nodes to visit first
A
● Bellman-Ford: similar to
1 3
Dijkstra’s but works on
2 negative weights
C D ○ Uses dynamic
4 5 programming to “relax’
edges
E B

20
ALGORITHMS: MINIMUM
SPANNING TREE
Minimum spanning tree: Find set of edges that cumulatively
have the total minimum weight and still connects all nodes

Minimum edges needed ● Kruskal: Sort edges from the

● With weights 1, 2, 4, 5 lowest weight and get those
on top if the two nodes are not
connected yet
● Prim: Select a random node
8 and pick a connecting edge
A
with the lowest weight. Collect
1 3
edges from the resulting
2 connected node and repeat
C D choosing of edges among all
4 5 the connected nodes in such
fashion.
E B

21
ALGORITHMS: PROBLEM
SOLVING
Complete search: Iterate through all possibilities of a solution
systematically

Put queens on a grid where they do not ● Brute force: Create nested
threaten each other
● Put queens by row, taking care to loops or recursions to
put them in separate columns explore all possibilities
● Check for threats at the diagonal and
backtrack to previous layout if there
● A*: Explore nodes with the
are lowest cost first
● Graph traversal: Reform
problem into a graph
problem and traverse
through all possibilities

22
ALGORITHMS: PROBLEM
SOLVING
Divide and conquer: Recurse through a problem by splitting it
into n similar problems and consolidating the solutions

You have a cat of length a. Find two ● Binary search on a tree is

cats on a row of cats ordered from an example
shortest length that is a little longer
● Bisection method is useful
and little shorter than yours.
● Use binary search to find the in arriving at a numerical
floor and ceiling lengths solution
row of cats

1 2 3 5 7 10 12

Your cat is of length 8

Go to segments 5-12, 5-7, 10-12
Closest lengths are 7 and 10

23
ALGORITHMS: PROBLEM
SOLVING
Dynamic programming: Prune complete search by observing
recursion leading to an optimal solution

Determine grouping of matrix chain ● Top-down: Recurse from

multiplications that will yield the smallest
number of operations the top and parts of the
● A: 3x2, B: 2x5, C: 5x4; E = ABC solution for later rebuilds
● Group matrices like complete search
● Overwrite saved solution if it is
● Bottom-up: Build up to
smaller the solution from base
until cases
A B C
● Build order is important!
A 0 30 64 ● Solution configuration can
be recovered by saving
from

B 0 40 previous iterations
C 0

24
ALGORITHMS: PROBLEM
SOLVING
Greedy: Get what is best at the moment

Buy two take one free promo! Find ● Special case of dynamic
the maximum discount you can get programming that satisfies
given your basket items.
the greedy property
● Go to the counter with the
three most expensive items on ● Although it does not work
your basket every time all the time, it can yield
fast and slightly
shopping basket
suboptimal solutions
1 2 3 5 7 10 12 ● When in doubt, use
dynamic programming
checkout
instead

Saved 9!
25
ALGORITHMS: MATH AND
GEOMETRY
Basic arithmetic: Remember elementary axioms, factors, etc.

Three friends share a garden - one ● Radix/Base conversion

worked A hours and another worked ● Numerical pattern finding
B hours to clean up the whole
● Fractions
garden. The third friend paid D
dollars. How much should A get? ● Logarithms and
exponents
● Prime numbers
● Modular arithmetic
● Euclidean algorithm
A, B, and C have equal shares. A and
B clean up their respective areas plus
extra time that they give up to clean
C’s area.
26
ALGORITHMS: MATH AND
GEOMETRY
Probability and statistics: Apply basic probability axioms and
combinatorics

Monty Hall problem - find the chance ● Permutations and

of winning when you switch to combinations
another door
● Bayes’ theorem,
doors conditional probabilities
● Binomial, Catalan,
? goat ?
Fibonacci numbers

If you stayed with your original choice, it’s as

if you just opened that door straight away, so
the chance is ⅓.

The chance if switching is therefore ⅔.

27
ALGORITHMS: MATH AND
GEOMETRY
Geometry: Apply 2D and 3D geometry theorems and conjectures

● Line and plane

intersections
● Area, perimeter, volume
● Convex hull
● Point inside polygon
● Be careful of numerical
errors when using
floating-point!

28
ALGORITHMS: STRINGS
String matching, processing, and manipulation

● Knuth-Morris-Pratt
algorithm
● String alignment
● Suffix trie, prefix tree,
arrays

29
ALGORITHMS: DATA
PROCESSING
Apply algorithms to sort, filter, and transform data

● Bubble, insertion,
selection sorts
● Priority queue
● Summation and
production
● Bit masking
● Character to ASCII value

30
TIPS

◦ Learn new algorithms and data

structures
◦ Be exposed to a lot of known
CS problems
◦ Practice by trying out online
judges, solving some problems,
and getting used to input/output
formatting

31
CoE 163
Computing Architectures and Algorithms

01a: Algorithms Review