---

CIS 350

Data Structures and Algorithm Analysis

Lecture Notes

---

Course Overview

• Data Structures
  
• Algorithms
  
• Software Design
  
• Data Abstraction
  

Abstract Data Types (ADT's)

• Specify ADT
• Representation
• Data type - bindings
• Type declaration statement

Built-in Types

• Static Type Checking
• Dynamic Type Checking
• Storage Management
  Allocation, garbage, dangling reference
  
• Elementary Built-in Types
  char,Boolean,integer,real

Structured Types

• Implentation and Operations
• Arrays, Records, Strings

Object-Orinted Programming

• Abtract Data Types
• Inheritance
• Templates

Stacks

• Attributes and Operations
• Array Implementation

Queues

• Attributes and Operations
• Array Implementation

Program Complexity

• Complexity
  • Efficiency
  • Best/Worst/Average Case Performance
  • Units - Big Oh/Omega/Theta
• Rules for Order Arithmetic
  • Multiplicative constants
  • Addition/Multi. Rules

Complexity Examples

Complexity Computation Heuristics

More Complexity Examples

• Nested Loops
• goto's

Recursion

• Recursive Algorithms
• Recursive Data Structure

Simulating Recursion

• Parameter Transmission
• Storage
• Transfer Control - Exit, Entry

Pointer Variables

• Address Operator
• Output
• Pointers and Structs

Singly Linked Lists

• Basic Operations
• Array Implementation

Linked List Operators

• Removing Nodes
• Inserting Nodes
• Pointer Implementation

• Ordered/Unordered Lists
• Internal/External Searches
• Adding/Deleting Array Elements
• Array vs. Stack
• Ordered Lists

Hash tables

• Hashing Functions
• Library Example
• Collisions
• Clustering
• Displacement
• Collision Resolution
  • Linear Probing - Succesful/Unsuccessful
  • Quadratic Probing - Successful/Unsuccessful

Hash Collision Resolution and Complexity

• Strategies
  • Linear Probing
  • Buckets
  • Chaining
• Complexity of Hashing - Insert/Delete/Member
• What affects runtime?
  
• Sample Hashing Functions
  
  

Trees

• Tree Variations
• Class BinTree

Binary Search Tree(BST)

• Class BST

Tree Traversals

• Inorder
• Preorder
• Postorder
• Threaded Trees

AVL Trees

• LL Rotation
• LR Rotation

Additional Trees

• Priority Queues
• General Trees
• Tries

B-trees

Graphs

• Terminology Review
• Isomorphic vs equal graphs
• Bipartite Graphs
• K-regular Graphs
• Graph ADT Operators

Graph Representations

• Incidence and Adjacency Matrices
• Adjacency and Edge Lists

More Graph Terminology

• Connected Graphs
• Spanning Tree
• Algorithms

Biconnected Graphs

• Definition
• Determining
• Example

Euler Circuit

• Definition
• Fleury's Algorithm

Graph Representations

Augmenting Path

Directed Graphs (Digraphs)

• Weakly/Stongly Connected
• Adjacency Matrix and List
• Incidence Matrix and List
• Changes in Digraph ADT?

Shortest Path

• Dijkstra
• Floyd's Algorithm
• Warshall's Transitive Closure

Topological sorting

• Definition
• Directed Acyclic Graph(DAG)

• Shell
• External Sorting
• Merge Sort
• In situ arrays