Data Structures and Algorithms Examination Notes

Examination Structure and Requirements

  • Course Information

    • Course Name: Data Structures and Algorithms
    • Course Code: PR05
    • Academic Year: 2024-2025
    • Block Period: 2
    • Mock Test Date: NA
    • Exam Supervisors: E. van den Aker, R. Bindels
    • Maximum Points: 85
    • Points needed to pass: 47
    • Point scale calculation: ( PI = \frac{(P-E)}{(T-E)} \times 10 )

  • Instructions for Candidates

    • Allowed aids: Writing utensils, black or blue ink pen
    • Check for completeness and report any missing parts
    • Complete necessary entries on the form/answer sheet
    • Submit all materials to the exam supervisor

Key Questions and Topics

Abstract Data Types
  • Definition: An abstract data type (ADT) is a mathematical model for data types where the data type is defined by its behavior from the point of view of a user, specifically the operations that can be performed on it.
Basic Data Structures and Functions

  • Heap and Priority Queue

    • A: A heap can be implemented using a priority queue.
    • B: A priority queue can be implemented using a heap.
    • Options:
    • a) Only A is true
    • b) Only B is true
    • c) Both A and B are true
    • d) Both are false

  • Reversing an Array

    • Function implementation required in Python or pseudocode.

  • Finding an Element in a Linked List

    • Function implementation required in Python or pseudocode.
Arrays vs. Linked Lists
  • Advantages of Arrays:
    • Fast random access due to contiguous memory allocation.
  • Disadvantages of Arrays:
    • Fixed size; resizing requires creating a new array.
  • Advantages of Linked Lists:
    • Dynamic size and ease of insertion/deletion.
  • Disadvantages of Linked Lists:
    • Slower access time as nodes are scattered in memory.
Searching Algorithms

  • Binary Search

    • Function needed for sorted arrays.
    • Time Complexity: O(log n)

  • Stack Implementation:

    • Use an array for implementation; include push and pop functions.
Stack vs. Queue
  • Stack:
    • LIFO (Last In First Out) structure.
  • Queue:
    • FIFO (First In First Out) structure.
  • Key Differences:
    • Stacks use push/pop; queues use enqueue/dequeue.
Trees and Heaps
  • Ordered Binary Tree Construction
    • Construct tree using numbers: 5, 8, 6, 2, 3, 7, 1.
  • Max Heap Construction
    • Construct heap using numbers: 5, 8, 6, 2, 3, 7, 1.
Complexity and Optimization
  • Dynamic Programming:
    • Method to optimize algorithms by storing results of expensive function calls.
  • Fibonacci Function:
    • Implementation using dynamic programming to find the nth Fibonacci number, where: ( F0 = 0, F1 = 1, Fn = F{n-1} + F_{n-2} ).
Algorithm Complexity
  • Mergesort:
    • Average and worst-case complexity is ( O(n \log n) ).
  • Complexity Visualization:
    • Draw O(1), O(n), O(n log n), O(2^n), O(n²) with proper labels.
  • Power Calculation:
    • Calculate required multiplications using standard method vs. Horner’s Algorithm.
  • Snippet Complexity:
    • Python code provided results in ( O(n^2) ).
Performance Analysis
  • Algorithm Performance:
    • Given a complexity of ( n^3 ) for an algorithm, calculate time for different values of n, e.g., from 2000 to 8000.