Data Abstractions
CSCI 2320 -  Fall 2018 - Tentative Schedule - 12:45 TT

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

# Topic(s) Reading Assignments
 & Handouts
Laboratory Assignment

#1

8/23

TH



Introduction To Class
Discuss Course Outline

------------ Review Divided Into 3 Parts ------------

Review-Basic-Data-Types PPS  PDF 

Review-Arrays-Strrings
PPS  PDF

Review-Functions-Memory-Maps PPS  PDF


Note:
The PDF files are SEARCHABLE
The PPS files contain ANIMATION

 Course Outline

Project-2017.zip

Visual-Studio-Installation

Questionnaire

------------ Review Divided Into 3 Parts ------------

Review-Basic-Data-Types  HW

Review-Arrays-Strrings  HW


# 2

8/28

TU


Review
 

Review Functions & Memory Maps

Dynamic Memory
Create Dynamic Memory Ptrs
Initialize Ptrs To NULL
Acceptable Range Of Pointer Values
Validate Memory Allocation
malloc & free
new & delete
Allocate A Dynamic Array
Free A Dynamic Array
Allocate A Ptr To A Struct
Access Struct Variables
(*Ptr).field =
Ptr->field =

Review-Functions-Memory-Maps PPS  PDF

OOP-1-Pointers-Dynamic-Memory-Slides  PPS  PDF

Review-Functions-Memory-Maps  HW

# 3

8/30

TH


Quiz 1 ==> 3 Review HW A, B, & C

Dynamic Memory
Create Dynamic Memory Ptrs
Initialize Ptrs To NULL
Acceptable Range Of Pointer Values
Validate Memory Allocation
malloc & free
new & delete
Allocate A Dynamic Array
Free A Dynamic Array
Allocate A Ptr To A Struct
Access Struct Variables
(*Ptr).field =
Ptr->field =


Introduce Classes
Function Overloading
End Of String Marker '/0'
Aggregates : arrays, structs, classes
Student Struct - Set Function
Intro To Classes
Student Class - Set Method
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
>, >=, <, <=, ==, !=, =
Testing
Function Signatures
Scope
ADT - Abstract Data Type

 

 


OOP-1-Pointers-Dynamic-Memory-Slides  PPS  PDF

OOP-2-Classes-  Slides  PDF

 

OOP-02-Classes-Slides-A.pdf

OOP-02-Classes-Slides-B.pdf

OOP-02-Classes-Slides-C.pdf

Code The Book Class
Test Your Functions
Put All The Code In main.cpp
Use My Test Code

# 4

9/4

TU

 

Classes

Function Overloading
End Of String Marker '/0'
Aggregates : arrays, structs, classes
Student Struct - Set Function
Intro To Classes
Student Class - Set Method
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
>, >=, <, <=, ==, !=, =
Testing
Function Signatures
Scope
ADT - Abstract Data Type

 


OOP-02-Classes-Slides-A.pdf

OOP-02-Classes-Slides-B.pdf

OOP-02-Classes-Slides-C.pdf

OOP-03-Interface-Slides  Slides  PDF



OOP-03-Interface-HW



# 5

9/6

TH


Templates
Create Swap Function
template <class T>
template <class InfoType>
C++ Also Supports Generics
Templates - Pattern For What Shall Become A Function
Templated Function Generated At Run Time
Templates With Multiple Parameters
Templated ListType
Constructor & Destructor

Start Stack

 

 

OOP-04-Templates  Slides PDF

TomH-ListType-Student.zip

 

OOP-4-Templates-ListType-Dynamic-Memory-HW

# 6

9/11

TU

 

Quiz 2 ==> On Interface & Classes

Stacks
ADT - Abstract Data Type
LIFO - Last In First Out
FIFO - First In First Out
Stack & Queue
Push, Pop, Empty
StackTop, Resize, Full
Copy Constructor, operator = Overload
Stack Design I - Static Array
Stack Design II - Dynamic Array
Stack Design III - Templates
Help With Resize
 
 

OOP-05-Stack   Slides  PDF

TomH-Stack-Student.zip

OOP-05-Stacks-HW

