COMP7506 – Algorithms and Data Structures

Algorithms and Data Structures was one of my last two subjects in my Graduate Diploma in Information Technology. It served as a broad look at the design and implementation of data structures and computer algorithms for the processing of large datasets. 

The course covered many topics both common in general purpose software development and more common only in high-performance computing (or choosing an existing implementation)

  • Abstract vs Concrete Data types in Java (interfaces and the impleting class)
  • Arrays vs Linked Lists – when to use one or the other and linked list implementation
  • Time and Space (memory/storage) Asymptotic Analysis:
    • Big O Notation + Big Theta Notation / Big Omega Notation
    • Describing an algorithm in psuedo-code for easier discussion.
  • Stacks (first in, last out) and Queues (first in, first out). Usage and implementation.
  • List ADT (like Java’s ArrayList)
  • Trees 
    • traversal orders (pre-, post-, in-order)
    • Binary Trees
    • Arithemetic Expression Trees
    • Implementation (linked or array-based)
  • Heaps and Priority Queue implementation
  • Maps, HashTables, Sets usage and implementation
    • Hashing, Compression of keys to a fixed size table
    • Linear probing, double hashing, separate chaining
  • Text Processing and Searching.
    • Boyer-Moore Heuristics
    • Knuth-Morris-Prat Algorithm
    • Tries (the tree-based data structure for storing text occurrences)
    • Huffman Encoding and pre-fix coding.
  • Graphs and graph traversal.
  • Sorting and Selection
    • Merge Sort, Bubble Sort, Insertion Sort, Quick Sort
    • Quick Select, Partition

Assignment 1

The first assignment’s backstory was a simulation of airspace in Australia. The actual task was to implement a Queue and a Cube data structure together with appropriate unit tests attaining 80% code coverage for the most marks in this area.

Assignment 2

The second assignment was about text processing. We were given a large volume of text and needed to implement various search functions, some were:

  • Word occurence count
  • Phrase search
  • Prefix search
  • word  search

Trie Class (for storing word occurrences)

Trie Node

As well as the actual search method implementation we had to write a readme justifying our decisions and choices in algorithms; and the post-graduate students (which I was) needed to write a research essay on optimising the loading time of the text and data structures by saving it to disk.

report_redacted

Overall thoughts

During the assignments, particularly the second one, I discovered that I work well by breaking up a large task into smaller parts that I can complete. I found if I break it up before I start much actual development and write the sub-tasks down, I can more easily focus on each task.

This course was rather hard, though probably not the hardest course I’ve done during this degree. (The hardest course I did was CSSE7023 – Advanced Software Engineering.) To be honest (and I think it’s good to be) I actually wanted to drop this course because I didn’t see the relevance, nor did I enjoy it in the slightest. For several reasons, I ended up staying in the course and I also ended up passing it! I still don’t actually see the relevance of all the different types of tree data structures, but I am glad I did the course and learnt the concepts. Also, doing the assignments with their abstract data types, concrete data types, and search functionality implementation did give me more practical experience in object-oriented programming which helped in my work as a junior software developer at Canopy Tools.

I would however recommend the book A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow. It is quite accessible and frankly explained the concepts better and with less words than the prescribed textbook.

Taken from https://pragprog.com/book/jwdsal/a-common-sense-guide-to-data-structures-and-algorithms. Retrieved on 3rd January 2019