Calendar May 4, 2016 23:11

Blogger Blogger

Max & Min Heap

So now that class is over and I took my final for my CS2420 class last night, I find that I have come to love programming and I miss not having an assignment to work on. So today I decided that since I had already created a Max Heap class, that I should also create a Min Heap class.

While I was working, I found that 99% of the code was going to be the same, and I didn't want to just create a copy and tweak a few lines. So instead I decided to create a abstract Heap class that I could inherit from.

So I created the base class and moved most of the code to that file. Then I made the Max and Min Heap classes and made the changes required in each class to make it work. While this also wasn't that hard, I think that it was a good exerciser. I did something similar in the Components assignment, but I think this was a much better example of how to use inheritance.

Here is my code:


That's all for now, thanks for reading!

Replies 0 Comments Reply Reply

Calendar April 29, 2016 13:48

Blogger Blogger

Stack Class in C#

So this week there is no more homework for my C# class since the semester is coming to an end and we have a final exam next week.

Since I was bored at work, I started thinking that we never created a stack for one of the class assignments. So I decided to create my own, which wasn't that hard since its essentially just a wrapper around an array.

I started to work on it yesterday for a couple hours and finished it this morning.

Here is my code:


Thanks for reading!

Replies 0 Comments Reply Reply

Calendar April 27, 2016 02:48

Blogger Blogger

CS 2420 - Assignment 9 - Max Heap

This week's assignment is not as hard as the last one, we just have to create a heap data structure. We had the choice of either creating a min heap or max heap, so I went with Max since it made the most sense to me.

While the assignment its self wasn't too hard, it took me a while to do all the conditional logic behind the Sink() function.

Here is my code:

using System;
using System.Collections;
using System.Collections.Generic;

namespace Assignment9
{
    class MaxHeap<T> : IEnumerable<T> where T : IComparable
    {
        private T[] UnderlyingArray;
        private int ElementCount = 0;
        private int OldCount = 0;
        private bool IsHeap = true;

        public MaxHeap(int starting_size)
        {
            UnderlyingArray = new T[starting_size];
        }

        public MaxHeap()
        {
            UnderlyingArray = new T[5];
        }

        public int Count
        {
            get
            {
                return ElementCount;
            }
        }

        public void Clear()
        {
            UnderlyingArray = new T[UnderlyingArray.Length];
        }

        public T this[int index]
        {
            get
            {
                return UnderlyingArray[index];
            }
        }

        public void Add(T new_value)
        {
            if (!IsHeap)
                BuildHeap();

            if (ElementCount == UnderlyingArray.Length)
                Resize();

            UnderlyingArray[ElementCount] = new_value;
            Swim();
            ElementCount++;
        }

        public T PopTop()
        {
            if (!IsHeap)
                BuildHeap();

            T max = UnderlyingArray[0];

            Swap(0, ElementCount - 1);
            UnderlyingArray[ElementCount - 1] = default(T);
            ElementCount--;
            Sink();
            
            return max;
        }

        public void Sort()
        {
            if (!IsHeap)
                BuildHeap();

            OldCount = ElementCount;

            for (int i = 0; i < OldCount; i++)
            {
                Swap(0, ElementCount - 1);
                ElementCount--;
                Sink();
            }

            IsHeap = false;
            ElementCount = OldCount;
        }

        public void BuildHeap()
        {
            if (IsHeap)
                return;

            int last_item = OldCount - 1;

            for (int index = 0; index < OldCount / 2; index++)
            {
                Swap(index, last_item);
                last_item--;
            }

            ElementCount = OldCount;
            IsHeap = true;
        }

        private void Swim()
        {
            int current_index = ElementCount;

            while (current_index != 0)
            {
                int parent_index = FindParent(current_index);

                if (UnderlyingArray[current_index].CompareTo(UnderlyingArray[parent_index]) == 0)
                    break;

                else if (UnderlyingArray[current_index].CompareTo(UnderlyingArray[parent_index]) > 0)
                    Swap(current_index, parent_index);

                current_index = parent_index;
            }
        }

