Class 

Topics

 Reading Assignments 
& Handouts

 Laboratory 
Assignments 

# 1

8/28

R

# 2

9/2

T

Spend At Least an Hour Or Two
Developing Classes, Working With
Constructors, Destructors, Function
Overloading, Etc.

OOP 2 HW
Do Some Of OOP2 Homework
In Preparation For Quiz

# 3

9/4

R

OOP 2 Slide

Finish OOP 2 HW

Athlete Class Lab

# 4

9/9

T

# 5

9/11

R

# 6

9/16

T

Single Linked List - Direct Access File Implementation

Why Direct Access Files?
Why Direct Access Files, As Opposed To Text Files?
Download Application
Visual Studio Projects Re-visited
Execute Binary Outside Visual Studio Net Environment
Redirecting Output To A Text File
Other Files In The Debug Folder
fopen & fclose- Open To Create New File Close File (wb+)
fseek – moving the Read-Write Pointer
fwrite – Writing Direct Access Records
fopen & fclose- Open To Create New File Close File (rb+)
fread – Reading Direct Access Records
Generic Template ReadRecord, WriteRecord, & FileLength

FILE  *FilePtr;
FilePtr = fopen (NewFileName,"rb+");
FilePtr = fopen (NewFileName,"wb+");
fseek(FilePtr, 4 * sizeof(Student), SEEK_SET);
fwrite(&Students,sizeof(Student),(long)1,FilePtr);
fread(&Students,sizeof(Student),(long)1,FilePtr);

Optional
Chap08
TextFiles

Optional
Chap11
Direct Access File

# 7

9/18

R

# 8

9/23

T

Introduction To The Direct Access File
Implementation Of A Double Linked List

Generic Design

ListHeader Class
DLNode Class
Inheritance
PartListHeader Class
AutoListHeader Class

 

# 9

9/25

R

# 10

9/30

T

# 11

10/2

R

# 12

10/7

T

# 13

10/9

R

Inplace
InsertAfter

KeyTable
Key - Ptr
AddKeyToTable
DeleteKeyFromTable

# 14

10/14

T

How To Compute # Read/Writes Per Second
Optimized Drive
Fragmented Drive

Structure : One Unordered File For Data
Compute Average/Worst Search Time
Compute Average/Worst Add Time
Compute Average/Worst Delete Time

Structure : One Ordered File For Data
Must Alwasy Be Maintained In Order
Compute N*N Sort Time
Compute NLogN Sort Time
Compute Average/Worst Search Time
Compute Average/Worst Add Time
Compute Average/Worst Delete Time

Structure : Double Linked List File File For Data
Assume 100 Evenly Distributed Headers
Compute Average/Worst Search Time (if know which header)
Compute Average/Worst Search Time (if don't know which header)
Compute Average/Worst Add Time (if know which header)
Compute Average/Worst Delete Time (if know which header & Ptr)

Structure : Double Linked List File File For Data
KeyTable(s) Available For All Search
Assume 100 Evenly Distributed Headers
Compute Average/Worst Search Time

Introduction To Binary Trees
Balanced Tree
Complete Tree
Skew Tree
Start BinTree application.
 

# 15

10/16

R

SetLeft
SetRight
Inplace

Inorder Traversal
PreOrder Traversal
PostOrder Traversal

Board Work
Single Linked List
Double Linked List
Circular Linked List
Double Circular Linked List
 

# 16

10/21

T

Binary Tree Applications
InOrder Traversal
PreOrder Traversal
PostOrder Traversal 

Non-Recursive Tree Traversals

Left InThreaded Binary Tree
General Tree

Figuring Binary Tree Distribution
Skew To Balanced  

# 17

10/23

R

# 18

10/28

T

Planar Graphs
Problems with Adjacency Matrix Solutions
E-Mail & Airline Reservation
IP Addresses ==> 4,294,967,296
Adj Matrix ==> 4,294,967,296 x 4,294,967,296 =
18,446,744,073,709,551,616 cells
Sparce - Dense - Graph
Vertex Adjacency
Vertex Connectivity
Adjacency List
Creating Adjacency Lists
Data Inputs
Data Dictionary
Build Adjacency List For
Shortest Path
Dijkstra's Algorithm
 

# 19

10/30

R

Delete-DeleteTree
Due 11/4

# 20

11/4

T

# 21

11/6

R

 
AVL Trees
Two Russians named Adelson-Velskii and Landis.

An empty tree is height balanced.

For a tree T, T-L shall denote the left subtree and T-R shall denote the right subtree.

For a tree T, h-L shall denote the height of the left subtree (T-L) and h-R shall denote the height of the right subtree (T-R).

A non empty binary tree is HEIGHT BALANCED if and only if
T-R and T-L are height balanced
-1 <= (h-L) - (h-R)| <= +1

The BALANCE FACTOR of a node T in a binary tree bf(T) = h-L - h-R.

 For any node T in an AVL tree, bf(T) = -1, 0, or +1

Introduction To AVL Trees
Rotate Left
 

AVLTrees

RotateLeft

RotateRight

DoubleRotateRight

# 22

11/11

T

# 23

11/13

R

AVL Trees
Two Russians named Adelson-Velskii and Landis.

An empty tree is height balanced.

For a tree T, T-L shall denote the left subtree and T-R shall denote the right subtree.

For a tree T, h-L shall denote the height of the left subtree (T-L) and h-R shall denote the height of the right subtree (T-R).

A non empty binary tree is HEIGHT BALANCED if and only if
T-R and T-L are height balanced
-1 <= (h-L) - (h-R)| <= +1

The BALANCE FACTOR of a node T in a binary tree bf(T) = h-L - h-R.

 For any node T in an AVL tree, bf(T) = -1, 0, or +1

Introduction To AVL Trees
Rotate Left
Rotate Right
Double Rotate Left
Double Rotate Right
 

# 24

11/18

T

B Tree Requirements
M-Way Tree
Searching A B Tree
M = 5 Data Split -Two Levels
M = 5 Data Split - Three Levels
Size Of A B Tree Node
Calculating M For A Given Buffer Size & Info Size
2 Files - Header File & Node File

B+ Tree Requirements
M-Way Tree
Searching A B+ Tree
M = 5 Data Split -Two Levels
M = 5 Data Split - Three Levels
Size Of A B+ Tree Node
Calculating M For A Given Buffer Size & Key Size &  Info Size
3 Files - Header File & Node File & Data File

Difference Between A B Tree & A B+ Tree
Search Efficiency
At Least 1/2 Full - Average 3/4 Full - Max = 4/4 Full
No Reads & Writes

Demo With FoxPro Database 

# 25

11/20

R

# 26

11/25

T

# 27

11/27

R

# 28

12/2

T

# 29

12/4

R

# 30

12/9

T

12/10
12/11