About this Course
This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.
All the features of this course are available for free. People who are interested in digging deeper into the content may wish to obtain the textbook Algorithms, Fourth Edition (upon which the course is based) or visit the website algs4.cs.princeton.edu for a wealth of additional material.
Compilation: PASSED API: PASSEDPercolation. Given a composite systems comprised of randomly distributed insulating and metallic materials: what fraction of the materials need to be metallic so that the composite system is an electrical conductor? Given a porous landscape with water on the surface (or oil below), under what conditions will the water be able to drain through to the bottom (or the oil to gush through to the surface)? Scientists have defined an abstract process known as percolation to model such situations. The model. We model a percolation system using an n-by-n grid of sites. Each site is either open or blocked. A full site is an open site that can be connected to an open site in the top row via a chain of neighboring (left, right, up, down) open sites. We say the system percolates if there is a full site in the bottom row. In other words, a system percolates if we fill all open sites connected to the top row and that process fills some open site on the bottom row. (For the insulating/metallic materials example, the open sites correspond to metallic materials, so that a system that percolates has a metallic path from top to bottom, with full sites conducting. For the porous substance example, the open sites correspond to empty space through which water might flow, so that a system that percolates lets water fill open sites, flowing from top to bottom.)SpotBugs: PASSED PMD: PASSED Checkstyle: FAILED (0 errors, 17 warnings)
Correctness: 38/38 tests passed Memory: 9/8 tests passed Timing: 20/20 tests passed
Aggregate score: 101.25% [ Compilation: 5%, API: 5%, Style: 0%, Correctness: 60%, Timing: 10%, Memory: 20% ]
==============================================================================================================
Compilation: PASSED (0 errors, 4 warnings) API: PASSEDSpotBugs: FAILED (1 warning) PMD: PASSED Checkstyle: FAILED (0 errors, 24 warnings)
Correctness: 49/49 tests passed Memory: 134/133 tests passed Timing: 193/193 tests passed
Aggregate score: 100.08% [ Compilation: 5%, API: 5%, Style: 0%, Correctness: 60%, Timing: 10%, Memory: 20% ]
Write a generic data type for a deque and a randomized queue. The goal of this assignment is to implement elementary data structures using arrays and linked lists, and to introduce you to generics and iterators.
Dequeue. A double-ended queue or deque (pronounced “deck”) is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure.
Randomized queue. A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random among items in the data structure.
==============================================================================================================
Compilation: PASSED API: PASSEDSpotBugs: FAILED (3 warnings) PMD: PASSED Checkstyle: FAILED (0 errors, 43 warnings)
Correctness: 41/41 tests passed Memory: 1/1 tests passed Timing: 41/41 tests passed
Aggregate score: 100.00% [ Compilation: 5%, API: 5%, Style: 0%, Correctness: 60%, Timing: 10%, Memory: 20% ]
The problem. Given a set of n distinct points in the plane, find every (maximal) line segment that connects a subset of 4 or more of the points.
Brute force. Write a program BruteCollinearPoints.java that examines 4 points at a time and checks whether they all lie on the same line segment, returning all such line segments. The order of growth of the running time of the program will be n4 in the worst case and it will use space proportional to n plus the number of line segments returned.
A faster, sorting-based solution. Remarkably, it is possible to solve the problem much faster than the brute-force solution described above. The growth of the running time of the program will be n2 log n in the worst case and it will use space proportional to n plus the number of line segments returned.==============================================================================================================
Compilation: PASSED API: PASSED
SpotBugs: PASSED PMD: PASSED Checkstyle: FAILED (0 errors, 95 warnings)
Correctness: 52/52 tests passed Memory: 22/22 tests passed Timing: 125/125 tests passed
Aggregate score: 100.00% [ Compilation: 5%, API: 5%, Style: 0%, Correctness: 60%, Timing: 10%, Memory: 20% ]
Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.
The problem. The 8-puzzle is a sliding puzzle that is played on a 3-by-3 grid with 8 square tiles labeled 1 through 8, plus a blank square. The goal is to rearrange the tiles so that they are in row-major order, using as few moves as possible. You are permitted to slide tiles either horizontally or vertically into the blank square. The following diagram shows a sequence of moves from an initial board (left) to the goal board (right).
