Unit 1:
Arrays:
Definition: A collection of values of the same type stored in consecutive memory locations, accessed by integer indices.
Operations:
● create(int length): Initializes a new array.
● set(int index, Object value): Sets the value at a specified index.
● get(int index): Retrieves the value at a specified index.
Abstract Data Types (ADTs):
● Combines interface, behavior, and running time requirements without specifying implementation details.
● Example operations: create, set, get.
● Running time for set and get operations is constant (O(1)).
Lists
Definition: A sequence of data items, e.g., Java's LinkedList and ArrayList.
Operations:
● create(): Initializes a new list.
● isEmpty(): Checks if the list is empty.
● length(): Returns the number of items in the list.
● insert(int index, String s): Inserts an item at a specified index.
● get(int index): Retrieves the item at a specified index.
● delete(int index): Deletes the item at a specified index.
Types:
● Singly Linked List: Each item has a reference to the next item.
● Doubly Linked List: Each item has references to both the next and previous items.
● Comparisons with Arrays:
● Lists can grow/shrink dynamically, whereas array sizes are fixed.
● Lists support natural insertion/deletion, arrays require copying.
Queues
Definition:A queue is an abstract data type that follows the First-In-First-Out (FIFO) principle. It can be visualised as a line of objects where the first object added is the
first one to be removed. Queues are used to manage elements in the order they were added.
● Operations:
● create(): Initializes a new queue.
● isEmpty(): Checks if the queue is empty.
● length(): Returns the number of items in the queue.
● add(String s): Adds an item to the back of the queue.
● remove(): Removes and returns the front item of the queue.
Implementation:
● Typically implemented as a singly linked list.
● Operations add and remove run in constant time (O(1)).
Stacks
Definition: A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle. It can be visualized as a vertical stack of objects where the last object
added is the first one to be removed. Stacks can be implemented using references or arrays.
.
Operations:
● create(): Initializes a new stack.
● isEmpty(): Checks if the stack is empty.
● length(): Returns the number of items on the stack.
● push(String s): Adds an item to the top of the stack.
● pop(): Removes and returns the top item of the stack.
Implementation:
● Can be implemented as a backwards singly linked list.
● Operations push and pop are performed at the list's head.
● Time complexity for push and pop operations is constant (O(1)).
Summary
● Arrays: Fixed size, constant time access, used for homogeneous data.
● Lists: Dynamic size, supports easy insertion/deletion, used for sequences of data.
● Queues: FIFO structure, constant time operations, used in scheduling and order processing.
● Stacks: LIFO structure, constant time operations, used in function calls and depth-first search.
Abstract Data Types (ADTs)
Definition: ADTs specify a data structure by defining the operations that can be performed on the data, the behavior of these operations, and their running times.
They do not specify implementation details or language-specific constructs.
Components:
● Interface: Defines the available operations.
● Behavioral Description: Describes what the operations do.
● Running Time Requirements: Specifies the performance expectations for the operations.
● Purpose: ADTs allow programmers to use data structures in a consistent and predictable manner, regardless of how they are implemented.
Linked Lists:
Definition: A type of list where each item (node) contains a reference to the next item in the sequence.
Types:
● Singly Linked List: Each node has a reference to the next node.
● Doubly Linked List: Each node has references to both the next and previous nodes.
● Operations:
● create(): Initializes a new linked list.
● isEmpty(): Checks if the list is empty.
● length(): Returns the number of items in the list.
● insertAtHead(String value): Inserts an item at the head of the list.
● insertAtTail(String value): Inserts an item at the tail of the list.
● deleteHead(): Removes the head item of the list.
● deleteTail(): Removes the tail item of the list.
● insert(int index, String value): Inserts an item at a specified index.
● delete(int index): Deletes an item at a specified index.
● get(int index): Retrieves the item at a specified index.
Advantages:
● Dynamic size: Can grow and shrink as needed.
● Efficient insertions and deletions, especially at the head or tail.
, Disadvantages:
● Access time for retrieving the ith element is linear (O(n)) as it requires traversal from the head.
Unit 2:
Binary Trees
Definition: A tree where each node has up to two children.
● Nodes: Elements in the tree (e.g., a, b, c, etc.).
● Root: The top node with no parent.
● Leaf: A node with no children.
● Subtree: A tree consisting of a node and its descendants.
Operations:
● create(String s): Creates a one-node tree.
● join(String s, Tree left, Tree right): Creates a tree with specified root and subtrees.
● isLeaf(): Checks if the tree has one node.
● leftChild(), rightChild(): Returns the left or right subtree.
● value(): Returns the value stored at the root.
Traversal Methods:
● Pre-order: Process node, then left subtree, then right subtree.
● Post-order: Process left subtree, right subtree, then node.
● In-order: Process left subtree, node, then right subtree.
Binary Search Trees (BSTs)
Definition: A binary tree where for each node, all values in the left subtree are less, and all values in the right subtree are greater.
Operations:
● create(): Initializes an empty BST.
● isEmpty(): Checks if the BST is empty.
● size(): Returns the number of items in the BST.
● contains(int i): Checks if a value is in the BST.
● insert(int i): Adds a value to the BST.
● delete(int i): Removes a value from the BST.
Performance: Operations contains(), insert(), and delete() are proportional to the tree's height.
Height: The number of levels in the tree. A balanced BST has height proportional to log2(n), where n is the number of nodes.
Priority Queues:
Definition: A data structure where each item is associated with a priority. Items with higher priority (lower numerical value) are processed first.
Operations:
● create(): Initializes an empty priority queue.
● isEmpty(): Checks if the queue is empty.
● size(): Returns the number of items in the queue.
● insert(int p, Object obj): Inserts an item with a given priority.
● next(): Removes and returns the highest-priority item.
Implementation: Often implemented using a binary heap.
● Heap Property: Every node is less than or equal to its children.
● Shape Property: The tree is a complete binary tree (all levels are fully filled except possibly the last, which is filled from left to right).
● Stored in an array for efficient access and manipulation.
● Insertion: Adds a new item and "bubbles up" to maintain heap property.
● Removal: Removes the root, replaces it with the last item, and "bubbles down" to maintain heap property.
Non-Binary Trees:
● General Trees: Nodes may have any number of children.
● Left-Child, Right-Sibling Representation: Uses left and right pointers to represent the first child and next sibling, respectively.
Summary
● Binary Trees: Basic tree structure with efficient traversal methods (pre-order, post-order, in-order).
● Binary Search Trees: Efficient for dynamic sets with fast search, insert, and delete operations, typically proportional to log2(size).
● Priority Queues: Efficient for processing items by priority using binary heaps, with operations proportional to log2(size).
● Non-Binary Trees: Flexible structure for nodes with multiple children, often represented using left-child, right-sibling pointers for simplicity.
Unit 3:
Algorithm Analysis :
● Algorithm analysis in the context of data structures and algorithms involves evaluating and comparing algorithms based on their efficiency and
performance characteristics. It helps us understand how an algorithm's execution time and memory usage grow as the input size increases.
● One commonly used measure in algorithm analysis is the Big O notation. It provides an upper bound on the growth rate of an algorithm's time complexity
or space complexity. The Big O notation expresses the worst-case scenario, indicating the maximum amount of resources an algorithm requires. It helps us
estimate how an algorithm scales with larger inputs.
● Depth-First Search (DFS): Depth-First Search explores a graph by traversing as far as possible along each branch before backtracking. It uses a stack or
recursion to keep track of visited vertices.
● Breadth-First Search (BFS): Breadth-First Search explores a graph level by level, visiting all neighbors of a vertex before moving to the next level. It uses a
queue to keep track of visited vertices.
Goal: Predict the performance of algorithms.
Challenge: Predicting exact time in seconds isn't feasible due to variations in hardware, compiler efficiency, and language differences.
Primitive Operations:
● Definition: Basic CPU instructions like variable assignments and arithmetic operations.
● Running Time: Estimated by counting the number of primitive operations.
Scalability
● Objective: Understand how performance scales with data size (n).
Examples:
● Inserting into a sorted list: time proportional to n.
● Inserting into a priority queue: time proportional to log2(n).
Asymptotic Behavior:
● Focus: Performance as n approaches infinity.
● Concept: Ignore constant factors and lower-order terms (terms that become insignificant as n grows).
Ignoring Constant Factors
● Justification: Constant factors depend on implementation details, which we're abstracting away.
● Exception: When comparing similar approaches, constant factors may be relevant.
