Skip to content

Instantly share code, notes, and snippets.

@aesmi

aesmi/2521_exercises.md

Forked from jedavidson/2521_exercises.md
Created August 10, 2022 07:12
Show Gist options
  • Save aesmi/67dddfaf7ba3a69d24010429f5cf5843 to your computer and use it in GitHub Desktop.
Save aesmi/67dddfaf7ba3a69d24010429f5cf5843 to your computer and use it in GitHub Desktop.
Download ZIP
A curated list of some good revision and exam preparation problems for UNSW's COMP2521. Personal opinion.
Raw
2521_exercises.md

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 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

If you're able to solve the Easy and Intermediate problems without much difficulty, you're probably very well prepared for any practical exam questions you'll receive (curveballs notwithstanding). You could 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, either because they're fundamental or I think they'd be most similar to exam questions.

Some advice first

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. This also only focuses on practical questions from the 3 major topics in this course, but you may possibly also be asked practical questions for other topics too.

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. It's just a good habit to get used to.

For COMP1511 students

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 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 (notably, array problems and theory)

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.

Linked List Exercises

Easy

Intermediate

Challenges

Tree Exercises

Note that in some of these problems, the tree is not necessarily a search tree.

Easy

Intermediate

Challenges

Graph Exercises

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.

Easy

  • 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

Intermediate

Challenges

  • 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment