Class 

Topic's)

 Reading Assignments 
& Handouts

 Laboratory 
Assignments 

# 1

1/17

R

Basic Data Types
Range Of Acceptable Values
sizeof, limits.h
declarations,
initializations,
assignments
printf - control string
scanf - control string
puts, gets
constants vs variables
Documentation
Modules/Function Design
program components
Pass By Reference/Value
Modules with Pointers
Modules with Reference Variables

Stream Input - Output
cout << "\nEnter No";
cin >> No;
cin >> FirstName;
cin.getline(FullName);

String Functions
strlen, strcmp, strcpy
 

OOP 1 Slides

Questionnaire HW

OOP-1-HW.

Elementary Sort Lab

Install Visual Studio 2005

# 2

1/22

T

interface
class to hpp & cpp
#ifndef, #endif
4 Reasons To Create
.hpp & .cpp Class Interface

Indigenous Data
Exogenous Data
Standard Template Library
 

Do as much as you can from
OOP 2 HW
Due 1/32

# 3

1/24

R

Review .hpp .cpp Files
Examine Test Code
 

# 4

1/29

T

Dynamic Memory
Shallow Copy
Deep Copy
LIFO & FIFO
Array Implementation Of A Stack
Dynamic Stack
Templates
Template Stack
Primitive Operations
Push, Pop, Empty
Full

 

Stack Lab
Do Push, Pop, Empty
Tonight
Due 2/5

# 5

1/31

R

Memory Management

# 6

2/5

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);
fclose(FilePtr);

Optional
Chap08
TextFiles

Optional
Chap11
Direct Access File

# 7

2/7

R

UnOrdered List - Average Search, Worst Search,
Average/Worst Insertion, Average/Worst Deletion

Sorting The UnOrdered List - N*N, NLogN

Ordered List - Average Search, Worst Search,
Average/Worst Insertion, Average/Worst Deletion

void CreateHeaderNodes(char HeaderFileName[],  
long int NoHeaders = 6);
	void CreateNodes(char NodeFileName[], 
long int NoNodes);

# 8

2/12

T

Constructor To Create New Data Structured Files
DA_DLList(char HeaderFileName[], char NodeFileName[], 
	    long int NoHeaders, long int NoNodes);

Constructor To Use Previously Created Data Structured Files
DA_DLList(char HeaderFileName[], char NodeFileName[]);

SimpleFileOutput.txt 

# 9

2/14

R

DLList - Average Search, Worst Search,
Divide & Conquer

Using A Double Linked List as a Stack
	bool Empty (long int HeaderNo);
bool Push (long int HeaderNo, InfoType NewInfo);
bool Insert (long int HeaderNo, InfoType NewInfo);

Internal Memory DLList - Internal Memory Array Implementation

template <class InfoType, class HeaderType>
class DLList 
{
public:

    DLList(long int NewMaxHeaders  = 4, long int NewMaxNodes = 10);
	void CreateHeaderNodes(char HeaderFileName[],  
                                        long int NoHeaders = 4);
	void CreateNodes(char NodeFileName[], 
                                       long int NoNodes = 10);

    ~DLList(void);

    NodePtr GetNode(void);                                      
    void FreeNode(NodePtr OldNodePtr);
	bool Empty(long int HeaderNo);

	bool Push(long int HeaderNo, InfoType NewInfo);
	bool Pop(long int HeaderNo, InfoType &OldInfo);

	bool Insert(long int HeaderNo, InfoType NewInfo);
	bool Remove(long int HeaderNo, InfoType &OldInfo);

	bool InsertAfter(long int HeaderNo, InfoType NewInfo, 
                                            NodePtr LeftBrother);
	bool Inplace(long int HeaderNo, InfoType NewInfo);

    void DisplayHeaders(char Message[] = "", bool pause = true);
    void DisplayNodes(char Message[] = "", bool pause = true);   
    void Display(char Message[] = "", bool pause = true);  

private:	

    DLNode <InfoType> 
		*Nodes;
    HeaderType
		*Headers;
    NodePtr 
		Avail;
    long int 
		MaxNodes, 
		MaxHeaders;	
};	

CreateNodes, CreateHeaders, GetNode, FreeNode
Using A Linked List As A Stack
Push, Pop, Empty

Study For Exam !

# 10

2/19

R

Using A Linked List As An Ordered List
Push, Pop, Empty
Insert, Remove, Empty
InsertAfter, Inplace

# 11

2/21

R

# 12

2/26

T

Translating DLList Constructor, Destructor, GetNode,
Freenode, & Push into a
Direct Access File Model for DA-DLList

# 13

2/28

R

Circular Linked List
Double Circular Linked List
Single Linked List
Double Linked List

Algorithm Analysis

# 14

3/4

T

Single Linked Lists vs.
Double Linked Lists vs.
Circular Linked List vs.
Double Circular Linked Lists

# 15

3/6

R

Infix, Prefix, Postfix

Infix-Prefix-Postfix-HW

# 16

3/11

T

BinTree Class
SetLeft
SetRight
Inplace

Recursive Inorder Traversal
Recursive Inorder Traversal
Recursive Inorder Traversal
 

# 17

3/13

R

Non-Recursive Traversals
Tree Searching

# 18

3/18

T

# 19

3/20

R

# 20

3/25

T

Deletion From Binary Tree
Lazy Deletion,
Bubble Up Deletion,
Major Shift Deletion

Recursive Delete(HeaderNo) 

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

# 21

3/27

R

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

Practice Timing
Spreadsheet

# 22

4/1

T

# 23

4/3

R

Go Over Exam

Introduction To B Trees & B+ Trees

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 

# 24

4/8

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

4/10

R

Project Work Day

B+Tree - HW

# 26

4/15

T

# 27

4/17

R

# 28

4/22

T

# 29

4/24

R

# 30

4/29

T

# 31

5/1

T

M 5/5
T 5/6