Data Structures and Algorithms: Core Concepts and Comparisons
Graph and Tree Structures Fundamentals
Difference between Tree and Graph
The fundamental differences between trees and graphs are summarized below:
| Feature | Tree | Graph |
|---|---|---|
| Structure | A tree is a hierarchical structure containing a root and several levels of child nodes. | A graph is a network structure containing vertices and edges without any fixed hierarchical arrangement. |
| Cycles | A tree never contains cycles because it maintains a strict parent-child relationship across all nodes. | A graph can freely contain cycles |
C++ Data Structures: Circular List, AVL Rotations, DFS & Palindrome
Create and Display a Circular Singly Linked List
In a circular singly linked list, the last node’s next pointer points back to the head instead of NULL.
C++
// struct definition
struct Node {
int data;
Node* next;
};
// Function to insert a node (Creating the list)
void insertEnd(Node*& head, int value) {
Node* newNode = new Node();
newNode->data = value;
if (head == NULL) {
head = newNode;
newNode->next = head; // Points to itself
Solve 8-Puzzle Problem with Python and A* Search
Write a Program to Implement 8-Puzzle problem using Python
import heapq
from termcolor import colored
# Class to represent the state of the 8-puzzle
class PuzzleState:
def __init__(self, board, parent, move, depth, cost):
self.Board = board # The puzzle board configuration
self.Parent = parent # Parent state
self.Move = move # Move to reach this state
self.Depth = depth # Depth in the search tree
self.Cost = cost # Cost (depth + heuristic)
Algorithm Complexity and Data Structure Fundamentals Q&A
1. What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
2. Suppose we have a O(n)
time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.
O(nLogn)
3. Given an unsorted array. The array has this property
Read MoreSignals, Systems, and 5G Network Fundamentals
Signal Transformation for Continuous-Time Signals
Q1 (a) — Explain the signal transformation needed for transforming the independent variable for continuous-time signals.
Signal transformation changes the independent variable (usually time) to modify or analyze signals. Common transformations include:
- Time shifting: Shifts the signal by a time constant t₀.
- Time scaling: Compresses the signal (if a > 1) or expands it (if a < 1).
- Time reversal: Flips the signal around the vertical axis.
These
Read MoreEssential Data Structures and Algorithms Reference: DSA Core Concepts
Lesson 2: Object-Oriented Programming and Linked Lists
OOP Fundamentals
- Class: The blueprint for creating objects. Object: An instance of a class.
- Attribute: A variable stored within an object. Method: A function defined within a class.
- The
selfkeyword refers to the object instance.__init__is the constructor method.
OOP Example (Python)
class Car:
def __init__(self, make, model, year):
self.make = make; self.model = model; self.year = year
def info(self):
return f"{self.year}