In preparation for applying to OMSCS, I took the recommended MOOC on Data Structures & Algorithms offered by Georgia Tech.

Overall

To prepare for the application to Georgia Tech’s OMSCS program, I completed 2 of the 3 recommended MOOCs. The following summarizes the courses related to Java.

edX Introduction to Object-Oriented Programming with Java

This course was about data structures and algorithms, fundamental concepts in Computer Science and commonly encountered in software engineering tech interviews. The language used in the lectures was Java, and all implementation assignments for data structures and algorithms were submitted in Java.

Data Structures & Algorithms

Content

The course consists of 4 Parts, requiring about 9-10 hours per week for approximately 5 months. Each part is divided into around 3 Modules, structured to teach data structures and algorithms. Assessment is determined through quizzes, assignments, and tests, with a certificate issued for scores of 60% or higher. The following site visualizes the data structures and algorithms covered in this course, which was helpful for grasping the functioning of these concepts.

CS 1332 Data Structures and Algorithms Visualization Tool

Data Structures

Up until Part 3, the course content focused on data structures, classified as follows. Diagrams corresponding to each data structure were provided using the above Visualization Tool.

from edX Data Structures & Algorithms

Part 1: ArrayLists, LinkedLists, Stacks and Queues

In Part 1, I learned about the fundamental data structures: ArrayList, LinkedList, Stack, and Queue.

• ArrayList
  A resizable array that automatically increases its size as elements are added. It offers fast access to specific elements but may have slower addition speeds. This data structure excels at random access of elements within the array.

• LinkedList
  A structure where each element contains information pointing to the next element. It’s easy to add data to the end, but movement is only possible in one direction.

• Stack
  A data structure similar to documents stacked on a desk, where the last added data is the first to be removed (FILO - First-In, Last-Out). The implementation of Stack was discussed in terms of both array-backed and linked-backed. The following diagram represents a Linked Stack.

• Queue
  A structure akin to a waiting line, where the first data added is the first to be removed (FIFO - First-In, First-Out). Queue was also addressed in both array-backed and linked-backed contexts. The following represents a Linked Queue.

Part 2: Binary Trees, Heaps, SkipLists and HashMaps

Part 2 dealt with Binary Search Trees, Heaps, SkipLists, and HashMaps.

• Binary Search Tree
  A data structure composed of nodes and edges where each node can have a maximum of two child nodes.

• Heap
  Data is organized according to priority, implemented either as a Min heap (where parent node values are less than child node values) or Max heap (where parent node values are greater). This structure is utilized as a Priority Queue and can be implemented using an array, wherein the parent node’s index is i/2 of its child nodes’ indices.

• SkipList
  A data structure that enhances the search speed of a LinkedList by consisting of multiple levels of nodes. Higher-level nodes can skip several lower-level nodes, thus enabling faster searches.

• HashMap
  A structure that holds pairs of keys and values, converting keys into hash values via a hash function and using them as indices in an array.

Part 3: AVL and 2-4 Trees, Divide and Conquer Algorithms

Part 3 covered AVL trees, 2-4 Trees, and algorithms including Iterative Sorts and Divide & Conquer Sorts.

• AVL
  An AVL tree is a Binary Search Tree (BST) that maintains balance; the height difference between any node’s left and right subtrees is at most one. While a BST can become unbalanced, leading to O(n) searching time, AVL trees ensure O(log n) time even in the worst case by rebalancing during node additions and deletions through a process known as Rotation.

• 2-4 Tree
  Each node can have between 2 to 4 child nodes, and during node additions and deletions, nodes are repositioned to adhere to range conditions.

Algorithms

The algorithms covered in this course can be classified as follows. A summary of the various methods is outlined below.

Additionally, here are videos that visualize each sorting method shared as references.

15 Sorting Algorithms in 6 Minutes

Part 3: Iterative Sorts, Divide & Conquer Sorts

Part 3 addressed Iterative Sorts and Divide & Conquer Sorts. Iterative Sorts consist of algorithms such as Bubble Sort, which sorts through repetition. Divide & Conquer Sorts involve splitting larger problems into smaller ones, solving each individually, and then merging the results.

Iterative Sorts:

• Bubble Sort: Compares adjacent elements and swaps them if necessary to sort the list.
• Insertion Sort: Inserts each element of the unsorted section into its correct position.
• Selection Sort: Selects the smallest element from the unsorted section and places it in order.
• Cocktail Shaker Sort: An enhanced version of Bubble Sort that alternately scans left and right, comparing and swapping adjacent elements.

Divide & Conquer Sorts:

• Merge Sort: Divides a large sequence into smaller sequences, sorts each, and merges them back together.
• Quick Sort: Chooses a pivot to split the sequence around and sorts based on that pivot.

Part 4: Pattern Matching, Dijkstra’s, MST, and Dynamic Programming Algorithms

Part 4 focused on Pattern Matching in text, Graph Algorithms, Minimum Spanning Trees (MST), and Dynamic Programming.

Pattern Matching:

• Boyer-Moore (BM): Features backward comparison of the search string, aligning the last character of the text and search string, and remembering positions upon mismatches.
• Knuth-Morris-Pratt (KMP): Sequentially compares characters, while memorizing matches to skip unnecessary comparisons.
• Rabin-Karp (RK): Utilizes hash functions to compute hash values for parts of the search string and text, performing actual comparisons only when hashes match.

Graph Algorithms:

• Breadth-First Search: Prioritizes adjacent vertices starting from the initial vertex, managing the next visit using a Queue.
• Depth-First Search: Prioritizes vertices further from the starting point, managing the next to visit with a Stack.
• Dijkstra’s Algorithm: Solves single-source shortest path problems under non-negative edge weights using a Priority Queue to select the lowest weight vertex.

Minimum Spanning Trees (MST):

• Prim’s Algorithm: Finds the Minimum Spanning Tree (MST) with minimal edge weight sum by starting from one vertex and iteratively selecting the lowest-weight edge using a Priority Queue, suitable for dense graphs.
• Kruskal’s Algorithm: Also seeks the MST by checking edges in order of increasing weight, making it better suited for sparse graphs.

Dynamic Programming:

• Longest Common Subsequence (LCS): Resolves the longest common subsequence between two strings by building a table and comparing characters.
• Bellman-Ford: Determines the shortest paths from a single source vertex to all others, functioning even with negative edge weights by relaxing edges iteratively.
• Floyd-Warshall: Computes the shortest paths between all pairs of vertices.

Reflection

This course was quite enriching, allowing me to learn numerous data structures and algorithms. The tools provided were excellent, aiding visualization and understanding of the concepts. Through some exercises, I was able to implement certain ideas, deepening my comprehension. Some problems on LeetCode utilized techniques from what I learned in this course. I found hints for implementation during the lectures, and I aim to master these skills so I can apply them fluidly in the future.