I've received more questions than I will have time to answer during Friday's lecture. This is great. In order to maximise answers and lecture time, I've separated the questions into 3 main categories:
* **Quick answers:** Questions I can answer quickly and easily in writing in this document so don't need to spend lecture time on them (unless there are follow-up questions).
* **To address in the lecture:** These questions I'll prioritise answering during the lecture on Friday 4th August.
* **Provide resources:** These are often bigger or more vague questions. Or questions I feel have already been answered during the course. For these questions I'll provide links to where it's been covered already in our lectures and/or some external resources to help you find your answers. Any follow-up questions on this material are welcome!

Please note that this document is a work-in-progress. For example, I haven't actually put the resources in the "provide resources" section at the time of sharing this document with students. I will continue to fill it out over the course of Thursday evening and maybe Friday morning too. I will also check back at the questions being submitted and add them to this list.

To submit questions, fill out the form provided [here](https://forms.gle/HLcb1VWUGYkHWYxV7).

# Please clarify your question(s)

Q: Allocating memory to arrays when you dont known they exact size. When to use calloc/malloc/realloc, double pointers vs single pointer for arrays.

A: Do you mean, "If I need an array and I don't know how big it might be, how do I create the array initially, and update it as needed (using calloc/malloc/realloc etc)?" ?

# Quick answers provided here

**Q: Kruskal's or Prim's algorithm, what cases should one be used over another for creating a minimal spanning tree?**

A: We didn't go into the complexity of either algorithm much if at all, but to answer your question, the time complexity of Prim's algorithm is O(V^2) and the time complexity of Kruskal's algorithm is O(E log V). So for a sparse graph (lots of vertices but few edges), Kruskal's is faster, but if you have a much more dense graph, then Prim's is quicker.

**Q: MergeSort is an example of a quicker algorithm, but it was stated that it uses more memory. What are examples of where this would be a large issue stopping us from using it?**

A: The answer to this question depends on how much data we have to sort and how much memory we have at our disposal. Basically, if we have a normal laptop worth of memory then we would step away from mergesort much sooner (with a much smaller data set) than if we have a rack of machines worth of memory to work with. You might find yourself choosing between upgrading your RAM and choosing a differnet sort to use.

**Q: How to answer short answer questions. And how in detail we need to be. Go through a lot of examples of possible exam questions.**

A: Two parts to this answer:
* Understand (and respond to) what the question is asking. (https://www.matrix.edu.au/how-to-respond-to-nesa-key-words-to-ace-your-hsc/)
* Starting with what you think is most relevant, brain-dump everything you know on the topic. If you do this, starting with the most relevant is the most important thing because the marker may stop reading if it seems like you're rambling. If they find most of the correct information early on, then they may search through the rest of your answer for the last bit. And make sure not to contradict yourself.
* Look at how many marks are being awarded for the answer. Try and think about how you would mark the question and what those marks would corresspond to.

**Q: I would like to know the difficulty and possible exam questions for programming questions. I want to know what sort of difficulty is expected**

A: Please look at the [Sample Exam](https://cgi.cse.unsw.edu.au/~cs2521/23T2/sample-exam) provided.

**Q: If I need an array and I don't know how big it might be, how do I create the array initially, and update it as needed (using calloc/malloc/realloc etc)?**

A: The realloc() function gives a handy way to grow or shrink an array:

If oldp is the result of an earlier call to malloc() such as `old = malloc(oldsize);` then `newp = realloc(oldp, newsize);` does the following:
1. Allocates newsize bytes of memory,
2. Copies the contents of *oldp to it (up to the lesser of oldsize and newsize)
3. Frees oldp.
4. Returns the address of the newly allocated memory

Source (has a lot more detail and implementation examples you might find useful): https://newton.ex.ac.uk/teaching/resources/jmr/appendix-growable.html

# To address in the lecture

* Dijkstra
* Quicksort: 1,4,6,7

~~1. Median of three Quicksort. Specifically, in the lecture it was said that it has a worst case of O(N^2) but I struggled to figure it out. I also found online resources stating it's worst case was O(N*log(N)). Can we get a better example~~
2. Ways to memorise the AVL, MST and Dijkstra algorithms 😵‍💫
3. How to answer short answer questions. And how in detail we need to be. Go through a lot of examples of possible exam questions. (some answer above)
~~4. Quick sort - how the partitioning works~~
5. Will we be expected to code tries/compressed tries? If so, could we walk through the code/pseudocode in the lecture?
6. Understanding more about time complexity and how to find the time complexity. I was having trouble with last weeks lab maybe that’s a good starting point?
7. Code to identify minimum/maximum comparisons for different sorting algorithms.
8. Identifying maximum number of edges, vertices visited for DFS, BFS etc.
9. Perhaps some simple proofs (if possible) of the MST algorithms?
10. AVL Rebalancing
11. Tree rotation (visually)
12. Recursion functions - I’m very bad at recursion, I can’t seem to understand the logic. Please help me understand the logic of the recursion functions.
13. C Implementation of Kruskal's Algorithm
14. C Implementation of Prim's Algorithm
15. "How I Study" -> Sim's approach to studying for comp

# Provide resources

**Q: What is an adjacency matrix, how to implement it
Q: What is an adjacency list, how to implement it**

A: The above two questions have answers in the *Graph Implementation* lecture in Week 4 Friday.
[YouTube Link](https://youtube.com/live/Li7tBZhUcNI?feature=share)
[Lecture slides for graph implementations](http://www.cse.unsw.edu.au/~cs2521/23T2/lectures/comp2521-21t2-5-2-graph-implementations.pdf)
Implementations can be found in the [lecture code](http://www.cse.unsw.edu.au/~cs2521/23T2/live/) under wk5-2-graph-imp/exercises.

**Q: C Implementation of Weighted and Directed Graphs**

A: This can be found in the [lecture slides for weighted and directed graphs](https://slides.com/simmautner/comp2521-21t2-7-2-weighted-directed-graphs). These include only slight changes to the lecture code from the Graph Implementation topic (all code on the slides can be copied, and all the changes are highlighted for your convenience).

**Q: Avl or bst tree implantation code.**

A: BST implementation can be found in the [lecture code](http://www.cse.unsw.edu.au/~cs2521/23T2/live/) under wk3-bst.
AVL implementation can be found partially in the [lecture code](http://www.cse.unsw.edu.au/~cs2521/23T2/live/) under wk3-balancing. Any incomplete code can be found in the [lecture slides for AVL trees](https://slides.com/simmautner/comp2521-21t2-4-2-avl-trees).

# Uncategorised