Data Structures and their Applications

Data Structures and their Applications in CS2004

Overview

• Instructor: Dr. Mahir Arzoky

• Course: Algorithms and their Applications

• Year: 2024-2025

Course Resources

• CodeRunner Tutorials

• CodeRunner Worksheet

• Mock Tests for practice

Event Details

• Hackathon sponsored by Eli Lilly and Company

• Date: 5th November

• Online briefing session: 30th October, 14:00-16:00 (mandatory attendance)

• Prizes available, networking opportunities with recruitment managers

• Registration limited: scan QR code for details

Previous Topics Covered

• Concepts of Computation and Algorithms

• Comparing Algorithms

• Mathematical Foundations related to Algorithms

• Big-Oh Notation and its implications on computational complexity

Current Lecture Topics

Key Data Structures to Discuss:

• Lists

• Stacks

• Queues

• Hash Tables

• Graphs

Importance of Data Structures

• Foundation of Algorithms: Proper data structures significantly enhance algorithm design.

• Efficiency: Choosing the right data structure can optimize performance (e.g., sorting a list).

• Analysis: Use Big-Oh notation to measure data structures’ effectiveness.

Detailed Discussion on Data Structures

Lists

• Definition: A sequence of zero or more data items with a dynamic length.

• Operations: Items can be accessed, inserted, or deleted at any position.

• Implementations:

  • Array: Simple, maintains insertion order, indexed. O(1) for index search.

  • LinkedList: Does not maintain indexes, requires traversal. Complexity: O(n) for search, with O(1) for best-case insertion/deletion at the head, O(n) for worst case.

Stacks

• Characteristic: Insertions and deletions occur at one end (top), following LIFO (Last In, First Out) principle.

• Operations:

  • Push: Add item to the top.

  • Pop: Remove item from the top.

Queues

• Characteristic: Insertions at the rear, deletions at the front (FIFO - First In, First Out).

• Operations:

  • ENQUEUE: Insert item at the rear.

  • DEQUEUE: Remove item from the front.

Hash Tables

• Definition: Maps a key to a value, utilizing a hash function to index the data.

• Key functions: Handle collisions where different keys map to the same index.

Applications of Data Structures

• Lists: Implement other data structures (queues, stacks), mathematical vectors.

• Stacks: Used for reversing strings, undo mechanisms, web navigation, syntax evaluation in compilers.

• Queues: Support single-resource applications like print jobs, email messages, processor tasks.

• Hash Tables: Useful for address books, linking file names/paths, password verification.

Introduction to Graphs

• Definition: A graph consists of nodes (vertices) connected by edges.

• Applications: Road maps, project networks, electrical circuits, and biological connections.

Graph Theory Concepts

Definitions

• Directed Graph: A graph where edges have a direction.

• Undirected Graph: A graph where edges have no orientation.

• Complete Graph: A graph with an edge between every pair of vertices.

• Path: Sequence of vertices connected by edges, with potential cycles.

• Connectivity: Determines if nodes are reachable from one another.

• Weighted Graph: Implements weights for edges to signify the cost/distance.

Graph Representation

• Typically represented as a 2D matrix or adjacency list depending on application requirements.

• Non-weighted graphs use binary indicators for edge presence; weighted graphs retain cost data.

Upcoming Topics

• Next lecture: Focus on sorting algorithms.

• Laboratory: Implementation and study of discussed data structures with practical exercises.