Lecture 22 – November 12, 2007
In
class everyone filled in the Big O estimates of the running time of each of the
following code fragments. We then went
over the ones whose answers are shown in red. For homework, you are to determine the
answers to the remaining two.
1.
Determine a Big O
estimate of the running time of each of the following code fragments. In each case, assume that the integer
identifier N is proportional to the
problem size:
Count := N;
loop
exit when Count <= 0;
-- some code without any loops
Count := Count - 4;
end loop;
Big O O(n)
for Count in 1..N loop
-- some code without any loops
end loop;
for Count
in reverse 1..N loop
-- some code without any loops
end loop;
Big O O(n)
Count := 1;
loop
exit when Count >= N;
-- some code without any loops
Count := 17 * Count;
end loop;
Big O O(lg n)
for Count in 1..2_500_000 loop
-- some code without any loops
end loop;
Big O O(1)
Count := 1;
loop
exit when Count >= N;
for Index in 1..Count loop
-- some code without any loops
end loop;
Count :=
Count + 1;
end loop;
Big O O(n2)
Count := 1;
loop
exit when Count >= N;
Index := Count;
loop
exit when Index <= 0;
-- some code without any loops
Index := Index / 13;
end loop;
Count :=
Count + 1;
end loop;
Big O
for Index in 1..N loop
-- some code without any loops
end loop;
Count :=
1;
loop
exit when Count >= N;
-- some code without any loops
Count := 2 * Count;
end loop;
Big O
We discussed what was learned from the
in-class exercise last week. Merge Sort
and Quick Sort are faster than Bubble
Sort and Insertion Sort. We reviewed
their growth rates (Big O). Merge
Sort and Quick Sort are O(N log2N), Bubble Sort and Insertion Sort are O(N2).
We learned that :
·
2N, .25N,
N/4 are all O(N)
·
Any
constant is O(1)
· When the computation of the work yields something like (N2+3N)/2, the term with the biggest exponent dominates and the answer is O(N2).
What is the Big O of the program below? O(1)
with Ada.Text_IO;
with Ada.Float_Text_IO;
procedure Pennies is
Three_Pennies : constant Float := 0.03;
Total_Dollars : Float;
begin
Total_Dollars := 0.0;
-- Initialize the sum
for Count
in 1..100_000 loop
Total_Dollars := Total_Dollars +
Three_Pennies;
end loop;
Ada.Float_Text_IO.Put (Item => Total_Dollars,
Fore => 10,
Aft => 2,
Exp => 0);
Ada.Text_IO.New_Line;
Ada.Float_Text_IO.Put
(Item => 100_000.0 * Three_Pennies,
Fore => 10,
Aft => 2,
Exp => 0);
Ada.Text_IO.New_Line;
end Pennies;
2.
What output would you expect from the program above?
3000.00
3000.00
We
spent time discussing that decimal fractions which terminate may not terminate
as binary fractions.
We
discussed how to convert a base ten decimal fraction into a base two binary
fraction by repeatedly:
Example:
.3
x 2
0.6
x2
1.2
x2
0.4
x2
0.8
x2
1.6 repeats
answer: .01001…
We very briefly reviewed the notes from
Nov. 5th (lecture 21)
We
went on to define a binary tree as:
type
node;
type
nodepointer is access node;
private
type node is record
info
: integer;
left : nodepointer;
right : nodepointer;
end
record;
We
then wrote code to create some nodes and connect them in a binary tree
temp
:= new node;
temp.info
:= 14;
root
:= temp;
temp:=
new node;
temp.info
:= 2;
if
(temp.info < root.info) then
root.left := temp;
--
else not completed
We
then created a third node
temp
:= new node;
temp.info
:= -5;
and
discovered that the code we wrote to find where to put it wouldn't work.
Assignment
for Wednesday: Modified and simplified from in-class
description
Write
a program (an .adb) to create and insert nodes into their proper place in a
binary search tree. Get the node values
from the user.