Data Structures and Algorithms Flashcards

Flashcards based on Data Structures and Algorithms lecture notes.

Time Complexity

The amount of time required by the algorithm to complete.

Recursive Method without Base Case

An infinite loop occurs.

Selection Sort Algorithm (Average Time Complexity)

O(n^2)

Constant Time Complexity (Big-O notation)

O(1)

Key Benefit of Generic Dynamic Data Structures

Allows code reusability, hence can be used to store all valid object types.

Doubly Linked List

Allows traversal in both forward and backward directions. (True)

Graph Representation

Adjacency List, Adjacency Matrix as well as Incidence Matrix

Dijkstra's Algorithm Use

Find the shortest path between two nodes in a graph

Functional Interface

Has a single abstract method. (True)

Primary Advantage of Linked List over Array

Dynamic size adjustment

Binary Search Tree (BST) InOrder Traversal

Left subtree, root, right subtree

Recursion

A function that calls itself to solve smaller subproblems of the same type.

Divide and Conquer

A problem-solving paradigm where a problem is divided into smaller subproblems, solved independently, and their solutions combined. Example: Merge Sort.

Cost Function O(log2n) vs O(n)

O(log2n) performs better because the time taken increases much slower with input size compared to O(n).

Linked List

A data structure where elements are stored in nodes, each containing data and a pointer to the next node.

Hash Tables and Hash Functions

Hash Tables use Hash Functions to map keys to indices in an array for efficient data storage and retrieval.

HashSet and Object Equality

To use HashSet, the equals() and hashCode() methods must be implemented in the class, and relevant attributes should be immutable.

Functional Interface (Java)

An interface with a single abstract method, useful for lambda expressions and functional programming.

Binary Tree vs Array for Sorted Names

Array is better due to constant-time access using indices provided the array is sorted.

Binary Search Tree vs. Binary Tree

A Binary Search Tree maintains an ordered structure, allowing efficient searching, insertion, and deletion, While a Binary Tree does not have any specific ordering.

Graph

A data structure consisting of nodes (vertices) and edges connecting them, differing from a tree by allowing cycles and multiple connections between nodes.

Dijkstra's Algorithm

An algorithm for finding the shortest paths between nodes in a graph, iteratively updating tentative distances until the shortest path to each node is found.

HashMap vs. TreeMap

HashMap offers faster average-case performance with O(1) lookup but does not guarantee any specific order of elements. TreeMap guarantees sorted order.