Data Structures and Algorithms Quiz

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What data structure is used to represent a graph in an adjacency list format?

An array of linked lists (correct)

A binary tree

A single array

A hash set

Which operation in an adjacency list representation has a time complexity that notably differs from an adjacency matrix when adding a node?

Adding a node (correct)

Adding an edge

Finding neighbors of a node

Are two nodes adjacent?

What is the primary limitation of using an adjacency matrix for a sparse graph?

It consumes more memory due to storing many zeroes (correct)

It slows down adding new nodes

It facilitates easy traversal

It simplifies edge lookup

In a scenario where you frequently check if two nodes are adjacent, which representation would be more efficient?

Adjacency matrix Signup and view all the answers

What advantage does an adjacency list have over an adjacency matrix when managing a dynamic graph?

Lower memory usage Signup and view all the answers

What is a key advantage of using a linked list over a dynamic array?

No need to allocate a fixed block of contiguous memory in advance Signup and view all the answers

What is the purpose of the calculation start + cell_size * index in low-level arrays?

To access the exact memory address of a desired cell Signup and view all the answers

Which operation on a singly linked list has a time complexity of O(n)?

Deleting the last node Signup and view all the answers

How does a doubly linked list improve efficiency compared to a singly linked list?

By maintaining references to both the previous and next nodes Signup and view all the answers

What does the id() function in Python return?

A unique identifier for the specified object Signup and view all the answers

What is the purpose of using header and trailer nodes in a linked list?

To avoid special cases when performing operations at the boundaries of the list Signup and view all the answers

Which of the following statements about the time complexity of operations in a linked list is true?

Insertion and deletion can be performed in O(1) time if pointers are adjusted correctly Signup and view all the answers

Why would the outputs of the id() function differ when the same script is run multiple times?

Python determines new memory locations based on current availability Signup and view all the answers

Which characteristic is true about low-level arrays?

They allow constant time access to any cell based on its index Signup and view all the answers

What happens when a dynamic array reaches its capacity according to the growth strategy of doubling?

The new capacity becomes twice the current capacity. Signup and view all the answers

What is the amortized running time of each append operation in a dynamically growing array using geometric increase?

O(1) Signup and view all the answers

Which representation of expressions does NOT require parentheses?

Postfix Signup and view all the answers

Why does performing a series of n append operations with a fixed increment take Ω(n²) time?

The fixed increments cause frequent resizing. Signup and view all the answers

What will be the value of 'tmp' after the expression 'tmp = primes[3:6]' followed by 'tmp = 15'?

15 Signup and view all the answers

In a postfix expression, where is the operator placed in relation to its operands?

After the operands Signup and view all the answers

What is the result of the expression '*+AB+CD' in infix form?

(A + B) * (C + D) Signup and view all the answers

What capacity growth strategy is more efficient in terms of time complexity for append operations?

Doubling the capacity Signup and view all the answers

What condition must a binary tree meet to be classified as complete?

All nodes at level h - 1 and above must have two children. Signup and view all the answers

What is the maximum number of nodes at level 3 of a binary tree?

7 Signup and view all the answers

How many total nodes can a binary tree of height 2 have at most?

7 Signup and view all the answers

Which statement is true regarding balanced binary trees?

The height of any node's right subtree differs from the left by no more than 1. Signup and view all the answers

What is the definition of a full binary tree?

Each node has exactly zero or two children. Signup and view all the answers

Which of the following statements is false regarding complete binary trees?

Complete binary trees require all nodes to be filled on the last level. Signup and view all the answers

For a complete binary tree of height 0, what is the maximum number of nodes?

1 Signup and view all the answers

Which condition does NOT apply to a balanced binary tree?

The difference in height between subtrees is more than 2. Signup and view all the answers

What is a requirement for applying topological sort on a graph?

The graph must be acyclic. Signup and view all the answers

In topological sorting, how is the order of nodes determined?

Each node appears before the nodes it points to. Signup and view all the answers

How many different valid topological sorts can a directed acyclic graph have?

Multiple valid sortings. Signup and view all the answers

What does Dijkstra’s algorithm aim to find in a graph?

The shortest path from a start node to all other nodes. Signup and view all the answers

Which sorting algorithm is notably recognized for its divide and conquer approach?

Merge Sort Signup and view all the answers

Which of the following statements about topological sort is incorrect?

It can include nodes with cycles. Signup and view all the answers

What is the main goal of a Trie data structure?

To efficiently perform string operations. Signup and view all the answers

What common characteristic do Merge Sort and Quick Sort share?

Both use the divide and conquer strategy. Signup and view all the answers

Study Notes

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.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

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.