1. Homepage
2. Programming
3. Algorithm Design and Analysis - Assignment Three: Persistent dynamic set

# Algorithm Design and Analysis - Assignment Three: Persistent dynamic set

Algorithm Design and AnalysisPersistent dynamic setJava

# Algorithm Design and Analysis - Assignment Three

Due 16 December 2022

A persistent dynamic set is a set which maintains past versions of itself as it gets updated. One simple implementation of a persistent dynamic set would be to copy the entire data structure whenever it gets modified, but this approach becomes Θ(n) and may require substantial memory, so instead the data structure just keeps track of changes made.

The purpose of this assignment is to develop an eﬀicient data structure for a persistent dynamic set of Comparable elements.

The assignment should include the following components, each with some suitable test examples:

Binary Search Tree which is a binary search tree with add, contains, and remove methods. Each node contains a Comparable element, and links to its left and right children (or null if it doesn’t have a child). Note that each node will NOT have a link to its parent (to simplify effort later in the assignment). It is suggested that the binary search tree class be arranged to be extensible, and hook methods included that get called whenever a node is visited during add or remove. Please include a suitable way to visualise the tree. (10 marks) Persistent Dynamic Set which is an implementation of a persistent dynamic set for Comparable elements which utilises the binary search tree. When an element is added or removed only the nodes that are affected from the root down to that element are copied and links made to unaffected nodes from the previous version of the binary search tree. For example if “dog” is added to the tree on the left a second tree with four new (green) nodes is created on the right, including a new (green) root node to represent the updated version.

Please include some suitable way to visualise the different version of the tree. (20 marks) Balanced Persistent Dynamic Set which is a red-black tree subclass of the binary search tree that keeps the tree balanced so the persistent dynamic set is guaranteed to have O (log n) operations. It should utilise the tree’s hook methods to avoid traversing the tree multiple times during rebalancing, and care should be used during left and right rotations to correctly update the version. The eight cases to be considered in the remove method will be limited to a maximum three marks. (15 marks)

Demonstration of the programs with a 3-5 minute video.

## Get Expert Help On This Assignment

#### Scan above qrcode with Wechat

Algorithm Design and Analysis代写,Persistent dynamic set代写,Java代写,Algorithm Design and Analysis代编,Persistent dynamic set代编,Java代编,Algorithm Design and Analysis代考,Persistent dynamic set代考,Java代考,Algorithm Design and Analysishelp,Persistent dynamic sethelp,Javahelp,Algorithm Design and Analysis作业代写,Persistent dynamic set作业代写,Java作业代写,Algorithm Design and Analysis编程代写,Persistent dynamic set编程代写,Java编程代写,Algorithm Design and Analysisprogramming help,Persistent dynamic setprogramming help,Javaprogramming help,Algorithm Design and Analysisassignment help,Persistent dynamic setassignment help,Javaassignment help,Algorithm Design and Analysissolution,Persistent dynamic setsolution,Javasolution,