1
Tuesday, March 4, 14
IMPROVING PSEUDOCODE
CS16: Introduction to Data Structures & Algorithms
Tuesday, March 4, 14
Clean Your Code
•  Errors per line ~ constant
•  Fewer lines à fewer errors overall
•  Fewer lines are easier to grade
•  More likely to receive credit
•  Cleaner code reflects cleaner thinking and
a better understanding of the material
•  Let’s work through an example…
2
Tuesday, March 4, 14
3
Lowest Common Ancestor (LCA)
Problem: Given two nodes u and v,
determine the deepest node that’s an
ancestor of both.
A
B
E
F
I
D
C
J
G
K
u
v
LCA(u, v)
C
D
A
J
E
B
G
J
A
G
C
C
H
Tuesday, March 4, 14
function LCA(u, v):
lca = null
udepth = T.depth(u)
vdepth = T.depth(v)
if (T.isroot(u) == true) or (T.isroot(v) == true) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if udepth > vdepth then
u = T.parent(u)
udepth = udepth – 1
else if vdepth > udepth
v = T.parent(v)
vdepth = vdepth – 1
else
u = T.parent(u); udepth = udepth - 1
v = T.parent(v); vdepth = vdepth – 1
return lca
4
Tuesday, March 4, 14
5
function LCA(u, v):
What are the inputs? The output?
lca = null
udepth = T.depth(u)
vdepth = T.depth(v)
if (T.isroot(u) == true) or (T.isroot(v) == true) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if udepth > vdepth then
u = T.parent(u)
udepth = udepth – 1
else if vdepth > udepth
v = T.parent(v)
vdepth = vdepth – 1
else
u = T.parent(u); udepth = udepth - 1
v = T.parent(v); vdepth = vdepth – 1
return lca
Tuesday, March 4, 14
function LCA(u, v):
// Input: two nodes u, v
// Output: the lowest common ancestor of u and v
lca = null
udepth = T.depth(u)
vdepth = T.depth(v)
if (T.isroot(u) == true) or (T.isroot(v) == true) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if udepth > vdepth then
u = T.parent(u)
udepth = udepth – 1
else if vdepth > udepth
v = T.parent(v)
vdepth = vdepth – 1
else
u = T.parent(u); udepth = udepth - 1
v = T.parent(v); vdepth = vdepth – 1
return lca
6
Tuesday, March 4, 14
function LCA(u, v):
// Input: two nodes u, v
// Output: the lowest common ancestor of u and v
lca = null
Where does T
udepth = T.depth(u)
come from?
vdepth = T.depth(v)
if (T.isroot(u) == true) or (T.isroot(v) == true) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if udepth > vdepth then
u = T.parent(u)
udepth = udepth – 1
else if vdepth > udepth
v = T.parent(v)
vdepth = vdepth – 1
else
u = T.parent(u); udepth = udepth - 1
v = T.parent(v); vdepth = vdepth – 1
return lca
7
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
udepth = T.depth(u)
vdepth = T.depth(v)
if (T.isroot(u) == true) or (T.isroot(v) == true) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if udepth > vdepth then
u = T.parent(u)
udepth = udepth – 1
else if vdepth > udepth
v = T.parent(v)
vdepth = vdepth – 1
else
u = T.parent(u); udepth = udepth - 1
v = T.parent(v); vdepth = vdepth – 1
return lca
8
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
udepth = T.depth(u)
vdepth = T.depth(v)
if (T.isroot(u) == true) or (T.isroot(v) == true) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if udepth > vdepth then
Needlessly complex
u = T.parent(u)
udepth = udepth – 1
else if vdepth > udepth
v = T.parent(v)
vdepth = vdepth – 1
else
u = T.parent(u); udepth = udepth - 1
v = T.parent(v); vdepth = vdepth – 1
return lca
9
Tuesday, March 4, 14
10
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
udepth = T.depth(u)
Now irrelevant
vdepth = T.depth(v)
if (T.isroot(u) == true) or (T.isroot(v) == true) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
Tuesday, March 4, 14
11
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
if (T.isroot(u) == true) or (T.isroot(v) == true) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
Tuesday, March 4, 14
12
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
Redundant equality checks
if (T.isroot(u) == true) or (T.isroot(v) == true) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
Tuesday, March 4, 14
13
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
if
T.isroot(u)
or T.isroot(v)
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
then
Tuesday, March 4, 14
14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
if T.isroot(u) or T.isroot(v) then
lca = T.root
while (lca == null) do
if (u == v) then
lca = u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
if T.isroot(u) or T.isroot(v) then
Just r
lca = T.root
whites emoving s
o
pace
to fit o me
while (lca == null) do
n slide
s
if (u == v) then
lca = u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
15
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
if T.isroot(u) or T.isroot(v) then
lca = T.root
It’s the answer, return it!
while (lca == null) do
if (u == v) then
lca = u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
16
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
if T.isroot(u) or T.isroot(v) then
lca = T.root
return lca
while (lca == null) do
if (u == v) then
It’s the answer, return it!
lca = u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
17
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
if T.isroot(u) or T.isroot(v) then
lca = T.root
return lca
while (lca == null) do
if (u == v) then
lca = u
return lca
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
18
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
if T.isroot(u) or T.isroot(v) then
lca = T.root
Condition is irrelevant
return lca
while (lca == null) do
if (u == v) then
lca = u
return lca
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
return lca
19
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
lca = null
if T.isroot(u) or T.isroot(v) then
lca = T.root
return lca
lca is no longer used
repeat
if (u == v) then
lca = u
return lca
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
20
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
if T.isroot(u) or T.isroot(v) then
return T.root
repeat
if (u == v) then
return u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
21
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
if T.isroot(u) or T.isroot(v) then
return T.root
repeat
if (u == v) then
return u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
22
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
if T.isroot(u) or T.isroot(v) then
return T.root
repeat
if (u == v) then
return u
else
if T.depth(u) > T.depth(v) then
u = T.parent(u)
else if T.depth(v) > T.depth(u)
v = T.parent(v)
else
u = T.parent(u)
v = T.parent(v)
23
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
while T.depth(u) > T.depth(v)
u = T.parent(u)
while T.depth(v) > T.depth(u)
v = T.parent(v)
if T.isroot(u) or T.isroot(v) then
return T.root
repeat
if (u == v) then
return u
else
u = T.parent(u)
v = T.parent(v)
24
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
while T.depth(u) > T.depth(v)
u = T.parent(u)
while T.depth(v) > T.depth(u)
v = T.parent(v)
if T.isroot(u) or T.isroot(v) then
return T.root
repeat
if (u == v) then
return u
else
u = T.parent(u)
v = T.parent(v)
25
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
while T.depth(u) > T.depth(v)
u = T.parent(u)
while T.depth(v) > T.depth(u)
v = T.parent(v)
if T.isroot(u) or T.isroot(v) or u == v then
return u
repeat
if (u == v) then
return u
else
u = T.parent(u)
v = T.parent(v)
26
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
while T.depth(u) > T.depth(v)
u = T.parent(u)
while T.depth(v) > T.depth(u)
Can be simplified!
v = T.parent(v)
if T.isroot(u) or T.isroot(v) or u == v then
return u
repeat
if (u == v) then
return u
else
u = T.parent(u)
v = T.parent(v)
27
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
while T.depth(u) > T.depth(v)
u = T.parent(u)
while T.depth(v) > T.depth(u)
v = T.parent(v)
if u == v then
return u
repeat
if (u == v) then
return u
Condense into a single loop!
else
u = T.parent(u)
v = T.parent(v)
28
Tuesday, March 4, 14
function LCA(u, v, T):
// Input: two nodes u, v in a tree T
// Output: the lowest common ancestor of u and v
while T.depth(u) > T.depth(v)
u = T.parent(u)
while T.depth(v) > T.depth(u)
v = T.parent(v)
while u != v then
u = T.parent(u)
v = T.parent(v)
return u
From a clunky 19 lines to an elegant 8 line beauty!
29