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