COSC2123

In this course, I was focusing on analysing various types of data structures and the performance of each type with Time Complexity in Average - Best - Worst cases in looking-up data, merging - comparing - sorting data sets, inserting - removing - copying data, and a lot of other algorithms to refine and produce data for some specific purposes basing on the requirements of the real problem. Some of the main data structures that I was taught and self-researching during the time of this course include:

• Composite types: Array, Record, Struct, Enum, Union.
• Abstract types: List, ArrayList, Map, Multimap, Set, Bag, Stack, Queue (normal, priority), Deque, LinkedList (singly, doubly, circular).
  • Arrays: Matrix, Associative Array, Parallel Array, Sorted Array, Vector, Lookup Tables.
  • Trees: Binary Tree, Binary Search Tree, Cartesian Tree, AVL Tree, Red-Black Tree, 2-3 Tree, Left-Child Right-Sibling Binary Tree, Random Binary Search Tree, Weighted Balanced Tree, K-d Tree (Min-Max, Relaxed, Adaptive), Forests.
  • Graphs: Adjacency List - Matrix, Directed Graph, Directed Acyclic Graph, Multigraph.

Some of the algorithms that was covered by this course:

• Levenshtein Edit Distance, Convex-Hull algorithm (also Quickhull), Laplacian, Collision detection, Pseudorandom number generator.
• Sorting: Topological Sort, Selection Sort (also Heap Sort), Bubble Sort, Odd-even Sort, Quick Sort, Merge Sort, Insertion Sort, Shell Sort, Spaghetti Sort, Bucket Sort, Postman Sort, Radix Sort.
• Searching: Linear Search, Binary Search, Fibonacci, Quick Selection.
• Graph: Algorithms for routing: Ford-Fulkerson, Euclidean, Kruskal, Prism, Bellman-Ford, Dijkstra, Floyd-Warshall, Johnson. Algorithms for searching: Depth First Search, Breath First Search, Brute Force, Lex-BFS, Dijkstra, Backtracker, Prufer coding.

Assignment 1 was about applying some basic algorithms in insertion, deletion and lookup of data in custom data structures comprising Sorted LinkedList, Balanced Tree, HashMap, LinkedList (singly or doubly), and Binary Search Tree. The input data will be growing in density from low to very high. Then I needed to evaluate the Time Complexity for each data structure, and compare the performance of each type to tell which one of them would be best suited in what situations of data inputs.

Assignment 2 required students to implement a maze generator program using Recursive Backtracker, Growing Tree and Prism algorithms. The types of maze were Rectangular Maze, Hexagonal Maze and Tunnel Maze. All mazes must be perfect. Then students must complete the algorithms to solve the generated mazes using Wall Follower and Bidirectional Recursive Backtracker algorithms.