Data Structures CH.1-3

Data Structure

A specific way to store and organize data in a computer so it can be used efficiently.

Algorithm

A set of exact steps needed for a computer to solve a problem or reach a goal.

Procedure

A step-by-step set of instructions that takes specific inputs and follows exact actions to produce a desired outcome.

Data Abstraction

The practice of seperating the logical view from the physical view.

Pseudocode

High level description that combines natural language with familiar structure from programming language.

Graph

A DS consisting of a finite set of vertices and edges between pair of verticies.

Self-loop Edge

An edge that originates AND ends at the same vertex.

Parellel Edge

2 undirected edges with the same end vertices.

*For directed MUST share same orgin AND destination

Simple Graph

A graph that contains NO parellel edge and no self-loops

Weighted Graph

A graph with a specific value(weight)

Degree of Vertex

Number of edges in a vertex

in-degree

number of incoming edges into a vertex

out-degree

number of outcoming edges in a vertex

Path

A sequence of verticies where every vertex is adjacent to the next one in the sequence.

Simple Path

All verticies and edges are completley distinct.

Length of Path

Sum of all edges that make up the path.

Cycle

A circular sequence of alternating vertex and edges where the starting vertex is identical to the ending vertex

Adjecency Matrix

A square grid of true false values that represent edges of a graph. O(v²)

Adjacency List

A graph representation where a linked list is created for each vertex. O(V + E)

DiGraph

Graph whose ALL edges are directed

Directed Acylic Graph(DAG)

a Digraph that contains NO directed cycles. Flows in one direction.

Topological Ordering / Sort

A linear oredering of the vertecies in a digraph such that for every directed edge uv, u comes before v . - can have more than one option traversing order

Task

Represents an individual node or vertex in a DAG

Scheduling

An edges represents a dependency where on task must be completed before another one can begin.