Skip to content

2023 Exam B

QUESTION 1

  1. A
#include <stdio.h>

struct s;
typedef struct s * s_type;

int main(void) {
    s_type var;
    printf("The address of var is %p\n", var);
    return 0;
}
  1. B
#include <stdio.h>
#include <stdlib.h>

struct s;
typedef struct s * s_type;

int main(void) {
    s_type var = (s_type) malloc(sizeof(struct s));
    printf("The address of var is %p\n", var);
    return 0;
}

For each \(A\) and \(B\) codes:

  1. Will the code compile?

  2. Will the code run?

Justify your answer.

Analysis of Code A

  1. Will the code compile?
    Yes, the code will compile. The struct s is declared as an incomplete type, but this is allowed when defining a pointer to it (s_type). The code does not attempt to dereference the pointer or use sizeof on the incomplete type, so there are no compilation errors.

  2. Will the code run?
    Yes, the code will run and execute to completion. However, note that var is an uninitialized pointer, so printing its value with %p results in undefined behavior (it may print garbage, NULL, or potentially cause issues, but the program will still run).

Analysis of Code B

  1. Will the code compile?
    No, the code will not compile. The expression sizeof(struct s) is invalid because struct s is an incomplete type (only declared, not defined), and C does not allow sizeof on incomplete types. This will result in a compilation error.

  2. Will the code run?
    No, the code will not run because it fails to compile.

QUESTION 2

Implement a function count in JAVA Python, and C++ with the following restrictions:

  1. Function count takes a collection of elements, you can choose which collection to use for each language, and returns an integer value.

  2. Function count must return how many elements in the collection makes a function accept return true.

  3. Function accept takes one argument (with the same type as the elements in the collection taken by count); it will return true if the element satisfies the condition or property stated by accept, otherwise it will return false.

  4. The collection on which count operates can be empty but it cannot be NULL or None.

  5. If you use a function argument to represent the accept function, this cannot be NULL.

  6. The function must be generic, it must work with any type for the elements in the collection; if you use an argument to pass a function accept, this cannot be NULL or None.

  7. You can add a size argument if you are using an array in either C or C++.

For each implementation you need to explain advantages and disadvantages of the implementation.

Java

@FunctionalInterface
public interface Predicate<T> {
    boolean test(T t);
}

public class Count {
    public static <T> int count(T[] elements, Predicate<T> accept) {
        if (elements == null) {
            throw new IllegalArgumentException("Collection cannot be null");
        }
        if (accept == null) {
            throw new IllegalArgumentException("Accept function cannot be null");
        }

        int counter = 0;
        for (int i = 0; i < elements.length; i++) {
            if (elements[i] != null && accept.test(elements[i])) {
                counter++;
            }
        }
        return counter;
    }
}

Advantage:

It checks if the array or function is null and skips null items in the array so it won't crash if the function can't handle nulls.

It uses generics, so you can use it with numbers, strings, or anything, easily with short code like lambdas.

Disadvantages

It only takes arrays, not lists or other collections, so you need to change your data to an array and it doesn't work on LinkedList for example

It relies on accept method, so it is user's responsibility to define it well

Python

def count(elements, accept):
    if elements is None:
        raise ValueError("Collection cannot be None")
    if accept is None:
        raise ValueError("Accept function cannot be None")

    counter = 0
    for e in elements:
        if e is not None and accept(e):
            counter += 1
    return counter

Advantages

It works on any collections like lists or sets, not just array, so it's easy to use with different collection

It checks if the collection or function is None and raises an error, which stops crashes

It skips None items before checking them, so it won't crash if the function can't handle None.

Disadvantages

It doesn't check if "elements" can be iterated so it could crash if you pass something wrong like a number.

We cannot check if array and elem are actually the type we require

It relies on accept method, so it is user's responsibility to define it well

C++

#include <cassert>

template<typename T>
using Predicate = bool (*)(T);

template<typename T>
int count(T elements[], const int size, Predicate<T> accept) {
    assert(elements != nullptr);
    assert(size >= 0);
    assert(accept != nullptr);

    int counter = 0;
    for (int i = 0; i < size; ++i) {
        if (elements[i] != nullptr && accept(elements[i])) {
            ++counter;
        }
    }
    return counter;
} 

#include <cassert>
#include <type_traits> // For std::is_pointer_v

template<typename T>
using Predicate = bool (*)(T);

template<typename T>
int count(T elements[], const int size, Predicate<T> accept) {
    if (elements == nullptr) throw std::invalid_argument("elements cannot be null");
    if (size < 0) throw std::invalid_argument("size cannot be negative");
    if (accept == nullptr) throw std::invalid_argument("accept cannot be null");

    int counter = 0;
    for (int i = 0; i < size; ++i) {
        if constexpr (std::is_pointer_v<T>) {//If T is a pointer, it will have null element
            if (elements[i] != nullptr && accept(elements[i])) {
                ++counter;
            }
        } else { //If T is not a pointer like int, it won't have null element
            if (accept(elements[i])) {
                ++counter;
            }
        }
    }
    return counter;
}

Advantages

It uses templates to handle different types like ints or strings, making it flexible

It uses asserts to check for null array, negative size, or null function and skips null items in the array, which avoids crushing due to error argument

Disadvantages

It only takes arrays, not lists or other collections, so you need to change your data to an array

There is no way to verify size is indeed the size of the array. If size is too large, it is likely to cause illegal memory access

It relies on accept method, so it is user's responsibility to define it well

Question 3

