Skip to content

Java Implemented Portfolio covering data structures and algorithms including binary trees, red black trees, heap sorting, sorting algorithms, graphs, breath first and depth first search, prim's algorithm, concurrent applications

Notifications You must be signed in to change notification settings

mariamabdelati/Advanced_Algorithms_CourseWork

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

3 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Advanced Algorithms CourseWork

Java Implemented Portfolio -- University Junior Year

Mariam Abdelati

Table of Contents


Task One

Write a recursive method that given a binary tree, creates a new tree where every node is duplicated. Every duplicated node has to be inserted as a left child of the node.
Hint: The left child that was inserted should not be duplicated again or else your algorithm will run forever.
For example, for the following tree:

Binary Tree Unduplicated



should return the following tree

Duplicated Binary Tree


Task Two

Implement a red-black tree from scratch. Implementing all the basic operations of a red-black tree. Test your program by displaying the RB tree, after performing each of those operations:
  a. create a tree   b. insert the following to the tree [30, 15, 45, 35, 60, 55] and show the resulting tree after each operation.   c. delete 45 from the tree and show the resulting tree.


Task Three

Implement the heapsort algorithm from scratch. Your program should receive a list (or array from the user) and output a sorted list. Test you program against the following set of elements [90,87,65,11,23,45,21]


Task Five

Implement both the adjacency matrix and adjacency list representations of a graph, use the graph below as a testing example for your main program:

Graph


Task Six

Implement both the Breadth first search traversal and the Depth first search traversal of a graph, use the graph from the task above to test your main program.


Task Seven

Implement a Prim’s algorithm variation, where we need to find the spanning tree based on the largest distance not the smallest. Use the following graph as an example for testing your program, show the output of the program as a list of nodes representing the spanning tree. In addition, you should justify the usage of any other ADT for storing and processing inputs or outputs.

Prim's Algorithm


Task Eight

Search for sorting algorithms which could be implemented as a concurrent algorithm. Justify your findings. Then implement Merge sort algorithm as a concurrent application


Back to Top

About

Java Implemented Portfolio covering data structures and algorithms including binary trees, red black trees, heap sorting, sorting algorithms, graphs, breath first and depth first search, prim's algorithm, concurrent applications

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages