\documentclass[12pt]{article} \usepackage[utf8]{inputenc} \usepackage{amsmath, amssymb, amsthm} \usepackage{graphicx} \usepackage{listings} \usepackage{xcolor} \usepackage{hyperref} \usepackage{enumitem} \usepackage{geometry} \geometry{margin=1in} % Define colors for code \definecolor{codegray}{rgb}{0.5,0.5,0.5} \definecolor{codepurple}{rgb}{0.58,0,0.82} \definecolor{backcolour}{rgb}{0.95,0.95,0.92} \lstdefinestyle{mystyle}{ backgroundcolor=\color{backcolour}, commentstyle=\color{codegray}, keywordstyle=\color{blue}, numberstyle=\tiny\color{codegray}, stringstyle=\color{codepurple}, basicstyle=\ttfamily\footnotesize, breaklines=true, captionpos=b, keepspaces=true, numbers=left, numbersep=5pt, showspaces=false, showstringspaces=false, showtabs=false, tabsize=2 } \lstset{style=mystyle} \title{Algorithms and Data Structures: A Demonstration} \author{Your Name} \date{\today} \begin{document} \maketitle \tableofcontents \newpage \section{Introduction} Algorithms and data structures form the backbone of computer science and software engineering. In this document, we present a comprehensive overview of fundamental algorithms and data structures, including example code and explanations of how they work. This demonstration supports a program designed to showcase key algorithmic techniques. \section{O-notaion} Big-O notation is a mathematical concept used to describe the upper bound of an algorithm's running time or space requirements in terms of input size \( n \). It provides a high-level understanding of an algorithm's efficiency by abstracting away hardware-specific details and constant factors. Big-O expresses how the runtime grows as the input size increases. For example: \begin{itemize} \item \( O(1) \) — Constant time: the algorithm takes the same amount of time regardless of input size. \item \( O(\log n) \) — Logarithmic time: each step reduces the input size by a fraction (e.g., binary search). \item \( O(n) \) — Linear time: performance scales directly with input size. \item \( O(n \log n) \) — Log-linear time: typical of efficient sorting algorithms like merge sort and quick sort. \item \( O(n^2) \) — Quadratic time: common in simple nested loops (e.g., bubble sort). \end{itemize} This notation helps compare algorithms in terms of scalability and guides the selection of appropriate techniques for large-scale problems. \section{Data Structures} \subsection{Arrays} Arrays are fixed-size collections of elements of the same type, stored in contiguous memory locations. "Fixed-size" means that the size of the array is determined when it is created and cannot be changed later. This is because arrays allocate a block of memory large enough to hold all elements at once, and increasing the size would require allocating a new block and copying the existing data. "Contiguous memory" refers to the way array elements are stored in a single continuous block of memory, which allows for fast indexing and traversal. \begin{lstlisting}[language=Python, caption=Example of array usage in Python] arr = [1, 2, 3, 4, 5] print(arr[2]) # Output: 3 \end{lstlisting} \subsection{Linked Lists} Linked lists are dynamic data structures consisting of nodes that each contain data and a pointer to the next node. A dynamic data structure means its size can grow or shrink during runtime, unlike fixed-size structures such as arrays. This allows for efficient memory usage, especially when the number of elements is unknown in advance. Each node in a linked list includes a pointer, which is a variable that stores the memory address of another variable—in this case, the next node in the list. This use of pointers enables dynamic linking of elements in memory, rather than relying on contiguous storage. \begin{lstlisting}[language=Python, caption=Singly Linked List Node] class Node: def init(self, data): self.data = data self.next = None \end{lstlisting} \subsection{Stacks and Queues} Stacks follow the LIFO (Last In, First Out) principle, meaning that the last element added to the stack is the first one to be removed. This is analogous to a stack of plates where you add and remove plates only from the top. The 'growth' direction for a stack is from the bottom to the top. Queues, on the other hand, follow the FIFO (First In, First Out) principle, where the first element added is the first one to be removed. This is similar to a line of people waiting in line: the first person in line is served first. In a queue, the 'growth' happens at the rear (where new elements are enqueued), and removal happens at the front (where elements are dequeued). \begin{lstlisting}[language=Python, caption=Stack Implementation Using List] stack = [] stack.append(1) stack.append(2) print(stack.pop()) # Output: 2 \end{lstlisting} \begin{lstlisting}[language=Python, caption=Queue Implementation Using deque] from collections import deque queue = deque() queue.append(1) queue.append(2) print(queue.popleft()) # Output: 1 \end{lstlisting} \section{Algorithms} \subsection{Sorting Algorithms} \subsubsection{Bubble Sort} Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. "Stepping through" the list means iterating from the beginning of the list to the end, repeatedly examining pairs of neighboring elements. Specifically, it compares each element at index with the one at index . If the element at is greater than the element at , the two are swapped. This process continues until the list is sorted, with larger elements gradually "bubbling up" to the end of the list in each pass. \begin{lstlisting}[language=Python, caption=Bubble Sort Implementation] def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] \end{lstlisting} \subsubsection{Quick Sort} Quick sort is a divide-and-conquer algorithm that selects a pivot and partitions the array around the pivot. "Divide-and-conquer" refers to the strategy of breaking down a problem into smaller sub-problems, solving each recursively, and then combining the solutions. In quick sort, a "pivot" is an element chosen from the array, and the goal is to rearrange the array so that all elements less than the pivot come before it, and all elements greater come after it. This process is called "partitioning". After partitioning, the same procedure is recursively applied to the sub-arrays on either side of the pivot until the entire array is sorted. \begin{lstlisting}[language=Python, caption=Quick Sort Implementation] def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) \end{lstlisting} \subsection{Search Algorithms} \subsubsection{Binary Search} Binary search finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half. Initially, it compares the target value with the middle element of the array. If the target is equal to the middle element, the search is complete. If the target is less than the middle element, the search continues on the left half of the array. If the target is greater, it proceeds with the right half. This process continues, halving the search space each time, until the target is found or the interval is empty. This logarithmic reduction of the search space makes binary search highly efficient for sorted arrays. \begin{lstlisting}[language=Python, caption=Binary Search Implementation] def binary_search(arr, target): low = 0 high = len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return -1 \end{lstlisting} \section{Conclusion} This document provided a high-level overview and practical implementations of basic data structures and algorithms. These components are essential tools for efficient programming and problem solving. The accompanying program demonstrates how these algorithms behave in practice and highlights their differences in performance and use cases. \end{document}