Monday, September 23, 2024

CSE 220: Data Structures - BracU

CSE220: Data Structures & Python – A Deep Dive into Data Organization and Algorithms

Data structures form the backbone of efficient data management in computer science, providing methods to store, organize, and process data. CSE220 at Brac University focuses on introducing these structures, their algorithms, and their performance, preparing students for advanced programming and problem-solving. In this blog, we will merge the core ideas from CSE220 with practical implementations in Python, making it easier to understand how these theoretical concepts translate into real-world coding.

What is CSE220?

CSE220 is a 3-credit course offered at Brac University that covers the effective methods of organizing data. It revolves around elementary and advanced data structures, memory management, sorting, searching, and fundamental algorithms. By learning how data is stored, managed, and manipulated, students develop a solid foundation in data structure and algorithm analysis.

The course covers:

  • Arrays, Lists, Stacks, Queues

  • Linked Lists, Trees, Graphs

  • Hash Techniques

  • Recursion, Backtracking

  • Memory Management, Sorting, Searching

To reinforce these concepts, students participate in lab sessions where they get hands-on experience implementing these structures and algorithms.

Why Data Structures Matter

Data structures are vital because they determine how efficiently data can be accessed and manipulated. Choosing the right structure can improve the performance of algorithms and make applications run faster. Now, let's break down some key data structures taught in CSE220 and explore their Python implementations.

1. Arrays in Python

Arrays are collections of items stored at contiguous memory locations, making them efficient for storing multiple values of the same type. In Python, arrays can be implemented using lists or the array module. While lists provide dynamic sizing and allow appending and removing elements, traditional arrays in Python (from the array module) have a fixed size and do not support dynamic resizing.

Limitations of Arrays in Python:

  1. Fixed Size: Traditional arrays (using the array module) have a fixed size, meaning that once they are created, you cannot add or remove elements. If you need a different size, you must create a new array.

  2. Type Homogeneity: Traditional arrays enforce type homogeneity, meaning all elements must be of the same type, which can be limiting in certain scenarios.

  3. Less Flexibility: Unlike lists, traditional arrays do not support dynamic operations such as appending or removing elements.

  4. Performance Overhead: While lists can handle mixed types and resizing, this incurs a performance overhead compared to fixed-size arrays in other languages.

2. Multidimensional Arrays

Multidimensional arrays, like matrices, allow storing data in a table-like format, which is crucial for tasks that involve rows and columns, such as image processing or matrix calculations. These can be created using nested lists.

# 2D array (matrix)
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# Accessing elements
print(matrix[0][1])  # Output: 2


3. Linked Lists

A linked list is a linear data structure where each element (node) contains a value and a reference to the next node. Unlike arrays, linked lists provide dynamic memory allocation, which helps optimize memory usage.


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            temp = self.head
            while temp.next:
                temp = temp.next
            temp.next = new_node


4. Stacks and Queues

A stack follows the LIFO (Last In, First Out) principle, where the last element added is the first one to be removed. For a linked list-based stack, we typically add and remove elements from the head of the list for constant time operations.

Implementation:

  • Push: Insert an element at the head of the linked list.

  • Pop: Remove an element from the head of the linked list.

  • Peek: Look at the top element without removing it.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    # Push an element to the stack
    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top  # New node points to current top
        self.top = new_node  # Update top to new node
        print(f'Pushed {value} onto the stack.')

    # Pop an element from the stack
    def pop(self):
        if self.is_empty():
            return "Stack is empty"
        removed_value = self.top.value
        self.top = self.top.next  # Move top to the next node
        return f'Popped {removed_value} from the stack.'

    # Peek the top element of the stack
    def peek(self):
        if self.is_empty():
            return "Stack is empty"
        return f'Top element is {self.top.value}'

    # Check if the stack is empty
    def is_empty(self):
        return self.top is None

# Usage
stack = Stack()
stack.push(10)
stack.push(20)
print(stack.peek())  # Output: Top element is 20
print(stack.pop())   # Output: Popped 20 from the stack
print(stack.pop())   # Output: Popped 10 from the stack
print(stack.pop())   # Output: Stack is empty


A queue follows the FIFO (First In, First Out) principle, where the first element added is the first one to be removed. In a linked list-based queue, you maintain both a head (for dequeue) and a tail (for enqueue) to ensure constant time operations.

