COMP280: Data Structures Lecture 1

Flashcards covering key concepts from the lecture notes on data structures, algorithms, and Big-O analysis.

Data Structures

A collection of data values, the storage format for these values (e.g., array, linked list, stack, queue, search tree, graph), and the operations defined on them (the ADT).

Abstract Data Type (ADT)

A data type defined by its operations and behavior, independent of implementation.

Why Data Structures?

Different storage formats have different efficiencies for a problem; no single DS is best for all cases; choose the best DS for the problem.

Common data structures covered

Arrays, Linked Lists, Binary Search Trees, Heaps, Hash Tables, and Graph-related structures; many languages provide built-in DS (e.g., C++ STL: vector, set, map, queue, stack, priority_queue).

C++ importance

C++ remains an important language alongside Python, Java, JavaScript, C#, Swift; relatively old but evolving, efficient and powerful.

C++ basics ( Hello World )

A minimal C++ program structure, e.g., #include , using namespace std; int main() { cout << "Hello World!" << endl; return 0; }.

C++ compiling

g++ compiles a program; default output is executable a.out; using -o option names the executable (e.g., g++ myprog.cpp -o myprog.out).

C++ editors

IDEs: Dev C++, Eclipse, NetBeans, Xcode; vi is a text editor, not a full IDE, useful for small programs.

What is an Algorithm?

The ideas behind computer programs; language-independent; solves a general, specified problem.

What is a problem?

A mapping from input instances (domain) to an output set (range); problem specification includes typical input and expected output (e.g., sorting).

Input and Output in a problem

Describe how input looks (domain) and how output should look and relate to the input.

Find Minimum problem (definition)

Input: N ≥ 1 and a list a1, a2, …, aN; Output: the minimum element x = ai for some i, such that x ≤ aj for all j.

Input instance

An assignment of values to input variables, e.g., N = 10 and (a1, …, aN) = (5,1,7,4,3,2,3,3,0,8).

Implementing a mapping

Write a program that takes input and produces the correct output (Input → Program → Output).

Example Find Minimum solution idea

An O(n) algorithm that scans the array, updating the current minimum as it goes.

Two properties of algorithms

Correctness: always produces the correct output for legal input. Efficiency: fast in time and space (Big-O) and simplicity.

Odd Number problem (efficient approach)

To test if n is odd, look at the last bit (or last digit); other naive methods are less efficient.

Analyzing algorithms

Study the time and space resources an algorithm uses without running it on hardware; compare algorithms theoretically.

Big-O notation

A notation for measuring the upper bound of an algorithm's time (and sometimes space) complexity as a function of input size.

Common complexity functions

Functions used to classify growth: n, n^2, n^3, n^5, 2^n, 3^n, 2n, n log n, log n, etc.

Worst, Best, and Average case

Worst-case: maximum steps for size n; Best-case: minimum steps; Average-case: expected steps. Worst-case is simpler to guarantee and often close to average.

Average-case analysis drawbacks

Depends on assumed input distribution; harder to compute than worst-case; sometimes worst-case ≈ average (with exceptions like Quicksort and simplex).

Worst-case analysis

Typically easier to compute; identifies an input that causes the worst performance and provides a universal guarantee.