210CT Coursework: Algorithms & Data Structures

This coursework for the 210CT Programming, Algorithms and Data Structures course covers a range of topics across eight weeks. Each week presents several programming challenges focusing on fundamental data structures and algorithms. Students are tasked with writing functions to shuffle arrays, count trailing zeros in factorials, find perfect squares, perform matrix operations, reverse words in a sentence, check for prime numbers, remove vowels from strings, adapt binary search, extract ascending subsequences, implement binary search tree deletion, implement TREE_SORT, design and implement unweighted and weighted graphs, and implement graph traversals (BFS, DFS) and Dijkstra's algorithm. The assignments require both pseudocode and code implementation, along with analysis of runtime complexity using Big O notation. This comprehensive coursework provides a solid foundation in algorithm design and analysis.

Programming, Algorithms and Data Structure
Week 1
1. Write a function that randomly shuffles an array of integers and explain the rationale
behind its implementation.
2. Count the number of trailing 0s in a factorial number.
Week 2
3. Write the pseudocode for a function which returns the highest perfect square which
is less or equal to its parameter (a positive integer). Implement this in a
programming language of your choice.
4. Look back at last week's tasks. Describe the run-time bounds of these algorithms
using Big O notation.
5. Write the pseudocode corresponding to functions for addition, subtraction and
multiplication of two matrices, and then compute A=B*C –2*(B+C), where B and C
are two quadratic matrices of order n. What is the run-time?
Week 3
6. Write the pseudocode and code for a function that reverses the words in a sentence.
Input: "This is awesome" Output: "awesome is This". Give the Big O notation.
7. Write a recursive function (pseudocode and code) to check if a number n is prime
(hint: check whether n is divisible by any number below n).
8. Write a recursive function (pseudocode and code) that removes all vocals from a
given string s. Input: "beautiful" Output: "btfl".
Week 4
9. Adapt the binary search algorithm so that instead of outputting whether a specific
value was found, it outputs whether a value within a specific interval was found.
Week 5
10. Given a sequence of n integer numbers, extract the sub-sequence of maximum
length which is in ascending order.
11. Based on the Python code or the C++ code provided in class as a starting point,
implement the binary search tree node delete function.
Week 6
12. Implement TREE_SORT algorithm in a language of your choice, but make sure that
the INORDER function is implemented iteratively.
2016/2017 1 of 2

Week 7
13. Write the pseudocode for an unweighted graph data structure. You either use an
adjacency matrix or an adjacency list approach. Also, write a function to add a new
node and a function to add an edge. Following that, implement the graph you have
designed in the programming language of your choice. You may use your own
linked list from previous labs, the STL LL, or use a simple fixed size array (10
elements would be fine).
14. Implement BFS and DFS traversals for the above graph. Save the nodes traversed
in sequence to a text file.
Week 8
15. Implement Dijkstra’s algorithm for a weighted graph data structure (you have to
update your previous data structure so that it can deal with weights).
210CT Coursework 2016/2017 2 of 2