        private void Swap(int first, int second)
        {
            T temp = UnderlyingArray[first];
            UnderlyingArray[first] = UnderlyingArray[second];
            UnderlyingArray[second] = temp;
        }

        private void Sink()
        {
            int current_index = 0;

            while (current_index < ElementCount)
            {
                int max_child_index = current_index;
                int left_child_index = FindLeft(current_index);
                int right_child_index = FindRight(current_index);

                if (left_child_index >= ElementCount)
                    break;

                if (right_child_index >= ElementCount)
                    max_child_index = left_child_index;

                if (right_child_index < ElementCount &&
                    UnderlyingArray[left_child_index].CompareTo(UnderlyingArray[right_child_index]) == 0)
                    max_child_index = left_child_index;

                if (right_child_index < ElementCount && 
                    UnderlyingArray[left_child_index].CompareTo(UnderlyingArray[right_child_index]) > 0)
                    max_child_index = left_child_index;

                if (right_child_index < ElementCount && 
                    UnderlyingArray[left_child_index].CompareTo(UnderlyingArray[right_child_index]) < 0)
                    max_child_index = right_child_index;

                if (UnderlyingArray[max_child_index].CompareTo(UnderlyingArray[current_index]) == 0)
                    break;

                if (UnderlyingArray[max_child_index].CompareTo(UnderlyingArray[current_index]) > 0)
                    Swap(current_index, max_child_index);

                current_index = max_child_index;
            }
        }

        private int FindParent(int current_index)
        {
            return (current_index - 1) / 2;
        }

        private int FindLeft(int current_index)
        {
            return (current_index * 2) + 1;
        }

        private int FindRight(int current_index)
        {
            return (current_index * 2) + 2;
        }

        private void Resize()
        {
            T[] new_array = new T[UnderlyingArray.Length * 2];

            for (int index = 0; index < UnderlyingArray.Length; index++)
                new_array[index] = UnderlyingArray[index];

            UnderlyingArray = new_array;
        }

