Principles Of Data Abstraction
CSCI 2320 -  Fall 2009 - Tentative Schedule - 9:55 TT

All Labs/Assignments Are Due The Next Class Period Unless Specified Otherwise!

 Class 

Topic's)

 Reading Assignments 
& Handouts

 Laboratory 
Assignments 

 

# 1

8/27

R

  
Introduction To Class
Fill Out Questionnaire (Lab I-4 points)
Discuss Course Outline

Review C & Start To Introduce C++

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
 

 Read the Course Outline

OOP 1 Slides 

 Questionnaire HW

Install Visual Studio 2008 On Your Computer

Visual-Studio-2008-SP1
(Optional Install)

OOP-1-HW.

 

# 2

9/1

T

 
OOP 2

Review C Pointers

Aggregates : arrays, structs, classes
Student Struct - Set Function
Student Class - Set Method
Classes,
Member Functions = Methods
Class Data Members
Class Function Prototypes
Encapsulation
Constructors,
Destructors
public vs. private
scope operator
Function Overload
Function Signature
Default Arguments
 

 OOP 2 Slides

Dorm-Configuration

Simple Sort Lab 

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

 

# 3

9/3R

 

 

OOP 2

Classes,
Member Functions = Methods
Class Data Members
Class Function Prototypes
Encapsulation
Constructors,
Destructors
public vs. private
scope operator
Function Overload
Function Signature
Default Arguments
Memory Leaks
Mutator Method
Accessor Method
ADT - Abstract Data Type
Operator Overloads
>, >=, <, <=, ==, !=, =

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

Indigenous Data
Exogenous Data
Standard Template Library  
 

 OOP 2 Slides OOP 2 HW

Athlete-Class-Lab
Do All But
Operator Overloads

 

# 4

9/8

T

 

  

Partitioning Applications Into .hpp and .cpp files.
Classes Continued!

Partition Athlete Class
Overloaded Constructor
Overloaded Set
Destructor
Get
Overload <<
Overloaded Display
Overload Operators
 >, >=, <, <=, ==, !=, =

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

  

Athlete-Class-Lab
Extra Credit If Use hpp & cpp

 

# 5

9/10

R

 

 Partition Athlete Class
Review Classes
Templated Stack Class		 Stack Slides  Stack Lab I

 

# 6

9/15

T

 

 Templated Queue
Copy Constructor
Overload =
Resize

Start Direct Access Files

 Queue Slides Stack Lab II

 

# 7

9/17

R

 
Direct Access Files

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);
  

Direct Access Files

Optional
 Chap08
 TextFiles

Optional
 Chap11
 Direct Access File  

 Athlete-Direct-Access-Time-1 Lab

 

# 8

9/22

T

 


This Material Not On Exam I

Develop Heder Class - PartHeader - Inherits ListHeader

Double Linked List Application

Organize DLNodes For Insertion-Deletion
Available Pool
 

Direct Access Double Linked List
Constructor For New App
Constructor For Existing App

Trace/Sketch Available Pool
Trace/Sketch A Specific Header 

   Study For Exam 1
Extra Credit If You Do Study Group
For 3 Hours Or More

 

# 9

9/24

R

 

 Exam I   Athlete-Direct-Access-Time-2 Lab

 

# 10

9/29

T

 
DA_DLList Class
Direct Access Double Linked List
Constructor For New App
Constructor For Existing App

Trace/Sketch Available Pool
Trace/Sketch A Specific Header

CreateHeaderFile
CreateNodeFile
GetNode, FreeNode 
Hicks-Num-DA-DLList

Hicks-Inventory-DA-DLList

New-Constructors-DA-DLList

GetNode-Available-Pool-DA-DLList

FreeNode-Available-Pool

 

 DLList-1-DirAcc-Const-Dest-GetNode-FreeNode Lab

 

# 11

10/1

R

 

 DLList Class
 Internal Memory Dynamic
Array Solution

Using A Double-Linked-List as a Stack
bool Push (HeaderNo, NewInfo)
bool Pop (HeaderNo, &OldInfo)
bool Empty(HeaderNo)

 Graphical View
Of DA-DLList		 DLList-2 Lab
Individual Assignment Due
10/9

 

# 12

10/6

T

 

 Work In Class
Coin-Class Lab
Team Assignment		 Graphical View
Of DA-DLList		 Coin-Class-Lab
Team Assignment Due
10/9

 