# 7

9/13

TH

Review Stacks On Board

Discuss Direct Access
vs.
Sequential Text Files
In Software Engineering
 

OOP-6-DA-File  Slides  PDF


--- Optional ----


Chap08-TextFiles
Chap11-DirectAccessFiles


Spend At Least 4 Hours
Reviewing Slides

Write Several Practice Programs
That Create, And Then Read,
Direct Access Files

Create A Direct Access File Of Integers
Create A Direct Access File Of Parts
Practice fseek, fread, & fwrite

Review Text Files, If You Have
Forgotten Them

# 8

9/18

TU

 

Quiz 3  ==> On ListType & StackType

Direct Access Files
open, close
frets, puts
printf, scanf
format specifications for into, unsigned into, hex,
floating point, double, char, & string
Why We Need Direct Access Files
Direct Access vs. Text Files
dir & ls
open modes web+ & rib+
buffered file system

seek (Filet, No Bytes, SEEK SET)
fseek(StudentFil, 4 * sizeof(Student), SEEK_SET);

fwrite(&Info, InfoSize(byes), # records, fp);
fwrite(&NewStudent, sizeof(Student),(long)1,StudentFil);

fread(&Info, InfoSize(byes), # records, fp);
fread(&NewStudent,sizeof(Student),(long)1,StudentFil);

Develop Generic FileLength
Develop Generic ReadRecord
Develop Generic WriteRecord

 

OOP-07-Direct-Access-Functions-HW
Due 9/25


Do at least 3 Hours Before Thursday!



# 9

9/20

TH


DLNode Class
ListHeader Class
ListHeader Inherited
PartListHeader, StudentListHeader,
AutoListHeader, IntegerListHeader, etc.

DLList Class
Constructor, Destructor
CreateHeaderNodes,
CreateNodes
GetNode

About The Available Pool Of Nodes
Generally Single Linked

 

OOP-08-DA-DLList  Slides  PDF

TomH-DLList-Student.zip
OOP-08-DLList-1-HW
Diagnostic Levels 1-11
Due 10/4

# 10

9/25

TU

 
Quiz4 ==> On DAFiles

DLList Class
Constructor, Destructor
CreateHeaderNodes,
CreateNodes
GetNode
 
OOP-08-DA-DLList  Slides  PDF

TomH-DLList-Student.zip
OOP-08-DLList-A-HW
Due 10/4

# 11

9/27

TH

 
DLList Class
FreeNode
ValidHeader
ValidNode
Push
Pop
Empty
Insert
Remove
 

OOP-08-DA-DLList  Slides  PDF
STUDY FOR EXAM
Material SInce Last Exam +
DLList Constructor, Destructor,
GetNode, & FreeNode On Exam

# 12

10/2

TU


 Exam I


 

 

Get a Copy Of DA-DLList
Do Constructor, Destructor,
GetNode, FreeNode


# 13

10/4

TH


DLList Class
ValidHeader
ValidNode
InsertAfter
Inplace


 OOP-08-DA-DLList  Slides  PDF

   TomH-DA-DList-1-Student.zip

OOP-08-DLList-A-HW
Levels 1-18
# 14

10/9

TU

 

DA-DLList Class
Constructor & Destructor
Conversation

Software Engineering DA_DLList
STL

Key Tables
KeyTable + Direct Access Doubly Linked List
KeyTable --> Internal Memory Array Of Key-PTR
Written To File In Destructor
Read From File In Constructor

 

OOP-08-DA-DLList  Slides  PDF


TomH-DA-DList-1-Student.zip
OOP-08-DA-DLList-1
 Due 10/5

# 15

10/11

TH

 

Quiz 5 ==> On DLList

BinTree Internal Memory Solution
Constructor
Destructor
CreateNodes
CreateHeaders
GetNode
FreeNode
ValidHeader
ValidNode

SetLeft
SetRight
Inplace

 

TomH-BinTree-Student.zip OOP-08-DA-DLList-2-HW

# 16

10/16

TU

 
Skew Tree
Balanced Tree
Complete Tree

Inorder Traversal
PreOrder Traversal
PostOrder Traversal

Practice Direct Access Functions On Board
 

   
TomH-BinTree-Student.zip


OOP-08-DA-DLList-3-HW

# 17

10/18

TH

 
  Quiz 6 ==> On DA_DLList
 
Delete On Tree
(Not Accept Lazy Deletion)
(50% Credit For Poor Deletion)
(100% Possible For Good Deletion)

 No Nodes At Each Level

START AVL Trees
 



TomH-DA-BinTree-1-Student.zip

   
OOP-09-DA-BinTree-1-HW

# 18

10/23

TU

     
  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
 

 



AVLTrees

RotateLeft

RotateRight

DoubleRotateRight



   
OOP-09-DA-BinTree-2-HW

Do NoNodesAtEachLevel
  Do LoadBalanceStatistics:
     No Nodes ...........= xxxxxxxxxxxx
     No Levels ..........= xxxxxxxxxxxx
    Total Searches .....= xxxxxxxxxxxx
 Average Search .....= xxxxxx.xx
 LOG2(NoNodes).......= xxxxxx.xx 

# 19

10/25

TH

 
  Quiz 7==> On BinTree & DA_BinTree

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
  

 

AVLTrees

RotateLeft

RotateRight

DoubleRotateRight






OOP-09-DA-BinTree-3-HW

Do NoNodesAtEachLevel

# 20

10/30

TU


B Trees & B+ Trees


BTrees-Slides.pdf

OOP-09-DA-BinTree-4-HW
Due 11/6

Rebalance Tree

# 21

11/1

TH

 Exam II



   



# 22

11/6

TU

 
Hashing
Minimum Standards
Access Quotient = 1.2 (or better)
Loading Factor = 80% (or better)
Hash Clash
Collision
Clustered Data

Address Calculator
Building Hash Function
Modulus
Folding
Truncation
String - Maybe ASCII?
Think Prime

Collision Resolution Techniques
Linear Probing
Quadratic Probing
Linked List Overflow
Binary Tree Overflow



   
In-Class Lab 15 Points
Put Solution In Your To Be Graded Folder On Mars

# 23

11/8

TH

   
DBMS
Log Into MySQL

SHOW DATABASES
CREATE DATABASE
DROP DATABASE
USE
CREATE TABLE
DROP TABLE
DESCRIBE
SHOW FIELDS IN
SELECT * vs SELECT x,y,z
 
TomH-DA-AVL-Tree-Student.zip

OOP-15-AVL Final Project-1-HW
Due 11/15


# 24

11/13

TU

 
  Quiz 8==> On Hashing + AVL

TINYINT, SMALLINT, MEDIUMINT,
BIGINT, CHAR, VARCHAR, BLOB,
MEDIUMBLOB, LONGBLOB,


COUNT(*) vs COUNT(First)
SELECT ... WHERE
LIKE "X%"
ORDER BY
LIMIT
SELECT 2 * 3 + 5
SELECT POW()2,8)
CONCATENATE ("ABC", "DEF")
LEFT ("Trinity", 2)
RIGHT
 ("Trinity", 2)
UPDATE

DATE, TIME, TIMESTAMP, YEAR
SELECT CURDATE() --> MYSQL
SELECT CURTIME()
--> MYSQL
HOUR(X), MINUTE(x), SECOND(x)
DAY(x), MONTH(x), YEAR(x)
 


   

 

OOP-15-AVL Final Project-1-HW
Due 11/15

MySQL1-HW
Due 11/29


# 25

11/15

TH

 


   

OOP-15-AVL Final Project-2-HW
Due 11/27


# 26

11/20

TU


Work Independently On Project




   
 

# 27

11/22

TH


THANKSGIVING
 
 

# 28

11/27

TU








Database Homework


# 29

11/29

TH


 Exam III
   

# 30

12/4

TU

  

 Last Day To Submit Any Late Homework
Noon on 12/5

 Red Black Trees
General Trees





 


R

12/5

W





    READING DAY






    READING DAY






    READING DAY



R

12/6

TH





    READING DAY






    READING DAY






    READING DAY


+

No Assignments Will Be Accepted After Noon on 12/5