        public IEnumerator<T> GetEnumerator()
        {
            for (int index = 0; index < ElementCount; index++)
            {
                T temp = UnderlyingArray[index];
                //Console.WriteLine("Current Value: {0}", temp);
                yield return temp;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}

That's all for now, thanks for reading!

Replies 0 Comments Reply Reply

Calendar April 20, 2016 15:56

Blogger Blogger

CS 2420 - Assignment 8 - Components

This week's assignment is a bit more fun that usual since we are got to build a "game."

The point of this week's assignment to learn how to use components to build a game, instead of hard coding everything like we usually do. We also had a chance to review inheritance and understand how it works.

This time around there is too much code involved for me to put it here like I usually do, but if you are interested in looking at the code you can look here:

https://github.com/fushinoryuu/EAE2420/tree/master/DataStructuresAndSorts/Assignment8

I created these main class files: Component, Entity, Grid, Point, and Power Up.

The Grid was essentially a 2D array and everything ran through this file, it represented the map the player was going to play on. It also updated itself on the position of each enemy and the player and then displayed itself on the console.

The player and the enemies in the game all inherited from the Entity class and used a bunch of components to make each unique. For example, enemies had a component that allowed them to wrap around the Grid but the player was bound and couldn't go past the edges of the grid. To do this there was two components and I just had to make sure to give one to the player and the other to the enemies.

Power Ups are a type of component, but they don't inherit from the component class. I made it so they would modify the player's action. For example I had a Teleport Power Up. When they stepped on it, they would get randomly taken to an empty spot in the map.

I had a lot of fun with this assignment, but it took a little longer than I anticipated.

Anyways, that's all for now. Thanks for reading!

Replies 0 Comments Reply Reply

Calendar April 12, 2016 10:47

Blogger Blogger

CS 2420 - Assignment 7 - Hash Table

This week we had to write a hash table, also known as a dictionary. Hash tables are really nice because you can index with more than just integers, and they are faster running times than a regular array or a linked list.

Here is my code:


That's all for now, thanks for reading!

Replies 0 Comments Reply Reply

Calendar April 6, 2016 02:40

Blogger Blogger

CS 2420 - Assignment 6 - A Star

So this week we had to create a node graph and write our version of the A* (A Star) algorithm to find the shortest path. Here is the map we were given:



The map is not to scale, here are the coordinates of each node: 

A: -19, 11        B: -13, 13      C: 4, 14          D: -4, 12      E: -8, 3           F: -18, 1
G: -12, -8        H: 12, -9         I: -18, -11       J: -4, -11     K: -12, -14     L: 2, -18
M: 18, -13       N: 4, -9          O: 22, 11        P: 18, 3

I have seen multiple implementations of A* around the web, but they all use a matrix and it can get really complicated really quickly. I like this implementation better because its simple, but it works.

Here is my code:


That's all for now, thanks for reading!

Replies 0 Comments Reply Reply

Calendar March 30, 2016 22:05

Blogger Blogger

Breadth First Search - Matrix

So yesterday during class, we discussed how to make a path finding algorithm for a 2d map. I immediately thought of the example of flooding the map with water like I have seen before.

We didn't have to code it in class, we just had to know how one would write the algorithm. Last night I decided that I would try to code it and here is my work:


In my grid I make the starting cell marked with an X and the destination is marked with a D. The final path would be calculated by simply following the cell values in descending order to the final destination.

That's all for now, thanks for reading!

Replies 0 Comments Reply Reply

Calendar March 24, 2016 02:37

Blogger Blogger

CS 2420 - Assignment 5 - Part 5

So I just turned in my assignment a few minutes ago, and this is probably the hardest assignment yet. Most of the assignment was really simple actually, but the most challenging part was building the Expression Tree in the correct order.

This is because you have to keep the order of operations in mind when building the tree, Once the tree has been built in the correct order, its just a matter of doing a post-order traversal and evaluating as you go up the tree.

I kept thinking about how I should do this, and after talking to one of my friends, we realized that node rotations would be the simplest way to do it. So here is my code:

using System;
using System.Collections.Generic;

namespace Assignment5
{
    public TreeNode<string> root;

        public ExpressionTree(string input)
        {
            root = null;
            ExpressionParser parser = new ExpressionParser(this, input);
        }

        private class ExpressionParser
        {
            private Stack<TreeNode<string>> numberStack, operatorStack;

            public ExpressionParser(ExpressionTree tree, string input)
            {
                numberStack = new Stack<TreeNode<string>>();
                operatorStack = new Stack<TreeNode<string>>();
                string[] expressionArray = new string[input.Length];
                expressionArray = input.Split();

                BuildNodes(tree, expressionArray);
            }

            private void BuildNodes(ExpressionTree tree, string[] expressionArray)
            {
                foreach (string item in expressionArray)
                {
                    double tempNumber;
                    if (double.TryParse(item, out tempNumber))
                    {
                        TreeNode<string> number_node = new TreeNode<string> 
                            { Data = tempNumber.ToString() };
                        numberStack.Push(number_node);
                    }
                    else
                    {
                        TreeNode<string> operator_node = new TreeNode<string> 
                            { Data = item };
                        operatorStack.Push(operator_node);
                    }
                }
                BuildTree(tree);

            }

            private void BuildTree(ExpressionTree tree)
            {
                while (operatorStack.Count != 0)
                {
                    TreeNode<string> tempRoot = operatorStack.Pop();
                    tempRoot.Right = numberStack.Pop();
                    tempRoot.Left = numberStack.Pop();

                    if((tempRoot.Data == "*" || tempRoot.Data == "/") && 
                        (tempRoot.Right.Data == "+" || tempRoot.Right.Data == "-"))
                    {
                        tempRoot = tree.RotateLeft(tempRoot);
                    }
                    numberStack.Push(tempRoot);
                }
                TreeNode<string> subTree = numberStack.Pop();
                tree.root = tree.RotateLeft(subTree);
            }
        }

        private TreeNode<string> RotateLeft(TreeNode<string> currentNode)
        {
            TreeNode<string> tempNode = currentNode;
            currentNode = currentNode.Right;
            tempNode.Right = currentNode.Left;
            currentNode.Left = tempNode;
            return currentNode;
        }

        public void Evaluate(TreeNode<string> node)
        {
            if (node.Left != null)
                Evaluate(node.Left);
            if (node.Right != null)
                Evaluate(node.Right);
            switch (node.Data)
            {
                case "+":
                    double addResult = double.Parse(node.Left.Data) + 
                        double.Parse(node.Right.Data);
                    node.Data = addResult.ToString();
                    node.Left = null;
                    node.Right = null;
                    break;
                case "-":
                    double subResult = double.Parse(node.Left.Data) - 
                        double.Parse(node.Right.Data);
                    node.Data = subResult.ToString();
                    node.Left = null;
                    node.Right = null;
                    break;
                case "*":
                    double multResult = double.Parse(node.Left.Data) * 
                        double.Parse(node.Right.Data);
                    node.Data = multResult.ToString();
                    node.Left = null;
                    node.Right = null;
                    break;
                case "/":
                    double divResult = double.Parse(node.Left.Data) / 
                        double.Parse(node.Right.Data);
                    node.Data = divResult.ToString();
                    node.Left = null;
                    node.Right = null;
                    break;
                case "^":
                    double expResult = Math.Pow(double.Parse(node.Left.Data), 
                        double.Parse(node.Right.Data));
                    node.Data = expResult.ToString();
                    node.Left = null;
                    node.Right = null;
                    break;
            }
        }

        public string TraversePre(MyList<string> list, TreeNode<string> node)
        {
            list.Add(node.Data);
            if (node.Left != null)
                TraversePre(list, node.Left);
            if (node.Right != null)
                TraversePre(list, node.Right);
            return string.Join(", ", list);
        }

        public string TraverseIn(MyList<string> list, TreeNode<string> node)
        {
            if (node.Left != null)
                TraverseIn(list, node.Left);
            list.Add(node.Data);
            if (node.Right != null)
                TraverseIn(list, node.Right);
            return string.Join(", ", list);
        }

        public string TraversePost(MyList<string> list, TreeNode<string> node)
        {
            if (node.Left != null)
                TraversePost(list, node.Left);
            if (node.Right != null)
                TraversePost(list, node.Right);
            list.Add(node.Data);
            return string.Join(", ", list);
        }
    }
}

I was not able to make my Binary Search Tree self balancing. I know what I need to do, but I never had time to actually implement the code. I will try to finish writing the code and post it here when I'm done with my AVL tree.

Anyways, that's all for now. Thanks for reading!

Replies 0 Comments Reply Reply

Calendar March 16, 2016 23:19

Blogger Blogger

CS 2420 - Assignment 5 - Part 4

So I've been working more on my Expression Tree and after talking to another student, I realized that I could restructure my files.The Expression Tree works with a total of 3 class files: the Node, the expression parser, and the tree class itself.

At first I had created each class in separate class files, but it was kind of weird how I was parsing the input and how I was building the tree. So I decided to move my Expression Parser class to be nested within my Expression Tree class. This would allow me to do all the parsing and building of the tree within one class file instead of two where it can get messy and confusing.

Here is my new code, thanks for reading:

using System;
using System.Collections.Generic;

namespace Assignment5
{
    class ExpressionTree
    {
        public TreeNode<string> root;
        private int node_count;

