Lab Assignments for Coursera Online Course "Algorithms"

Lectures given by Prof. Robert Sedgewick and Prof. Kevin Wayne (Princeton University)

Assignment 1

• Use data type Union-Find implemented by two different algorithms to model a percolation system.
• Adopt the Monte Carlo simulation to estimate this percolation system's threshold.
• Empirically analyze the runtime of 2 algorithms that underpinning the data type Union-Find, i.e., quick find and weighted quick union algorithm.
• Details: https://coursera.cs.princeton.edu/algs4/assignments/percolation/specification.php

Assignment 2

• Implement generic and iterable data structures "Deque" and "Randomized Queue" using linked list and resizing array.
• Details: https://coursera.cs.princeton.edu/algs4/assignments/queues/specification.php

Assignment 3

• Build a "Point" data structure that implements Comparable<> interface and with method returns object-dependent comparator<>.
• Based on Java's sort() method implement an approach to detect colinear points (line segaments) in a given set of points, i.e., Point data type objects, for computer vision application.
• Details: https://coursera.cs.princeton.edu/algs4/assignments/collinear/specification.php

Assignment4

• Create a "Board" data-type that models n-by-n puzzles with sliding tiles.
• Use binary heap based "Priority Queue" data-type to implement A* algorithm for solving the n-by-n puzzles (Board states ast as nodes to form a tree-like data structure with one state as the goal).
• Details: https://coursera.cs.princeton.edu/algs4/assignments/8puzzle/faq.php

Assignment5:

• Implement a Kd-Tree (2D-Binary Search Tree) for 2D points storaging, range searching and nearest-neighbor searching, then compare its correctness with the brute force approach.
• Analyze memory usage and runtime of Kd-Tree and Brute-Force method by using theoretical model and empirical method.
• Details: https://coursera.cs.princeton.edu/algs4/assignments/kdtree/specification.php

Assignment6:

• Build the linguistic wordnet (a lexical database) by parsing the words in the wordnet and store their semantic relations, including synonyms and hyponyms, into a directed acyclic graph (DAG) data structure.
• Use breadth-first search (BFS) to realize the wordnet methods that find the shortest distance between any two words in the wordnet and the ancestor word that connects them.
• Details: https://coursera.cs.princeton.edu/algs4/assignments/wordnet/specification.php