Is a linearly organized collection of values implemented over linked nodes, an Abstract Data Type? Justify your answer.

No

An abstract data type just outlines what kind of data you're dealing with and what actions you can take on it, but it ignores the details like how the data is actually stored in memory or how those actions are implemented

But a linked list is a specific implements—using nodes connected by pointers (each node holds a value and a link to the next). This is a concrete implementation

Question 4

Is the definition of the Copy-Constructor correct?

class my_class {
public:
    //Empty constructor, initializes the value field with 0
    my_class(): value(0) {}

    //Constructor taking a value for the value field
    my_class(int v): value(v) {}

    //Copy-Constructor
    my_class(my_class other) {
        value = other.value;
    }

private:
    int value;
};

Justify your answer

No, the copy constructor should pass by reference. If we pass by value, to copy the value of an object, the copy constructor is needed, then we will have a circular requirement

QUESTION 5

Given the two following Python modules:

a.py

def function_in_a():
    print("Hello, I'm A!\n")

import b

function_in_a()
b.function_in_b()

b.py

def function_in_b():
    print("Hello, I'm B!\n")

if __name__ == "__main__":
    import a
    a.function_in_a()
    function_in_b()

What would be the output of running:

  1. ​python3 a.py​

  2. ​python3 b.py​

Justify your answer for each case.

  1. Output of python3 a.py​
Hello, I'm A!

Hello, I'm B!

Justification: When running a.py directly, it's the main module (__name__ == "__main__"). It defines function_in_a, imports b.py (which defines function_in_b but skips its if __name__ == "__main__" block since b is imported, not main). Then a.py calls function_in_a() (prints A's message) and b.function_in_b() (prints B's message).

  1. Output of python3 b.py​
Hello, I'm A!

Hello, I'm B!

Hello, I'm A!

Hello, I'm B!

Justification: When running b.py directly, it's the main module (__name__ == "__main__"). It defines function_in_b, then enters the if block: imports a.py, which executes a.py's module-level code—defining function_in_a, importing b.py again (as a separate module "b", which defines its own function_in_b but skips the if block), calling function_in_a() (prints A's message once), and calling the imported b.function_in_b() (prints B's message once). Back in b.py's if block, it then calls a.function_in_a() (which prints A's message again) and its own function_in_b() (prints B's message again).

QUESTION 6

Explain why pointer arithmetic in void pointers is considered an undefined behavior?

Void pointers (void*) don't have a specific type size associated with them (unlike int* where you know to add sizeof(int) for p + 1). Without knowing how many bytes to increment/decrement, pointer arithmetic (like adding offsets) can't be reliably performed, so the C/C++ standards classify it as undefined behavior to avoid unpredictable results or crashes.

QUESTION 7

In C++, given a generic node class with a value field, holding the node's value, and a next field, holding a pointer to the next node and the following functions:

  • Constructor
node(T value)

That initializes the node's value to value, and the node's next reference to NULL. - Setter functions

void set_value(T new_value);
void set_next(node<T> * new_next);

Which respectively sets the node's value and node's next reference with new values. - Getter functions

T get_value();
node<T> * get_next();

Which respectively returns the node's value and node's next reference.

A generic list class with a head field declared as node<T> * head; and a size field declared as int list_size.

Complete the following code (specified by a //TODO: complete comment):

//Empty constructor: constructs a new, empty, list.
list() {
    //TODO: complete
}

//Destructor
~list() {
    //TODO: complete
}

//Removes the value at a specific position
T remove_at(int pos) {
    assert(pos >= 0);
    assert(pos < list_size);
    //TODO: Complete
}

//Returns the value at a specific position
T at(int pos) {
    assert(pos >= 0);
    assert(pos < list_size);
    node<T> * current = head;
    int i = 0;
    while (i < pos) {
        //TODO: complete
    }
    return current.get_value();
}

int size() {
    return list_size;
}

Answer

class list {
public:
    node<T>* head;
    int list_size;

    // Empty constructor: constructs a new, empty, list.
    list() {
        head = nullptr;
        list_size = 0;
    }

    // Destructor
    ~list() {
        node<T>* current = head;
        while (current != nullptr) {
            node<T>* next_node = current->get_next();
            delete current;
            current = next_node;
        }
    }

    // Removes the value at a specific position
    T remove_at(int pos) {
        assert(pos >= 0);
        assert(pos < list_size);

        node<T>* current = head;
        T removed_value;

        if (pos == 0) {
            // Removing the head node
            removed_value = head->get_value();
            head = head->get_next();
            delete current;
        } else {
            // Traverse to the node just before the one to be removed
            node<T>* prev = nullptr;
            for (int i = 0; i < pos; ++i) {
                prev = current;
                current = current->get_next();
            }
            // `current` is now the node to remove
            removed_value = current->get_value();
            prev->set_next(current->get_next());
            delete current;
        }

        list_size--;
        return removed_value;
    }

    // Returns the value at a specific position
    T at(int pos) {
        assert(pos >= 0);
        assert(pos < list_size);
        node<T>* current = head;
        int i = 0;
        while (i < pos) {
            current = current->get_next();
            i++;
        }
        return current->get_value();
    }

    int size() {
        return list_size;
    }
};

QUESTION 8

Can a program always be considered an algorithm?
Justify your answer.

No The program Is a set of instruction that can be executed
But the algorithm should be a finite set of instruction that can be executed, which means if a program have infinite instruction is not the algorithm

For example

while(True):
    print("Hello, world")

‍