These exercises are some I did while studying for COMP2521, as well as some others which I've found afterwards which I think will be relevant. I've collected these problems mostly from LeetCode and HackerRank, which are excellent sites for practicing your coding abilities. Accounts on both sites will be necessary to do the problems listed.
The difficulty ranking is my opinion, but generally speaking here is what they mean:
- Easy: problems that you should be able to do with minimal difficulty
- Intermediate: problems that are a bit harder but doable; may take a little bit of thought and intuition
- Challenges: problems that I think are difficult and/or interesting, if you're up for it; possibly beyond the scope of 2521
Based on past exams, most practical exam questions fall in the Easy and Intermediate categories, and more often than not in the Easy category. If you're able to solve the Easy and Intermediate problems without much difficulty, you're probably very well prepared for any exam questions you'll receive (curveballs notwithstanding).
I'm also additionally marking problems I'd recommend most (regardless of their difficulty ranking) with a star (★). These are the ones I think are the most important, either because they're fundamental or I think they'd be most similar to exam questions.
First, if it's crunch time and you don't have very long to prepare for your 2521 exam, attacking these exercises is not the best use of your time. The theory component is ultimately king in terms of marks allocated in the final exam, and unfortunately doing these exercises likely won't help you understand theory (though, you may learn a few useful things regardless). This list is intended for people who already have a good plan to study for theory, and are looking for something solid to supplement this to take care of studying for the practical section, since course materials can be hit or miss.
As for actually doing these, I strongly encourage you when you're doing these exercises to think of different ways to do the problem, looking to reduce your time and space complexity as much as possible. While having any solution that works is (usually) enough in an exam, you can learn a lot by trying to come up with more efficient algorithms. This is also a skill which will serve you well in the natural successor to this course, COMP3121/3821.
I also strongly recommend you to not look at the official solution or other users' solutions until you've come up with something on your own. It's too easy to see a solution to a problem and trick yourself into thinking "I would've come up with that!" prematurely; you're cheating yourself out of a valuable learning experience too. Beware that some C solutions you come across to these problems also do some things which go against best practices in COMP2521 (e.g. simply overwriting pointers between linked lists rather than freeing the underlying memory). Submissions on these websites don't take style into account, but I would encourage you to write your solutions under the assumption that your style is being taken into account.
- Build up a linked list from the head
- Build up a linked list from the tail
- Insert a node at specific position in a linked list ★
- Insert a node into a sorted doubly-linked list ★
- Compare two linked lists ★
- Find the middle node of a linked list
- Reverse a linked list ★
- Reverse a doubly-linked list ★
- Remove all nodes with a certain value in a linked list ★
- Remove all duplicate nodes in a linked list ★
- Remove the nth last node from a linked list ★
- Determine if a linked list is palindromic ★
- Show the elements of a linked list in reverse order
- Merge two sorted linked lists, efficiently ★
- Reverse only part of a singly-linked list
- Find the point of intersection of two linked lists ★
- Swap all node pairs in a linked list
- Rotate a linked list by n places
- Remove all nodes with duplicates from a linked list ★
- Determine if a linked list has a cycle
- Find the first node of a cycle in a linked list
- Implement insertion sort for linked lists
- Implement the partitioning phase of quick sort for linked lists
- Swap all nth first and nth last node pairs in a linked list
- Remove all nodes which form a consecutive zero-sum sequence from a linked list
Note that in some of these problems, the tree is not necessarily a search tree.
- Find a node in a binary search tree ★
- Find the sum of all left leaf nodes in a binary tree
- Find the maximum depth of a binary tree ★
- Find the minimum depth of a binary tree ★
- Show the preorder traversal of a binary tree ★
- Show the inorder traversal of a binary tree ★
- Show the postorder traversal of a binary tree ★
- Determine if a binary tree is height balanced ★
- Compare two binary trees ★
- Determine if a binary tree is symmetric
- Invert a binary tree
- Calculate the tilt of a binary tree
- Determine if a binary tree is univalued
- Find the sum of all nodes in a given range ★
- Find the kth smallest node in a binary search tree ★
- Determine if a binary tree is a subtree of another ★
- Find the minimum absolute difference between two nodes in a binary tree
- Find the lowest common ancestor of two nodes in a binary search tree
- Find the lowest and leftmost node in a binary tree
- Remove a specific node from a binary search tree
- Find a root-to-leaf path in a binary search tree with a given node sum
- Determine if a binary tree is a binary search tree ★
- Count the number of nodes in a complete binary tree ★
- Show the infix sequence of values of two binary search trees
- Convert the preorder traversal of an N-ary tree to an array
- Convert the postorder traversal of an N-ary tree to an array
- Decode a Huffman-encoded string given its Huffman tree
- Convert a sorted linked list to a balanced BST
- Convert a binary tree into a degenerate binary tree in-place
- Build a binary tree given its preorder and inorder traversals
- Build a binary tree given its inorder and postorder traversals
- Recover a binary search tree
Note that there is a disappointing number of good 2521-style graph problems available, so I'm mostly going to give ideas for problems. This obviously takes time, so apologies if this section is empty when you view this page. For exercises without a link, you're welcome to just theorise about how you'd solve it and describe solutions in pseudocode, or you can try to implement a graph, test cases and the actual solutions to these problems in C.
- Find the sum of all even-numbered nodes in a graph ★
- Find the node in a graph with maximum value ★
- Count the number of edges in a graph ★
- Think about how you'd do this for each representation of a graph you've learned.
- Find the shortest path between two vertices in an unweighted, undirected graph
- Count the number of islands in a grid-like map
- Note that the data structure here is a 2D array, but graph-like thinking is very helpful. How would you apply what you know about graphs to something like this?
- Find a minimal spanning tree in a weighted, undirected graph
- You've learned 2 algorithms for doing this. Which one should you apply when, and why?
- Determine if a graph is bipartite
- If you're not a maths person, here's the definition of bipartite.
- Determine if a course plan is possible
- Once again, the data structure here is a 2D array, but graph-like thinking is very helpful. Identify what it means in terms of graphs for a course plan to be impossible to finish - this will give you ideas.
- Build a copy of a graph
- The copy should be a deep copy, meaning that each node should be a distinct object in memory from the companion node in the original graph. Being cheeky and just returning the original graph is not how you should do this question!
- Construct the transpose of a given graph
- Count the number of strongly connected components in a graph