        public ExpressionTree(string input)
        {
            root = null;
            ExpressionParser parser = new ExpressionParser(this, input);
        }

        private class ExpressionParser
        {
            private Stack<TreeNode<string>> numberStack, operatorStack;

            public ExpressionParser(ExpressionTree tree, string input)
            {
                numberStack = new Stack<TreeNode<string>>();
                operatorStack = new Stack<TreeNode<string>>();
                Console.WriteLine(input.Length);
                string[] expressionArray = new string[input.Length];
                expressionArray = input.Split();

                BuildNodes(tree, expressionArray);
            }

            private void BuildNodes(ExpressionTree tree, string[] expressionArray)
            {
                foreach (string item in expressionArray)
                {
                    int tempInt;
                    if (Int32.TryParse(item, out tempInt))
                    {
                        TreeNode<string> number_node = new TreeNode<string> { Data = tempInt.ToString() };
                        numberStack.Push(number_node);
                    }
                    else
                    {
                        TreeNode<string> operator_node = new TreeNode<string> { Data = item };
                        operatorStack.Push(operator_node);
                    }
                }
                BuildTree(tree);
            }

            private void BuildTree(ExpressionTree tree)
            {
                tree.node_count = numberStack.Count + operatorStack.Count;

                while (operatorStack.Count != 0)
                {
                    TreeNode<string> tempRoot = operatorStack.Pop();
                    tempRoot.Right = numberStack.Pop();
                    tempRoot.Left = numberStack.Pop();
                    numberStack.Push(tempRoot);
                }

                tree.root = numberStack.Pop();
            }
        }