Implementation:

  • Enqueue: Insert an element at the tail (end) of the linked list.

  • Dequeue: Remove an element from the head (front) of the linked list.

  • Peek: Look at the front element without removing it.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    # Enqueue an element to the queue
    def enqueue(self, value):
        new_node = Node(value)
        if self.tail:
            self.tail.next = new_node  # Current tail points to new node
        self.tail = new_node  # Update tail to new node
        if not self.head:  # If the queue was empty
            self.head = new_node
        print(f'Enqueued {value} into the queue.')

    # Dequeue an element from the queue
    def dequeue(self):
        if self.is_empty():
            return "Queue is empty"
        removed_value = self.head.value
        self.head = self.head.next  # Move head to the next node
        if not self.head:  # If the queue becomes empty
            self.tail = None
        return f'Dequeued {removed_value} from the queue.'

    # Peek the front element of the queue
    def peek(self):
        if self.is_empty():
            return "Queue is empty"
        return f'Front element is {self.head.value}'

    # Check if the queue is empty
    def is_empty(self):
        return self.head is None

# Usage
queue = Queue()
queue.enqueue(5)
queue.enqueue(15)
print(queue.peek())   # Output: Front element is 5
print(queue.dequeue()) # Output: Dequeued 5 from the queue
print(queue.dequeue()) # Output: Dequeued 15 from the queue
print(queue.dequeue()) # Output: Queue is empty


Key Differences Between Stack and Queue (Linked List-Based):

  1. Stack (LIFO):

    • Push: Insert at the head.

    • Pop: Remove from the head.

    • Only one pointer to manage (top).

  2. Queue (FIFO):

    • Enqueue: Insert at the tail.

    • Dequeue: Remove from the head.

    • Two pointers to manage (head and tail).

Advantages of Using Linked List for Stack and Queue:

  • Dynamic size: Linked lists allow the structure to grow and shrink dynamically.

  • Efficient memory usage: Nodes are created only when required, avoiding memory wastage.

This implementation provides an efficient way to implement both stack and queue using a linked list structure, ensuring constant time operations for insertion and deletion.

5. Recursion

Recursion is when a function calls itself to solve smaller instances of the same problem. This technique is powerful for breaking down complex problems, such as navigating tree structures or performing sorting.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

Recursion is elegant but can lead to memory issues if not managed carefully, so be mindful of the base case and recursion depth.

6. Hashing and Hashtables

Hashing transforms data into a fixed-size value for quick lookups, making it essential for large datasets. A hashtable stores key-value pairs and supports fast data retrieval.

7. Trees

A tree is a hierarchical structure with a root node and child nodes, resembling a parent-child relationship. Binary trees limit each node to two children and are useful for efficient searching, sorting, and hierarchical data representation.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

8. Binary Search Trees (BST) and Heaps

A Binary Search Tree (BST) maintains order by ensuring that the left subtree has values less than the parent node, and the right subtree has values greater than the parent node. This structure allows efficient searching.

Heaps, meanwhile, follow the heap property where each parent node is greater than or equal to its children (max heap). Heaps are useful in priority queues and sorting algorithms.

CSE220 lays the groundwork for understanding data structures, which are essential for efficient data handling and algorithm design. These structures, from arrays and linked lists to trees and heaps, not only form the core of computer science but also improve the performance and scalability of applications.

By learning how to implement these data structures in Python, students gain hands-on experience and a practical understanding of how to solve complex problems efficiently. Whether you’re studying data structures academically or using them in real-world applications, mastering these concepts will significantly enhance your programming skills and problem-solving abilities.

So dive into these structures, experiment with code, and unlock the power of data organization!

This blog provides an easy-to-follow guide to core data structures while linking the theoretical concepts taught in CSE220 to practical implementations in Python


Additional Resources:

Below are some helpful resources that include a combination of personal notes, departmental materials, and references from faculty members and students:


Happy learning! If you encounter any difficulties in CSE220, feel free to email me at my G Suite account. Thank you!

#DataStructures #CodingTips #Algorithms #Programming2024

Labels: , , , ,

posted by Monowar Husain @ September 23, 2024   0 Comments

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home