# 13

10/8

R

 
Review DLList vs DA_DLList
bool Pop (HeaderNo, &OldInfo)
Translating Internal Memory
Solutions Into Direct Access File Solutions

Using A Double-Linked-List as a Queue
bool Insert (HeaderNo, NewInfo)
bool Remove (HeaderNo, &OldInfo)
bool Empty(HeaderNo)

Using A Double-Linked-List as an
Ordered Linked List
bool Inplace (HeaderNo, NewInfo)
bool InsertAfter (HeaderNo, NewInfo, LeftBrother)
 

 Graphical View
Of DA-DLList		 DLList-3 Lab
Individual Assignment Due
10/15

 

# 14

10/13

T

 
Using A Double-Linked-List as an
Ordered Linked List
bool Inplace (HeaderNo, NewInfo)
bool InsertAfter (HeaderNo, NewInfo, LeftBrother)
 

Brief Description Of
NodePtr Search(long int HeaderNo, long int SoughtValue)
NodePtr Search(long int HeaderNo, char SoughtValue[])
bool Delete(long int HeaderNo, long int RecordNo);
 

    

 

# 15

10/15

R

 
Key Tables
Internal Memory Array
KeySets (Key, Ptr)
Binary Search Of Internal Memory Array
Add Rapid Search Functionality To
DA_DLList

Key Table
AddKeyToTable
DeleteKeyFromTable
Performance Enhancement

Introduction To Trees
 

   DLList-DirAcc-OrderedList Lab
Individual Assignment Due
10/20

 

# 16

10/20

T

 

 Review   BinTree_Lab I

 

# 17

10/22

R

 
Binary Tree
BinTree Class
Skew Tree
Complete Tree
Balanced Tree

Binary Tree Traversals
InOrder Traversal
PreOrder Traversal
PostOrder Traversal 

Non-Recursive Tree Traversals

Left InThreaded Binary Tree
General Tree

Figuring Binary Tree Distribution
Skew To Balanced  


3 Binary Tree Deletion Strategies
 1-Lazy Deletion (may not use)
2-Extend-Level Deletion (80% credit)
3- Bubble-Up Deletion (100% Credit)
 

 BinTreeTraversals

BinTree-1-First-Last.zip

DA-BinTree-1-First-Last.zip 

 STUDY FOR
EXAM

 

# 18

10/27

T

 

 Exam II    

 

# 19

10/29

R

 
Go Over Exam

Discuss Binary Tree Deletion
Discuss Calculations Of
Average Search & Worst On DA_BinTree
Review KeyTables

Discuss NoNodesAtEachLevels & Calculation
Of AverageBinaryTree Search Time

C#-DotNet Programming
Web Browser Application
 

   BinTree-Delete-Stats-Levels Lab
Team Assignment Due
11/5 

 

# 20

11/3

T

 


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

  

 

# 21

11/5

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

 		 DA_AVL Lab I
Team Assignment Due
11/12

 

# 22

11/10

T
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
 

 B+Tree  B+Tree - HW 

 

# 23

11/12

R

 

 B+ Trees & MySQL Database

Quiz AVL - B/B+ Trees

   DA_AVL Lab II

Team Assignment
Extra Credit If Completed Correctly By 11/25
Due 12/1
 

 

# 24

11/17

T

 
Graph Theory

 Define Graph G = (V,E)
Verticies (V) - Nodes
Edges (E) - Arcs
Adjacency
Connectivity
Undirected Graphs
V = {A, B, C, D, E}
E = { (A,B), (A,D), (A,E), (B,E) }
Sketching Graphs
Directed Graphs
V = {A, B, C, D}
E = { (A,B), (A,D), (A,E), (B,E) }
Sketching Graphs
Directed Graphs
V = {A, B, C, D}

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
  

 GraphTheory1

 GraphTheory2		 Graph-Theory-HW-1

 

# 25

11/19

R

 

 Dijkstra Algorithm
Adjacency List

Introduction To Hashing

 Hashing  

 

# 24

11/24

T

 

 Thanksgiving
Week

Individual Assignment

    

 

# 25

11/26

R

 

 Thanksgiving
Week		    

 

# 26

12/1

T

 

      

 

# 27

12/3

R

 

 Exam III    

 

# 28

12/8

T

 

      

12/9
12/10

 Reading Days Reading Days

 

 

 
 

No assignments will be accepted after 12/11 Noon