        public int NodeCount
        {
            get
            {
                return node_count;
            }
        }

        // TODO Finish Evaluate
        public void Evaluate(MyList<string> list, TreeNode<string> node)
        {
            if (node.Left != null)
                Evaluate(list, node.Left);
            if (node.Right != null)
                Evaluate(list, node.Right);
            throw new NotImplementedException();
        }

        public string TraversePre(MyList<string> list, TreeNode<string> node)
        {
            list.Add(node.Data);
            if (node.Left != null)
                TraversePre(list, node.Left);
            if (node.Right != null)
                TraversePre(list, node.Right);
            return string.Join(", ", list);
        }

        public string TraverseIn(MyList<string> list, TreeNode<string> node)
        {
            if (node.Left != null)
                TraverseIn(list, node.Left);
            list.Add(node.Data);
            if (node.Right != null)
                TraverseIn(list, node.Right);
            return string.Join(", ", list);
        }

        public string TraversePost(MyList<string> list, TreeNode<string> node)
        {
            if (node.Left != null)
                TraversePost(list, node.Left);
            if (node.Right != null)
                TraversePost(list, node.Right);
            list.Add(node.Data);
            return string.Join(", ", list);
        }
    }
}

Replies 0 Comments Reply Reply

Calendar March 9, 2016 10:37

Blogger Blogger

CS 2420 - Assignment 5 - Part 3

I have not been able to make my Binary Search Tree self balancing. I know how the nodes should behave on paper, but I haven't been able to do it in code.

Yesterday after class, I figured out how to finish my Expression Tree and the Parser that takes the user's input.

Expression Tree:

using System;

namespace Assignment5
{
    class ExpressionTree
    {
        public TreeNode<string> root;
        public int node_count;

        public ExpressionTree()
        {
            root = null;
        }

        // TODO Finish Evaluate
        public void Evaluate()
        {

        }

        public string TraversePre(MyList<string> list, TreeNode<string> node)
        {
            list.Add(node.data);
            if (node.left != null)
                TraversePre(list, node.left);
            if (node.right != null)
                TraversePre(list, node.right);
            return string.Join(", ", list);
        }

        public string TraverseIn(MyList<string> list, TreeNode<string> node)
        {
            if (node.left != null)
                TraverseIn(list, node.left);
            list.Add(node.data);
            if (node.right != null)
                TraverseIn(list, node.right);
            return string.Join(", ", list);
        }

        public string TraversePost(MyList<string> list, TreeNode<string> node)
        {
            if (node.left != null)
                TraversePost(list, node.left);
            if (node.right != null)
                TraversePost(list, node.right);
            list.Add(node.data);
            return string.Join(", ", list);
        }
    }
}

Parser:

using System;
using System.Collections;
using System.Collections.Generic;

namespace Assignment5
{
    class ExpressionParser
    {
        private Stack<TreeNode<string>> numberStack, operatorStack;

        public ExpressionParser(ExpressionTree ETree, string input)
        {
            numberStack = new Stack<TreeNode<string>>();
            operatorStack = new Stack<TreeNode<string>>();

            ToArray(ETree, input);
        }

