Algorithms and Data Structures – Lecture 1 (Stacks & Queues, Complexity Basics)

What is the primary aim of the module "Algorithms and Data Structures"?

To give students additional insight into programming techniques through data structures, algorithms and their complexity analysis in a practical context.

List any two intended learning outcomes of this module.

(1) Understand and select appropriate algorithms for a range of problems. (2) Design and implement algorithms and data structures for novel problems.

How many contact hours per week does the class meet, and in what formats?

Three hours per week, comprising lectures, discussions and tutorial sessions.

Name the essential textbook recommended for this course.

McGrath, M. (2011) C++ Programming in Easy Steps (4th ed.).

According to course policies, what is the consequence of missing assignment deadlines?

Failure to keep deadlines will adversely affect a student’s grade.

Complete the equation: Data Structures + Algorithms = .

Programs (Problem → Solution).

Define a data structure.

A specialized format (logical or mathematical model) for organizing and storing data to enable efficient access and manipulation.

Give three general examples of data structures mentioned in the lecture.

Array, Stack, Tree (also acceptable: Record, Queue, etc.).

What are the three broad categories into which data can be organized?

Primitive types, Composite types, Abstract Data Types (ADTs).

Give two examples of primitive data types.

Character (char) and Integer (int).

What is a composite data type?

A data type constructed from primitive and/or other composite types within a program (composition).

In C/C++, what keyword declares a user-defined composite type and what is it commonly called?

The keyword struct; it is called a structure (user-defined data structure).

Define an Abstract Data Type (ADT).

A mathematical model of data objects plus the operations on them, specified only by their behavior and constraints, not by implementation.

Which two core operations define an abstract stack ADT?

push (insert an item) and pop (remove the most recently pushed item).

State the main goal and two criteria for using data structures.

Goal: Organize data. Criteria: Facilitate efficient storage, retrieval and manipulation.

List four fundamental operations that can be performed on data structures.

Traversing, Searching, Insertion, Deletion (also Sorting, Merging).

Provide one formal definition of an algorithm given in the lecture.

A finite set of statements that guarantees an optimal solution in a finite interval of time.

What property must every correct algorithm satisfy when sorting input that is already sorted or contains duplicates?

It must still correctly sort the input (handle sorted and repeated elements).

State the two primary resources considered when measuring algorithm efficiency.

Time and Memory (space).

Why is measuring processor time alone insufficient for evaluating an algorithm’s efficiency?

Because real execution time varies with processor speed, language, compiler quality, OS, and input size; theoretical analysis abstracts from these factors.

How is running time typically expressed in theoretical analysis?

As a function of input size N, counting the number of primitive operations or steps.

What does asymptotic analysis focus on when N becomes very large?

The highest-order term of the time-complexity function, ignoring lower-order terms and constant factors.

Define Big O notation in one sentence.

A mathematical notation that describes an upper bound on the growth rate (worst-case) of an algorithm’s time or space complexity.

What is the Big O time complexity of accessing any single array element?

O(1) – Constant time.

Give the typical Big O for a simple loop that scans every element of an array once.

O(n) – Linear time.

What kind of nested-loop algorithm has time complexity O(n²)?

An algorithm that performs a full inner loop for each iteration of an outer loop over the same data set (e.g., duplicate checking).

Describe exponential time complexity and provide the Big O symbol.

Growth doubles with each additional input element; O(2^n).

Which classic problem often requires exponential time when solved exactly via dynamic programming?

The Traveling Salesman Problem (TSP).

State one example of an algorithm that typically runs in O(log n) time.

Binary search on a sorted array.

According to the Big-Oh rules, how would you simplify 3n + 5 for asymptotic notation?

O(n) – drop the constant coefficient and lower-order term.

Formally, f(n) is O(g(n)) if there exist positive constants c and n₀ such that .

f(n) ≤ c ·