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 obviously my opinion, but generally speaking here is what they mean:
- Easy: Problems that you should be able to do without too much difficulty.
- Intermediate: Problems that are a bit harder, but should be doable with a little bit of thought and intuition.
- Challenges: Problems that I think are difficult and/or interesting, if you're up for it. There are almost all harder than what's within the scope of 2521.
If you're able to solve the easy and intermediate problems without much difficulty, you're probably very well prepared for any programming questions you'll receive in the exam. You can safely ignore the challenges unless you're really keen and/or bored.
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 to try, either because they're fundamental or I think they'd be most similar to exam questions.
Doing these exercises likely won't help you understand theory (but you may learn a few useful things regardless). This list is intended for people who have already studied for theory or have a good plan to study for it, and are looking for something solid to supplement this to take care of studying for the programming section. This also only focuses on programming questions from the 3 major topics in this course, but you could also be asked practical questions for other topics too.
By no means should you feel compelled to do all (or any) of these problems if you want to do well! Someone could totally ignore this list and absolutely ace the course using only the resources posted officially by the course itself. This list was part product of the immense free time I had when taking 2521 after I had exhausted all of those resources, but part product of an interest in problem solving on my part.
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 editorial or other user-posted solutions until you've come up with something on your own, even just an idea. Fair warning: I think a lot of user-posted solutions on these websites are straight up garbage from a learning perspective. They may be algorithmically brilliant, but readability is usually a complete afterthought, and the explanations given are either non-existent or not very good for beginners.
Virtually none of these solutions will be written in C either (since it's way too basic of a language for the types of problems you typically encounter), and the precious little you do come across to these problems may 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. It's just a good habit to get used to (and makes an exam marker's life easier if they have to manually assess your code due to a poor automark).
If you're one of the COMP1511 students who has stumbled upon this list, then you may find the linked list problems to be good extra study material. However, do remember that
- Some of these problems are beyond 1511's scope, as this is a list intended primarily for 2521 students.
- There are other types of problems that you should be practicing too.
The websites featured in this list do have some other 1511-level problems, but they're a bit hard to come by, and you sort of need to know what you're looking for. In general, I would try to avoid these sites, as the average problem assumes a basic level of algorithmic competency that you aren't expected to develop until you start doing 2521. Instead, you're probably better off revising your lab tasks, weekly tests and assignments.
- 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, so you can't depend on the values to be ordered in any particular way.
- 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
- Count the number of downward paths in a binary tree with a given node sum, starting from any node
- Recover a binary search tree after a node swap
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.
- Check if you can visit all locked rooms
- Another one where graph-like thinking is very helpful.
- 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