Catalog Description:

Hardware characteristics of storage devices. Basic file organizations including sequential, direct, and indexed sequential; hashing and collision resolution; perfect hashing; signatures; bloom filters; sorting and other bit level structures. Tree structures including binary search trees, B-trees, and trees. Dynamic hashing techniques. Structures including grid files. Applying file structures to practical problems.

Contact Hours:

• Lecture: 3 hours

Prerequisites: CSC230 or ECE209 and CSC316 or ECE309
Co-requisites: None
Restrictions: None
Coordinator: Dr. Rada Chirkova
Textbook: Disk Based Algorithms for Big Data

Course Outcomes:

Upon successful completion of this course, a student will be able to:

1. learn about how information is maintained on external storage devices, both in physical and logical contexts
2. learn how to use order notation to describe an algorithm’s space and execution efficiency
3. study the strengths and limitations of a number of common in-memory searching and sorting algorithms
4. study the strengths and limitations of a number of common external searching and sorting algorithms

Topics:

• Physical Disk and Storage Basics
• Order Notation
• Logical File Organization
• Sequential and Direct File Access
• File-Management Strategies
• File Indexing
• Internal Sorting Algorithms
• Internal Searching Algorithms
• External Sorting Algorithms
• External Searching Algorithms
• Hashing
• Distributed Hash Tables
• (time permitting) Signature Files