5117COMP Data Structures And Algorithms

This structure will be the best case because when searching for a number such as 7 we are going through three steps as shown in the diagram.

The worst case

In the worst case there will be six move as we search for the lowest number as shown in the diagram below.

1. The linear search algorithm is a less efficient algorithm as compare to the binary search tree. In this algorithm we sequentially go through the entire list and goes on until either a match is found or the end of the list is encountered. It has an average case of 0(N). Binary search tree is faster than the linear search since its average case is 0(log (N)).

The hash table has an average case of 0(1) in the case whereby one doesn’t know the size of the input items due to constant retrieve time. But if the items are continuously added it is better to use binary search tree’s 0(log (N)).

1. For a complete binary search tree to be complete, all the levels must be completely filled from left to right but not the last level.

The binary search tree created in (a) above is a complete tree since all the nodes have children except nodes at the lowest level.

Question 2

1. Operations of the Stack implementation.
2. Empty() - it checks whether the stack is empty or not. No input parameters are required in this operation and it returns a Boolean value that is true or false.
3. Push() - this operation adds a value at the topmost of the stack. Although this operation do not return anything parameters must be provided.

• Pop() – this operation removes an item from the topmost of the stack. It is different from push() operation in that it don’t require any parameters but it returns the item.

1. Constructor() – it creates a new stack if there is none. It has no parameters and returns an empty stack.
2. A stack is a Last in First out (LIFO) data structure. This is true because items can only be injected at one side of the stack and removed only at the opposite end.

First in First out data structure occurs when the first element in a queue is the first one to be removed while in Last in First out principle the last item in the stack is the first one to be removed.

1. The program below shows that there are three names to be stored in a stack using a linked list. We first create a linked list and then add the names to the stack. The names are then printed and thereby printing the size of the list. The program below is an example of the implementation as stated above.

Import java.util.Linkedlist;

  Public class printNames{

  Public static void main(String[] args){

 /*Creation of a linked list*/

LinkedList list = new LinkedList();

/*adding values*/

List.add(“Mary”);

List.add(“John”);

List.add(“Kelvin”);

/*Printing the list*/

System.out.println(“LinkedList: ” + list);

/*Printing the size*/

System.out.println(“List size: ” + list.size());

Question 3

1. The following piece of code shows how to use operations put(k,v) and get(k) in an array-backed implementation.

put(k,v) operations is used in Maps to insert a pair of element into  the map in a form of <key, value> while get(k) is used to return a value of the key that has been specified.

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

public class Fruits {

public static void main(String[] args) {

Map<String,String> hMap = new HashMap<String, String>();

List<Map<String , String>> Map  = new ArrayList<Map<String,String>>();

hMap.put("Yellow", "Banana");

hMap.put("Green", "Apple");

hMap.put("Orange", "Orange");

Map.add(0,Map1);

Map.add(1,Map1);

for (Map<String, String> map : Map) {

System.out.println(map.get("Yellow"));

System.out.println(map.get("Green"));

System.out.println(map.get("Orange"));

In the code above, the line hMap.put ("Yellow", "Banana"); has been used to input a key which is a string value, that is, the color of the fruit followed by string banana. The key is then used by the get () method to retrieve the value of that string and display it using a for loop.

The use of put(k,v) and get(k) operations has some drawbacks in that when there are more than one entry that has the same key then the two values will be displayed at the same time. This results to a collision.

Compression functions are used to combine fixed lengths input to arrive to a single fixed length output therefore shortening the amount of data to be kept in a hash table. The main objective of a compression is that it reduces the number of collision that may occur in a given set of hash codes.

Question 4

1. The data structure that would be likely to be used is a Hash map. A Hash map includes some basic operation such as put () and get (), the former is used to add entries while the latter is used to retrieving these entries. In our case the addresses are already store in an electronic database so what we are supposed to do is search the addresses by username and then displaying them in ascending order. We shall assign each address with a username by using keys to help in searching and then sort the list in an ascending order. An example of a code to do this can be:

package testhashes;

import java.util.HashMap;

import java.util.Map;

import java.util.TreeMap;

public class searchsort {

public static void main(String[] args) {

Map<String, String> address = new HashMap<>();

address.put("vinny", "102");

address.put("peter", "123");

address.put("john", "576");

address.put("clark", "475");

addresssearch(address);

private static void addresssearch(Map<String, String> mapaddress) {

System.out.println("Orignal HashMap:" + mapaddress);

System.out.println("n1. Sort address by ascending keys: " );

                 TreeMap<String,String>mapSorted = new TreeMap<>(mapaddress);

mapSorted.forEach((key, value) -> {

System.out.println(key + "'s address is: " + value);

This data structure has a time complexity of O(1) on average case and best case while its worst case is O(n). This makes it more efficient than other data structures.

From the problem above we can rewrite it in a post-fix for to become:

Here how the stack data structure solves the problem:

The first digit starts

References

Maurer, W.D. and Lewis, T.G., 1975. Hash table methods. ACM Computing Surveys (CSUR), 7(1), pp.5-19.

Rogaway, P. and Shrimpton, T., 2004, February. Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In International workshop on fast software encryption (pp. 371-388). Springer, Berlin, Heidelberg