        public void ToArray(ExpressionTree ETree, string input)
        {
            string[] expressions = new string[input.Length];
            expressions = input.Split();

            BuildNodes(expressions, ETree);
        }

        private void BuildNodes(string[] expressions, ExpressionTree ETree)
        {
            foreach (string item in expressions)
            {
                int tempInt;
                if (Int32.TryParse(item, out tempInt))
                {
                    TreeNode<string> number_node = new TreeNode<string> { data = tempInt.ToString() };
                    numberStack.Push(number_node);
                }
                else                {
                    TreeNode<string> operator_node = new TreeNode<string> { data = item };
                    operatorStack.Push(operator_node);
                }
            }
            BuildTree(ETree);
        }

        private void BuildTree(ExpressionTree ETree)
        {
            ETree.node_count = numberStack.Count + operatorStack.Count;

            while (operatorStack.Count != 0)
            {
                TreeNode<string> tempRoot = operatorStack.Pop();
                tempRoot.right = numberStack.Pop();
                tempRoot.left = numberStack.Pop();
                numberStack.Push(tempRoot);
            }

            ETree.root = numberStack.Pop();
        }
    }
}

I will continue to work on this assignment. Thanks for reading!

Replies 0 Comments Reply Reply

Calendar March 7, 2016 00:29

Blogger Blogger

CS 2420 - Assignment 5 - Part 2

So I've been working on my Binary Search tree a bit more, and I have made some changes since last time. For example, in the assignment the traverse functions need to return a string of the numbers instead of being void.

Here is what I have now:

using System;

class BinarySearchTree
{
    public TreeNode root;
    private int node_count;

    public BinarySearchTree()
    {
        root = null;
        node_count = 0;
    }

    public void Add(int item)
    {
        TreeNode new_node = new TreeNode(item);

        if (root == null)
            root = new_node;
        else
        {
            TreeNode crawler = root;

            while (crawler != null)
            {
                new_node.parent = crawler;
                if (item >= crawler.data)
                    crawler = crawler.right;
                else
                    crawler = crawler.left;
            }

            if (item >= new_node.parent.data)
                new_node.parent.right = new_node;
            else
                new_node.parent.left = new_node;
        }
        node_count++;
        CalculateHeight(root);
        Console.WriteLine("");
    }

    public TreeNode Contains(int item)
    {
        TreeNode crawler = root;

        while (crawler != null)
        {
            if (item == crawler.data)
                return crawler;
            else if (item >= crawler.data)
                crawler = crawler.right;
            else
                crawler = crawler.left;
        }
        return null;
    }

    // TODO Finish Remove function
    public void Remove(TreeNode node)
    {
        if (node == null)
            Console.WriteLine("\nCould not remove the node you were looking for!\n");
        else
        {
            //Work needed
        }
    }

    public void Clear()
    {
        root = null;
        node_count = 0;
    }

    public int NodeCount
    {
        get
        {
            return node_count;
        }
    }

    private void CalculateHeight(TreeNode node)
    {
        if (node.left != null)
            CalculateHeight(node.left);
        if (node.right != null)
            CalculateHeight(node.right);

        if (node.left != null && node.right != null)
            node.height = Math.Max(node.left.height, node.right.height) + 1;

        else if (node.left != null && node.right == null)
            node.height = node.left.height + 1;

        else if (node.left == null && node.right != null)
            node.height = node.right.height + 1;

        else if (node.left == null && node.right == null)
            node.height = 1;
        Console.WriteLine("Node value: {0} Node Height: {1}", node.data, node.height);
        CheckBalance(node);
    }

    private void CheckBalance(TreeNode node)
    {
        if (node.left == null && node.right == null)
            return;

        else if (node.left != null && node.right == null)
            if (node.left.height > 1)
                Rotate(node);

            else if (node.left == null && node.right != null)
                if (node.right.height > 1)
                    Rotate(node);

                else if (node.left != null && node.right != null)
                {
                    if (node.left.height > node.right.height + 1)
                        Rotate(node.left);
                    else if (node.right.height > node.left.height + 1)
                        Rotate(node.right);
                }
    }

