Data Structures and Algorithms Quiz

CSC2720 Final Exam Review

• Exam Schedule: Wednesday, December 11, 2024, 11:00 AM - 1:00 PM, Urban Life Building Room 100
• Exam Format: 30% of the total grade, closed book.
• Allowed Materials: One A4-size handwritten, double-sided note. Printed notes are not allowed.
• Identification: Panther ID card (or driver's license) required for identity verification.

Big O Notation of Composite Functions

• Composite Function (c.O(f(x))): A composite function is a function that is a constant multiple of another function. Its Big O notation is denoted as O(f(x)).
• Example 1: def print10times(arr):... 10.O(N) ~ O(N) In this example, the function runs 10 times regardless of array size. (O(10)) The nested loop affecting O(N), resulting in O(N).
• Example 2: 10 + O(N) ~ O(N) The constant 10 has a Big O notation of O(1), combined with O(N) the function will run in O(N) time.

Python Lists

• Data Structure: An ordered, mutable collection of items in Python.
• Syntax: sample_list = [item1, item2, ...]
• Mutability: Lists are mutable, meaning their elements can be changed after creation.
• Heterogeneity: List elements can be of different data types.
• Built-in Methods: append(), insert(), remove(), pop(), sort(), sorted(), index() ,and count().

Python Lists - Time Complexity

• index[ ]: O(1)
• index assignment: O(1)
• append, pop(): O(1)
• pop(index): O(n)
• insert(index, item): O(n)
• contains, reverse: O(n)
• sort (): O(n log n)

Python Dictionaries

• Data Structure: A collection of key-value pairs, where keys are unique and values can be any type.
• Operations: copy, get item, set item, delete item, contains, iteration
• Time Complexity: copy: O(n), get item: O(1), set item: O(1), delete item: O(1), contains: O(1), iteration: O(n)

Low-Level Arrays

• Representation: Python internally stores strings as an array of 16-bit (2-byte) Unicode characters.
• Indexing: Memory address of an array element can be calculated using start + cell_size * index.
• Constant Time Access: Arbitrary access to array elements is in constant time O(1).

Referential Arrays

• References: Python variables refer to objects in memory.
• id(): Returns the unique identifier of an object.
• Immutable vs. Mutable: Changing elements in a copy of a list will only affect the copy, not the original. Modifications to a list's elements directly affect the original list.

Amortized Analysis of Dynamic Arrays

• Growth Strategy: Arrays increase in size in increments, typically doubling the size.
• Amortized Time Complexity of Append: O(1) for operations.
• Arithmetic Progression Issues: Fixed incrementing sizes during reallocation can result in O(n²) complexity when appending a series of elements, where n represents the total number of elements. This issue doesn't arise with doubling or geometric growth strategies during reallocation of dynamic arrays, where the time complexity will be O(n).

Evaluating Postfix Expressions

• Properties: The operator is placed after the operands. Left side of the operands are already present.
• Evaluation Steps:
  • Create a stack.
  • Read the expression from left to right.
  • If an operand is read, push it onto the stack.
  • If an operator is read:
    • Pop the necessary operands.
    • Apply the operator.
    • Push the result back onto the stack.
  • The final result is the value remaining on the stack.

Stack and Queues

• Data Structures not covered in this review.

Deque

• Data Structure: A double-ended queue. Allows insertion and deletion at both ends (front and rear).
• Common Operations: add_rear(item), add_front(item), remove_rear(), remove_front(), front(), rear(), is_empty(), size().

Linked Lists

• Memory Efficiency: No need to pre-allocate contiguous memory.
• Efficient Insertions/Deletions: O(1) time complexity because adjusting 'next' pointers is required, unlike shifting elements in an array. Can be used to implement other data structures like stacks or queues.

Doubly Linked Lists

• Each node keeps references to both the preceding and succeeding nodes.
• Improved time complexity for operations involving insertions and deletions at the beginning or end, especially compared to singly linked lists.
• Often include header and trailer nodes which are sentinel(or guard)nodes.

Hash Tables

• Implementation: Use a lookup table (array) and a hash function maps keys(item) to indices (locations/slots in an array), where the hashcode is modular with the size of the table (key%N).
• Collisions: Multiple keys might map to the same index.
• Hash Codes: Function generating an integer from an arbitrary key and used to produce the index.
• Compression Functions: Convert hash codes to valid array indices (e.g., using modular arithmetic). The division method can have limitations in some cases.

Hash Codes - Variable-Length Objects

• The summation and XOR hash codes are not suitable if the order of elements matters.
• Polynomial Hash Codes: Use different weights for elements at different positions (as given in example code) to provide better hash codes for variable-length objects.

Binary Search Tree

Binary Tree - Array-Based Implementation

• Representation: Storage with an array, where index-based calculation is used to traverse child nodes (left = 2i+1, right = 2i+2 and parent = (i-1)/2). The index must start at 0 to be effective.
• Operations: Initialization, insert, find, deletion, get, parent

Priority Queues in Python

• Implementation: using heapq module. heapq often defaults to min-heap. (heappush(), heappop(), heapify(), nlargest(), nsmallest()) will be used for the algorithms.

K-Way Merge

• Idea (Better Solution using Heap): Instead of repeatedly finding the minimum element in O(k), use a min-heap to find the minimum element in O(logk). This approach efficiently combines and processes elements from multiple sorted input lists.

Graph Representations: Adjacency Matrix and Adjacency List

• Adjacency Matrix: Square matrix representing edges (usually boolean). Easy for checking adjacency of two nodes (O(1)); but, adds /removes nodes/edges are O(n^2).
• Adjacency List: Collection of linked lists. Fast lookups/adjacencies are O(1); but, adds/removes nodes/edges are linear for a given graph size. The time complexities to add/remove nodes/edges will be a function of the size of the graph.

Graph Traversals (BFS and DFS)

• Algorithms: Implementations covered through code examples for Breadth-First Search (BFS) and Depth-First Search (DFS) traversal, recursive and iterative for DFS.

Other Important Topics

• Topological Sorting: Ordering nodes in a directed acyclic graph to satisfy predecessors/successors. This will be illustrated/implemented in code.
• Dijkstra's Algorithm: Finding shortest paths in a weighted graph, commonly used for network routing.
• Tries: Implementing a trie data structure, including methods for insertion and retrieval where the methods are implemented in code.
• Sorting Algorithms (Merge Sort and Quick Sort): Understanding and applying the concepts, with code implementations to understand the time complexities of these sorting algorithms.

Test your knowledge on data structures, specifically focusing on graphs and linked lists. This quiz covers concepts like adjacency lists, time complexity, and differences between various representations. Delve into how these structures impact operations and efficiency in dynamic scenarios.