ISCG6426 - Data Structures & Algorithms  - Assignment   1 - Solved

1.    Apply object-oriented design and implementation techniques.  

2.    Interpret the trade-offs and issues involved in the design, implementation, and application of various data structures with respect to a given problem.  

3.    Explain the purpose and answer questions about data structures and design patterns that illustrate strengths and weaknesses with respect to resource consumption.  

4.    Assess the impact of data structures on algorithms.  

5.    Analyse the scalability of data structures and algorithms in terms of both space and time complexity.  

  

•      Select a data structure or algorithm from the Appendix. Implement and create an interactive game or visualization which uses it in an educational manner. Once you’ve selected one.




  

  Task 1: Implement a data structure / algorithm                             [17 Marks]  
  

Select a data structure or algorithm from the appendix and get the lecturer’s approval to work on it. Ask your lecturer for functionality you will be required to implement.  

  

Correctly implement the chosen data structure. The implementation must use randomly generated data.  

  

  

  Task 2: Code an interactive visualization                                         [15 Marks]  
  

Choose an algorithm or data structure from the appendix and get the lecturer’s approval to work on it.  

Using the SFML.NET library (NuGet package or https://www.sfmldev.org/download/sfml.net/ ) or another approved library/framework, create an interactive game or visualization demonstrating how the chosen data structure or algorithm works.  

  

Work closely with your lecturer during this phase to ensure that your implementation is accurate. Failing to do so may result in loss of marks.  

  

Your implementation is required to accurately represent the chosen data structure/algorithm in an educational manner.  

  

It should support both keypresses and mouse input. It must implement a draw() and update() method in the visualization.  

  

  

  Task 3: Analysis & Commentary                                                           [8 Marks]  
  

Create a file named README.md in your project directory. In this file, write the following:  

  

-       A paragraph documenting issues you encountered in the design or implementation of your chosen data structure/algorithm.  

  

-       Briefly explain the strengths and weaknesses of your data structure or algorithm with respect to resource consumption. Under what conditions does it perform the best or worst?  

  

-       List a real-world application of your chosen data structure or algorithm.  

  

-       A sentence or two on the asymptotic worst-case time and space complexity of your chosen data structure/algorithm.   



  

  

Appendix 1  

  

Choose one of the following to implement for your assignment.  

Contact your lecturer for approval. As this is an open-source assignment, each student needs to work on something different.  

  

1.    Double-Ended Queue (deque)  

2.    Priority Queue  

3.    Sorting  

a.    BubbleSort  

b.    Insertion Sort  

c.    Selection Sort  

d.    QuickSort  

e.    MergeSort  

f.     HeapSort  

4.    Linked-List  

a.    Singly  

b.    Doubly  

c.    Circular  

5.    Searching  

a.    Binary search  

b.    Depth-first-search {Pre, In, Post}-order  

c.    Breadth-first search  

6.    Trees   

a.    Binary search tree  

b.    AVL Tree  

c.    Red-Black Tree  

d.    B-tree  

e.    Merkle-tree  

f.     Trie  

g.    Quadtree  

7.    Heap  

a.    Min  

b.    Max  

c.    Fibonacci  

d.    Binary  

8.    Hashing  

a.    Chaining  

b.    Open addressing  

c.    SHA256  

9.    Graph shortest-path  

a.    Dijkstra’s  

b.    Bellman-Ford  

c.    A* search  

d.    Floyd-Warshall  

10.  Network maximum flow  

a.    Ford-Fulkerson  

b.    Edmonds-Karp  

11.  Graph cycle detection (Floyd’s)  

12.  Directed Acyclic Graph (DAG)  

13.  Traveling Salesman Problem (TSP)  

14.  Minimum spanning tree (Boruvka’s, Prim’s, Kruskal’s)