    // TODO Finish Rotate function
    private void Rotate(TreeNode node)
    {
        //Work needed
    }

    public string TraversePre(MyList list, TreeNode node)
    {
        list.Add(node.data);
        if (node.left != null)
            TraversePre(list, node.left);
        if (node.right != null)
            TraversePre(list, node.right);
        return string.Join(", ", list);
    }

    public string TraverseIn(MyList list, TreeNode node)
    {
        if (node.left != null)
            TraverseIn(list, node.left);
        list.Add(node.data);
        if (node.right != null)
            TraverseIn(list, node.right);
        return string.Join(", ", list);
    }

    public string TraversePost(MyList list, TreeNode node)
    {
        if (node.left != null)
            TraversePost(list, node.left);
        if (node.right != null)
            TraversePost(list, node.right);
        list.Add(node.data);
        return string.Join(", ", list);
    }
}

There has been a few changes to the rest of the code as well. I have been trying to figure out how to make my tree self balancing. And while I have been able to calculate the depth/height of each node, I am running into issues on how I should rotate the nodes. I am also working on removing nodes, but I haven't made much progress in that department either.

Anyways, that's all for now. Thanks for reading!

Replies 0 Comments Reply Reply

Calendar March 3, 2016 19:24

Blogger Blogger

CS 2420 - Assignment 5 - Part 1

So even though there is no assignment this week, I asked the professor to post the next assignment early. It turns out that writing my Linked List class a few days ago was a good call, because the next assignment will be Trees!

The assignment will have us built two trees: a Binary Search Tree and a Binary Expression Tree.

I have started working on both, but I have been mainly focusing on the BS Tree since to me its the easiest of the two. I am actually almost done with the BS Tree, here is what I have:

class BinarySearchTree
{
    public TreeNode root;
    private int node_count;

    public BinarySearchTree()
    {
        root = null;
        node_count = 0;
    }

    public void Add(int item)
    {
        TreeNode new_node = new TreeNode(item);
        if (root == null)
            root = new_node;
        else
        {
            TreeNode crawler = root;

            while (crawler != null)
            {
                new_node.parent = crawler;
                if (item >= crawler.data)
                    crawler = crawler.right;
                else
                    crawler = crawler.left;
            }

            if (item >= new_node.parent.data)
                new_node.parent.right = new_node;
            else
                new_node.parent.left = new_node;
        }
        node_count++;
    }

    public bool Contains(int item)
    {
        TreeNode crawler = root;
        while (crawler != null)
        {
            if (item == crawler.data)
                return true;
            else if (item >= crawler.data)
                crawler = crawler.right;
            else
                crawler = crawler.left;
        }
        return false;
    }

    public void Clear()
    {
        root = null;
        node_count = 0;
    }

    public int NodeCount
    {
        get
        {
            return node_count;
        }
    }

    public void TraversePre(MyList list, TreeNode node)
    {
        list.Add(node.data);
        if (node.left != null)
            TraversePre(list, node.left);
        if (node.right != null)
            TraversePre(list, node.right);
    }

    public void TraverseIn(MyList list, TreeNode node)
    {
        if (node.left != null)
            TraverseIn(list, node.left);
        list.Add(node.data);
        if (node.right != null)
            TraverseIn(list, node.right);
    }

