Untitled Flashcards Set

Algorithm Efficiency

Describes how well an algorithm performs in terms of time and space as the input size grows.

Growth Functions of a Program

Shows how the running time or space of a program increases with input size.

Asymptotic Complexity of an Algorithm

Focuses on how an algorithm behaves as the input size approaches infinity.

Big-O Notation (Upper Bound)

Gives the worst-case upper bound on an algorithm's growth rate.

Big-O / Order Categories

Includes classes of algorithm efficiency based on input growth like O(1), O(n), O(n^2).

Comparing Growth Functions and Orders

Analyzes which growth function increases faster as input size becomes very large.

Analyzing Loop / Nested Loops Execution

Single loops contribute O(n) time, while nested loops multiply complexities.

ADT (Abstract Data Type)

Defines a logical data model and operations, independent of implementation.

Stack

A Last-In-First-Out (LIFO) structure.

Linear and Non-Linear Collections

Linear collections store data in sequence, while non-linear organize data hierarchically.

Stack Operations

Include push(), pop(), peek(), and isEmpty().

Concept of Stack Implementation

Stacks can be implemented using arrays or linked lists.

Operations for Stack (p13 of PPT)

Standard operations: push, pop, peek/top, isEmpty, isFull.

Idea of Applications of Stack

Useful in undo features, parsing expressions, recursion support, and backtracking.

Linked Structures

Store elements as nodes, with references to other nodes.

Linked Lists

A linear data structure with nodes connected via pointers.

What is a Queue? Queue’s Features

A First-In-First-Out (FIFO) structure.

Operations of Queue

Basic operations include enqueue, dequeue, peek, isEmpty, and isFull.

Implementation of Queue

Queues can be implemented using arrays, linked lists, or circular buffers.

What is a List?

An ordered collection of elements where duplicates are allowed.

Three Types of List Collections

Java provides ArrayList, LinkedList, and Vector.

Standard LinkedList in Java

Implements List and Deque interfaces efficiently.

Recursion

When a method calls itself to solve a smaller instance of the same problem.

Recursive Definitions

Specify rules to define an object in terms of itself.

Infinite Recursion

Occurs when a recursive function lacks a base case.

Recursion in Math

Defines functions using previous values.

Recursive Programming

Simplifies problems like tree traversal but needs a base case.

Recursion vs. Iteration

Recursion is elegant but uses more memory; iteration is often more efficient.

Linear Search

Checks each element one by one; time complexity O(n).

Binary Search

Searches a sorted array by repeatedly dividing it in half; time complexity O(log n).

Comparing Search Algorithms

Binary search is faster for sorted data; linear search is better for unsorted data.

Sorting

Arranges elements in a defined order.

Selection Sort

Repeatedly finds the minimum and positions it correctly; O(n^2).

Insertion Sort

Builds a sorted array by inserting elements; O(n^2).

Merge Sort

Divide-and-conquer algorithm; O(n log n).

Comparing Sorts

Merge sort is faster for large data; selection/insertion sorts are easier but less efficient.

Trees

Hierarchical structures with a root and child nodes.

Definitions of Trees

Connected acyclic graphs with one root node.

Properties of Trees

Include height, depth, level, and more; a tree with n nodes has n-1 edges.

Terms (Tree)

Key terms: root, leaf, height, subtree.

Binary Tree

Each node has at most two children.

Terms of Binary Tree

Full, complete, perfect, balanced binary trees.

Balance

Maintains minimal height for efficient operations.

Sorted Binary Trees (BST)

Left child < parent < right child for efficient searching.

Binary Search in a Sorted Array

Splits sorted array at each step; O(log n).

Tree Traversals

Visit each node in different orders: preorder, inorder, postorder.

Detailed Algorithms of Preorder, Inorder, Postorder

Visit patterns to traverse trees.

Examples and Programs of Tree Traversal

Use recursion to implement different traversal methods.

Create a Binary Tree with Given Numbers

Insert numbers following BST rules.

What is a Graph?

A collection of nodes and connections, can be directed/undirected.

Terminologies of Graph

Include vertex, edge, path, and more.

Graph Representations

Using adjacency lists, matrices, or edge lists.

Graph Traversal: DFS / BFS

DFS explores deep, BFS explores level-by-level.