Intro to File Processing, Computer Systems,

and C language programming

Outline:

Introduction ( Notes 1 )

• Bibliography
• Organizational Issues

Overview ( Miller 1, Claybrook 1 --- Notes 2 ):

• What is it?
• Where does it fit?
• Why study it?
• Who uses it?

An introduction to C ( K & R/Deitel, Notes 3 ):

• development of C
• basic syntax
• some key differences from Pascal
• C pointer, structure, union, and file syntax

An introduction to C++ ( Notes )

• Object-oriented programming in general
• C++ structure and class syntax and semantics
• Inheritance and protection
• Differences between C and C++

Quick review of records & files (Miller 2 & App B, K & R/Deitel, Notes ):

• layout of records in memory
  • variant records
  • Pascal record and file syntax
  • C structure and union syntax (review)
  • C++ class syntax introduction)

Writing code for large applications: Software engineering issues

• Supplement, ( Notes )
  • Types, pseudocode, interfaces, general nonsense
  • Modularity, reuse
  • Maintenance

Software engineering and secondary memory ( Notes 4 )

Blocking and Buffering ( Miller 3, Notes 5 )

• Record layout, blocks in general, simulating blocks in Pascal or C

Complexity ( Notes 6 )

Architectural Issues:

• Connection of file structures to architecture (supplement)

Secondary storage devices (Miller 4, Claybrook 2, supplement, Notes 7 )

• tapes
• drums, disks and floppy disks
• other secondary memory devices(Notes 8)
  • word-addressable media
    • core storage (LCS)
    • charge-coupled devices (CCD)
    • magnetic bubble memory (MBM)
    • optical storage
  • mass stores
    • juke boxes of tapes and CDs, CD packs
• block-addressable devices in general

The UNIX operating system

• development of UNIX
• basics of UNIX
  • basic commands, basic operations
• personalizing your environment
• shell programming
• the C-UNIX interface
• editors
  • vi
  • emacs

Time and Space computations (Miller 4)

System-defined/supported file structures:

Sequential Files (Miller 5, Claybrook 3.3)

• costs and algorithms

Direct Files (Miller 7, Claybrook 3.5, supplement --- Notes9

• direct, dictionary, hash-table organizations; costs and comparisons

Indexed Sequential Files (Miller 9, Claybrook 3.4, 3.7 --- Notes10)

• ISAM, VSAM, SIS; costs and tradeoffs

Algorithmic Issues (Claybrook 4, mostly supplement -- Notes11)

• Structural/inductive definition, recursion, induction, proof
• inductive property definitions(examples)
• Complexity and analysis
• Dynamic programming and applications

User-defined tree-based file structures

• Binary tree structures (Miller 8, Claybrook 4, supplement -- Notes12)
  • binary search trees, balanced trees, AVL trees
  • k-way trees (Miller 8, Claybrook 4, supplement)
    • B-trees and related structures
  • hierarchical tree structures (Claybrook 4, supplement)
    • multi-level binary trees, k-d trees

User-defined graph-based file structures

• multikey structures (Miller 10, Claybrook 5, supplement --- Notes13)
  • multirings
  • multilists
  • inverted lists
  • hybrid structures

Introduction to databases (Miller, Claybrook, supplement --- Notes14)

• database tables as file structures
• table as type + access + interface
• multiple linked tables, normalization, representing external pointers
• queries
  • types of queries
  • normal forms
  • optimization
• interaction with file structure, keys, memory layout
• Dynamic Programming

Merging and sorting (Claybrook 7, Miller 6, supplement --- Notes15)

• review of merging, searching, sorting;
• external merge and sort

Systems programming and file management (Claybrook 6, 8)

• Unix file descriptors