SC1007 DATA STRUCTURES & ALGORITHMS (3.0 AU)

Write a c function interleaveQueue()that rearranges the elements by interleaving the first half of the queue with the second half of the queue using one temporary stack for a given queue of integers of even length. Note that the interleaveQueue() function only uses push() and pop() when adding or removing integers from the stack and only uses enqueue() and dequeue() when adding or removing integers from the queue. [Please note that you must use only one temporary stack inside your function.]

The function prototypes are given as follows:

void interleaveQueue(Queue q)

Some test sample cases:
If the queue is (1, 2, 3, 4, 5, 6), the resulting queue will be (1, 4, 2, 5, 3, 6)
if the queue is (1, 2, 3, 4), the resulting queue will be (1, 3, 2, 4)

Took this module in 21/22 Sem 2.

Components: 8 x 5% take-home assignments, 2 x 20% programming tests, 20% MCQ

First half was taught by Dr Loke YR. No pre-recorded lectures, all done live on his Youtube channel. Content covered were: time and space complexity, linked lists, stacks/queues, trees + binary search trees, self balancing tree (AVL) and Huffman. Explanation can be a little hard to get sometimes.

Second half was taught by Dr Anh Tuan. Live lectures as well, no pre-recorded. Content covered were: hashing, graphs, BFS/DFS, backtracking, DP. Incredibly thick accent, although it was managable for me.

Weekly Labs: Weekly problem sets to be done in the labs. Not graded though, merely for practice.

Take-home assignments: Dr Loke sets significantly harder assignment questions than Dr Anh, around leetcode med/hard for most questions. For Dr Anh, assignment questions are similar to lab ones, with 1 other question being harder. Don’t be afraid to seek help from your batchmates/friends if you’re struggling with the problem sets. Many people are struggling as well, helping each other goes a long way. 🙂 Do try to score the full 40% for the assignments as it is a free significant chunk of the module. Although, Dr Loke says that some people find his assignment so difficult that they submitted nothing at all. 🙁

Programming tests: 2hr for both tests. 4 questions for 1st half, 3 questions + the MCQ for 2nd half. As usual, Dr Loke’s questions are significantly harder. Some personal exam tips are: partition your time wisely. Spend strictly 30min for each question, and move on after 30min if you cannot finish. Chances are, subsequent questions can be easier and you can finish in <30min, then you can go back and attempt the harder questions. Do use the draft paper provided to write out your pseudocode/logic before typing a single line of code. Lastly, if you're truly unable to solve the questions, try to code out some simple base cases instead of giving up. There could be some base cases in the test cases, which can give you some partial credit.

My test questions for reference:
First half:
-Removing current node if prev value + next value = current value in a doubly linked list.
-Zipping up two linked lists
-Finding minimum path in a binary tree
-Printing out the nodes of a ternary tree in a specific order, left to right then right to left and so on (Very difficult)

First half:
-DP problem for a given equation, similar to Fibonacci
-Output the total number of solutions for graph coloring problem given a certain starting color
-Output the total number of subgraphs for a given graph using BFS

MCQ: 10 questions, theory based. Important to know your Big-O notation, time comp of various algorithms like BFS/DFS, simple hashing functions, DP concepts.

Overall: Make sure your C fundamentals are solid, especially for pointers. Make use of resources like leetcode, youtube, g4g.

Assessment components:
8 hackerearth assignments – 40% (8×5%)
2 lab tests – 40%
final quiz – 20%

Programming language used: C prog

Lecturers: Dr Loke (first half) and Prof Luu Anh Tuan (sec half)

Weekly Hours: 2x1hr online lecture, 1x2hr lab, 1x1hr tutorial

Topics covered:
– Linked List
– Stack & Queue
– Trees
– AVL, Huffman
– Time complexity
– Hash Table
– BFS, DFS
– Backtracking
– DP
– Bipartite Graph

First half:
Covered by Dr Loke via his youtube live stream. The assignments set by Dr Loke were very difficult and took up a lot of time to solve given that it was only 5% worth. Lab test for his half can be prepared by practising leetcode. Heard many people struggle to even finish assignments and end up not finishing. Lab test was also quite hard — considerably lesser number of people left lab before end of session (<5 for mine).

Sec half:
Covered by Prof Anh Tuan. His lab test and assignments were much easier compared to Dr Loke, though he is not as good as Dr Loke at explaining and kind of hard to get his accent sometimes. Assignments were closely related with lab practice questions so not much effort were required as 80% can be copied-pasted and add a few more lines. Lab test was also related and much easier than 1st half — about half the lab left before end of exam.

Expected grade:
assignments (~38/40%)
lab test 1 (11.5/20%)
lab test 2 (14/20%)
quiz grade unknown
expecting B+ or if bell curve god helps, A-