Untitled Flashcards Set

Here are concise definitions (2 sentences or less) for each term:

Algorithm Efficiency

Algorithm efficiency describes how well an algorithm performs in terms of time and space as the input size grows. It helps evaluate the scalability of the solution.

Growth Functions of a Program

A growth function shows how the running time or space of a program increases with input size nn. It helps measure algorithm performance.

Asymptotic Complexity of an Algorithm

Asymptotic complexity focuses on how an algorithm behaves as the input size approaches infinity. It ignores constants and lower-order terms.

Big-O Notation (Upper Bound)

Big-O notation gives the worst-case upper bound on an algorithm's growth rate. It simplifies complexity expressions to their most significant term.

Big-O / Order Categories

Big-O categories include O(1)O(1), O(log⁡n)O(\log n), O(n)O(n), O(nlog⁡n)O(n \log n), O(n2)O(n^2), etc. Each represents a class of algorithm efficiency based on input growth.

Comparing Growth Functions and Orders

Growth functions are compared by analyzing which grows faster as nn becomes very large. For instance, O(n)O(n) is more efficient than O(n2)O(n^2) for large inputs.

Analyzing Loop / Nested Loops Execution

Single loops typically contribute O(n)O(n) time, while nested loops multiply their complexities (e.g., two nested loops = O(n2)O(n^2)). Loop structure directly affects algorithm efficiency.

Chapter 12:

ADT (Abstract Data Type)

An ADT defines a logical data model and operations, independent of implementation. Examples include Stack, Queue, and List.

Stack

A stack is a Last-In-First-Out (LIFO) structure. Items are added and removed from the top only.

Linear and Non-Linear Collections

Linear collections (like arrays and lists) store data in sequence. Non-linear collections (like trees and graphs) organize data hierarchically or through connections.

Stack Operations

Main stack operations include push() to add, pop() to remove, peek() to view the top, and isEmpty() to check if it's empty.

Concept of Stack Implementation

Stacks can be implemented using arrays or linked lists, each affecting performance and memory usage. The implementation hides underlying structure from the user.

Operations for Stack (p13 of PPT)

Standard stack operations: push (add), pop (remove), peek/top (view top item), isEmpty (check if empty), isFull (check if full, for arrays).

Idea of Applications of Stack

Stacks are useful in undo features, parsing expressions, recursion support, and backtracking algorithms.

Chapter 13:

Linked Structures

Linked structures store elements as nodes, each with data and references to other nodes. They enable dynamic memory allocation and flexible insertions/deletions.

Linked Lists

A linked list is a linear data structure with nodes connected via pointers. Types include singly, doubly, and circular linked lists.

Chapter 14:

What is a Queue? Queue’s Features

A queue is a First-In-First-Out (FIFO) structure. Items are added at the rear and removed from the front.

Operations of Queue

Basic queue operations are enqueue (insert), dequeue (remove), peek (front view), isEmpty, and isFull.

Implementation of Queue

Queues can be implemented using arrays, linked lists, or circular buffers to manage overflow efficiently.

Chapter 15:

What is a List?

A list is an ordered collection of elements where duplicates are allowed. Elements can be accessed by index.

Three Types of List Collections

Java provides: ArrayList (resizable array), LinkedList (doubly-linked), and Vector (synchronized array).

Standard LinkedList in Java

Java's LinkedList class implements List and Deque interfaces, supporting efficient insertions/deletions at both ends.

Chapter 17:

Recursion

Recursion is when a method calls itself to solve a smaller instance of the same problem.

Recursive Definitions

Recursive definitions specify rules to define an object in terms of itself (e.g., factorial: n!=n⋅(n−1)!n! = n \cdot (n-1)!).

Infinite Recursion

Occurs when a recursive function lacks a base case, causing it to call itself indefinitely, often resulting in a stack overflow.

Recursion in Math

Mathematical recursion defines functions like factorial, Fibonacci, or powers using previous values.

Recursive Programming

In programming, recursion simplifies problems like tree traversal, but requires a base case to prevent infinite loops.

Recursion vs. Iteration

Recursion is elegant but may use more memory (stack frames), while iteration is usually more efficient in space.

Chapter 18:

Linear Search

A simple search that checks each element one by one. Time complexity: O(n)O(n).

Binary Search

Searches a sorted array by repeatedly dividing it in half. Time complexity: O(log⁡n)O(\log n).

Comparing Search Algorithms

Binary search is faster than linear search for sorted data. Linear search is better for unsorted or small lists.

Sorting

Sorting arranges elements in a defined order (e.g., ascending). It helps improve search and data organization.

Selection Sort

Repeatedly finds the minimum and places it in the correct position. Time complexity: O(n2)O(n^2).

Insertion Sort

Builds the sorted array one item at a time by inserting elements into their correct position. Time complexity: O(n2)O(n^2).

Merge Sort

Divide-and-conquer algorithm that splits, sorts, and merges. Time complexity: O(nlog⁡n)O(n \log n).

Comparing Sorts

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

Chapter 19:

Trees

Trees are hierarchical structures with a root and child nodes. Each node can have multiple children.

Definitions of Trees

A tree is a connected acyclic graph. One node is the root, and all others are reachable from it.

Properties of Trees

Includes height, depth, level, degree, and number of nodes. A tree with nn nodes has n−1n-1 edges.

Terms (Tree)

Important terms: root, parent, child, sibling, leaf, internal node, height, depth, subtree.

Binary Tree

A binary tree is a tree where each node has at most two children (left and right).

Terms of Binary Tree

Includes full, complete, perfect, balanced binary trees. Each has structural rules.

Balance

A balanced binary tree maintains minimal height to ensure O(log⁡n)O(\log n) performance in operations.

Sorted Binary Trees (BST)

In a Binary Search Tree, left child < parent < right child. Enables efficient searching and sorting.

Binary Search in a Sorted Array

This algorithm splits the sorted array in half at each step. Time complexity: O(log⁡n)O(\log n).

Tree Traversals

Tree traversal visits each node: preorder (root-left-right), inorder (left-root-right), postorder (left-right-root).

Detailed Algorithms of Preorder, Inorder, Postorder

• Preorder: visit node → left → right

• Inorder: left → visit node → right

• Postorder: left → right → visit node

Examples and Programs of Tree Traversal

Use recursion to implement traversals. Each method processes the tree in a different node visitation order.

Create a Binary Tree with Given Numbers

Insert numbers one by one using BST rules (left if smaller, right if greater).

Chapter 24:

What is a Graph?

A graph is a collection of nodes (vertices) and connections (edges). Can be directed/undirected and weighted/unweighted.

Terminologies of Graph

Terms: vertex, edge, path, cycle, degree, adjacency, connected, directed/undirected, weighted/unweighted.

Graph Representations

Graphs are represented by adjacency lists, adjacency matrices, or edge lists.

Graph Traversal: DFS / BFS

• DFS (Depth-First Search) explores as deep as possible before backtracking.

• BFS (Breadth-First Search) explores neighbors level-by-level.
  They generate different visit sequences depending on structure.

Would you like me to export this into Knowt or Quizlet format next?