    public void TraversePost(MyList list, TreeNode node)
    {
        if (node.left != null)
            TraversePost(list, node.left);
        if (node.right != null)
            TraversePost(list, node.right);
        list.Add(node.data);
    }
}

My Binary Search Tree takes advantage of the List class I wrote for assignment 4 and of a Node class that has only three properties: Left, Right, & Parent. That's all for now, thanks for reading!

Replies 0 Comments Reply Reply

Calendar March 1, 2016 17:25

Blogger Blogger

Linked List class in C#

So today I was bored at work, and decided to write a Linked List in C# to get more practice with the language and get more familiar with Visual Studio.

I also decided to make my own enumerator for the linked list. Here is what I wrote:

Replies 0 Comments Reply Reply

Calendar February 26, 2016 22:27

Blogger Blogger

CS 2420 - Assignment 4 - Part 5

So now that I am done with the List class, I have moved on to another part of the assignment. This time I have to plot the running times of my sorts.

After thinking about it for a while, I decided that I would create a new class that would just be called from the Main function and it would sort lists of different sizes and it would output the time in milliseconds to a text file. This would make it easier to actually make a graph for each sort. In a graph, X would be the number of elements in the list and Y would be the time it took to sort the list.

Here is what I have for this new class:

using System;
using System.Diagnostics;
using System.IO;

class RunningTimes
{
    public static void SortPlot(ISorter sorter, int elements, string name)
    {
        Random randint = new Random();
        Stopwatch watch = new Stopwatch();
        StreamWriter file = new StreamWriter(@"ChristianMunoz_RunningTimes.txt", true);
        long time = watch.ElapsedMilliseconds;
        int[] list;

        while(elements > 0)
        {
            list = new int[elements];

            for (int i = 0; i < list.Length; i++)
                list[i] = randint.Next(1, 200);

            watch.Reset();
            watch.Start();
            sorter.sort(list, 0, list.Length);
            watch.Stop();
            time = watch.ElapsedMilliseconds;
            Console.WriteLine(time);

            file.WriteLine("Sort: {0} Element count: {1} Time in Milliseconds: {2}", name, elements, time);

            elements = elements - 10000;
        }
        file.WriteLine(" ");
        file.Close();
    }
}

In the part that says: @"ChristianMunoz_RunningTimes.txt" that is the location and name of the text file I'm creating. You can change the name to anything you want, and you can find the file in your pc by first going to the folder where you have your C# work: Documents\CSharp\DataStructuresAndSorts\Assignment4\bin\Debug. Or you can also replace the name and tell Visual Studio a specific location by pasting in a path that you want.

This is how I call the function from my main:

RunningTimes.SortPlot(qSorter, 70000, "Quick Sort");

Since this new class isn't doing anything special, I don't have to create a new instance of the class and I can just call it from my other file. In the above example: I pass in a Quick Sort object, I tell it how big I want my list to be (in this case it will be 70000 integers), and just for kicks I pass in a string to make it easier to read the txt file of the sort that I am on. The output of the file will look like this:

Quick Sort Element count: 70000 Time in Milliseconds: 93
Quick Sort Element count: 60000 Time in Milliseconds: 72
Quick Sort Element count: 50000 Time in Milliseconds: 48
Quick Sort Element count: 40000 Time in Milliseconds: 37
Quick Sort Element count: 30000 Time in Milliseconds: 20
Quick Sort Element count: 20000 Time in Milliseconds: S
Quick Sort Element count: 10000 Time in Milliseconds: 2

That's all for now, thanks for reading!

Replies 0 Comments Reply Reply

Calendar February 25, 2016 19:03

Blogger Blogger

CS 2420 - Assignment 4 - Part 4

Since last time I have been working on implementing my own Enumerator in my List class. I started to work on it Tuesday night while in class, but I was actually stuck on this assignment until earlier today when I figured it out.

Here is the finished Enumerator class:

private class myEnumerator : IEnumerator
{
    private MyList myList;
    private int index;

    public myEnumerator(MyList myList)
    {
        this.myList = myList;
        index = -1;
    }

    public bool MoveNext()
    {
        index++;
        return (index < myList.Count);
    }

    public T Current
    {
        get
        {
            return myList[index];
        }
    }

    object IEnumerator.Current
    {
        get
        {
            return Current;
        }
    }

    // Not Needed
    public void Dispose()
    {
        //Not Needed
    }

    public void Reset()
    {
        index = -1;
    }
}

This new class is embedded in the List class, and it just spits out the next item in the list. The cool thing about this new Enumerator is that it will stop as soon as it reached the Count of the items in the list instead of the length of the array. This way if there are any empty slots in the array, they won't get printed in the list.

That's all for now, thanks for reading!

Replies 0 Comments Reply Reply