Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-opus-4-20250514· AnthropicHugging Face LMArena Human Preference 140K

Please generate a series of exam questions for a university course on algorithms and…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Mistralmistral-small-3.1-24b-instruct-2503’s answer.
  1. User

    Please generate a series of exam questions for a university course on algorithms and data structures.

  2. Claude Assistant

    Here are exam questions for a university algorithms and data structures course:

    Question 1: Time Complexity Analysis (15 points)

    Consider the following pseudocode:

    function mystery(A[1...n])
        for i = 1 to n
            j = i
            while j > 1 and A[j] < A[j-1]
                swap(A[j], A[j-1])
                j = j - 1
    

    a) What sorting algorithm does this implement? (3 points) b) Analyze the worst-case time complexity. Show your work. (6 points) c) Analyze the best-case time complexity. Show your work. (6 points)

    Question 2: Binary Search Trees (20 points)

    a) Draw the binary search tree that results from inserting the following keys in order: 50, 30, 70, 20, 40, 60, 80, 10, 25, 35 (5 points)

    b) Show the tree after deleting node 30 from your tree in part (a). Explain which deletion strategy you used. (5 points)

    c) What is the height of the original tree from part (a)? If we inserted n random keys into an initially empty BST, what would be the expected height? (5 points)

    d) Convert your tree from part (a) into an AVL tree by performing the necessary rotations. Show each rotation step. (5 points)

    Question 3: Graph Algorithms (25 points)

    Given the following weighted directed graph:

    • Vertices: A, B, C, D, E, F
    • Edges: A→B(4), A→C(2), B→C(1), B→D(5), C→D(8), C→E(10), D→E(2), D→F(6), E→F(3)

    a) Run Dijkstra's algorithm starting from vertex A. Show the distance table after each iteration. (10 points)

    b) Run the Bellman-Ford algorithm starting from vertex A. Show the distance values after each of the |V|-1 iterations. (10 points)

    c) Explain why we might choose Bellman-Ford over Dijkstra's algorithm in certain scenarios. Provide a specific example. (5 points)

    Question 4: Dynamic Programming (20 points)

    The "House Robber" problem: You are a robber planning to rob houses along a street. Each house has a certain amount of money stashed. Adjacent houses have security systems connected, so you cannot rob two adjacent houses. Given an array of non-negative integers representing the amount of money in each house, determine the maximum amount you can rob.

    a) Define the recurrence relation for this problem. Clearly state what your subproblems represent. (8 points)

    b) Write pseudocode for a dynamic programming solution. (8 points)

    c) What is the time and space complexity of your solution? Can you optimize the space complexity? If so, how? (4 points)

    Question 5: Hash Tables (20 points)

    a) Explain how separate chaining and open addressing handle collisions differently. What are the advantages and disadvantages of each approach? (8 points)

    b) A hash table uses the hash function h(k) = k mod 13. Show the resulting hash table after inserting the keys {18, 41, 22, 44, 59, 32, 31, 73} using:

    • Separate chaining (6 points)
    • Linear probing (6 points)

    Question 6: Heap Operations (15 points)

    Starting with an empty min-heap, show the heap structure after each of the following operations:

    1. Insert: 15, 10, 20, 8, 21, 23, 12
    2. Extract-min
    3. Insert: 5
    4. Extract-min
    5. Extract-min

    Draw the heap as a tree after each operation and show the array representation.

    Question 7: Algorithm Design (15 points)

    Design an algorithm to find the k-th largest element in an unsorted array. Your solution should have better average-case time complexity than O(n log n).

    a) Describe your algorithm in detail. (8 points) b) Analyze its average-case and worst-case time complexity. (5 points) c) What is the space complexity? (2 points)

    Bonus Question (10 points)

    Prove that in any connected, undirected graph G = (V, E) with |V| vertices and |E| edges, we must have |E| ≥ |V| - 1. Then prove that if |E| = |V| - 1, the graph must be a tree.


    Grading Notes:

    • Total: 120 points (110 regular + 10 bonus)
    • Show all work for partial credit
    • Time limit: 3 hours
    • Closed book, one page of handwritten notes allowed

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.