Flashcards: Fundamentals of Algorithms and Data Structures — 24 cartões

Algorithm — definition?

Finite sequence of elementary operations solving a problem.

Algorithm expression — language?

Language-independent; describes *what* to do, not *how*.

Program — concept?

Sequence of instructions executed by hardware to perform tasks.

Complexity — focus?

Measures time or resources needed, based on input size.

Search algorithms — example?

Binary search, sequential search, etc.

Sorting algorithms — goal?

Arrange data in a specific order based on keys.

Data structures — purpose?

Organize and store data efficiently for algorithms.

Stack — principle?

LIFO: Last-In-First-Out.

Queue — principle?

FIFO: First-In-First-Out.

Linked list — structure?

Nodes with data and pointer to next node.

Binary tree — max children?

At most two children per node.

Graph — representation?

Adjacency matrix or adjacency list.

Hash function — role?

Maps keys to table indices for quick access.

Collision — meaning?

Two keys hash to the same index.

Chaining — collision resolution?

Store colliding elements in linked lists at each slot.

Open addressing — collision resolution?

Find alternative slot via probing methods.

Double hashing — method?

Uses two hash functions for probe sequences.

Algorithm complexity — notation?

Big O notation describes growth rate.

Worst-case complexity — meaning?

Maximum time for any input of size n.

Sequential search — complexity?

O(n): linear in number of elements.

Bubble sort — property?

Elementary, stable, in-place, quadratic time.

Data key — in records?

Unique attribute used for identification or sorting.

Satellite data — in records?

Additional info linked to the key, not used for sorting.

Array — characteristic?

Contiguous memory, fast access, fixed size.