#Double Ended Queue (Dequeue) | Explore Tumblr posts and blogs

sanesquaregg · 3 years ago

Text

The Collection Framework in Java

What is a Collection in Java?

Java collection is a single unit of objects. Before the Collections Framework, it had been hard for programmers to write down algorithms that worked for different collections. Java came with many Collection classes and Interfaces, like Vector, Stack, Hashtable, and Array.

In JDK 1.2, Java developers introduced theCollections Framework, an essential framework to help you achieve your data operations.

Why Do We Need Them?

Reduces programming effort & effort to study and use new APIs

Increases program speed and quality

Allows interoperability among unrelated APIs

Reduces effort to design new APIs

Fosters software reuse

Methods Present in the Collection Interface

NoMethodDescription1Public boolean add(E e)To insert an object in this collection.2Public boolean remove(Object element)To delete an element from the collection.3Default boolean removeIf(Predicate filter)For deleting all the elements of the collection that satisfy the specified predicate.4Public boolean retainAll(Collection c)For deleting all the elements of invoking collection except the specified collection.5Public int size()This return the total number of elements.6Publicvoid clear()This removes the total number of elements.7Publicboolean contains(Object element)It is used to search an element.8PublicIterator iterator()It returns an iterator.9PublicObject[] toArray()It converts collection into array.

Collection Framework Hierarchy

List Interface

This is the child interface of the collectioninterface. It is purely for lists of data, so we can store the ordered lists of the objects. It also allows duplicates to be stored. Many classes implement this list interface, including ArrayList, Vector, Stack, and others.

Array List

It is a class present in java. util package.

It uses a dynamic array for storing the element.

It is an array that has no size limit.

We can add or remove elements easily.

Linked List

The LinkedList class uses a doubly LinkedList to store elements. i.e., the user can add data at the initial position as well as the last position.

It allows Null insertion.

If we’d wish to perform an Insertion /Deletion operation LinkedList is preferred.

Used to implement Stacks and Queues.

Vector

Every method is synchronized.

The vector object is Thread safe.

At a time, one thread can operate on the Vector object.

Performance is low because Threads need to wait.

Stack

It is the child class of Vector.

It is based on LIFO (Last In First Out) i.e., the Element inserted in last will come first.

Queue

A queue interface, as its name suggests, upholds the FIFO (First In First Out) order much like a conventional queue line. All of the elements where the order of the elements matters will be stored in this interface. For instance, the tickets are always offered on a first-come, first-serve basis whenever we attempt to book one. As a result, the ticket is awarded to the requester who enters the queue first. There are many classes, including ArrayDeque, PriorityQueue, and others. Any of these subclasses can be used to create a queue object because they all implement the queue.

Dequeue

The queue data structure has only a very tiny modification in this case. The data structure deque, commonly referred to as a double-ended queue, allows us to add and delete pieces from both ends of the queue. ArrayDeque, which implements this interface. We can create a deque object using this class because it implements the Deque interface.

Set Interface

A set is an unordered collection of objects where it is impossible to hold duplicate values. When we want to keep unique objects and prevent object duplication, we utilize this collection. Numerous classes, including HashSet, TreeSet, LinkedHashSet, etc. implement this set interface. We can instantiate a set object with any of these subclasses because they all implement the set.

LinkedHashSet

The LinkedHashSet class extends the HashSet class.

Insertion order is preserved.

Duplicates aren’t allowed.

LinkedHashSet is non synchronized.

LinkedHashSet is the same as the HashSet except the above two differences are present.

HashSet

HashSet stores the elements by using the mechanism of Hashing.

It contains unique elements only.

This HashSet allows null values.

It doesn’t maintain insertion order. It inserted elements according to their hashcode.

It is the best approach for the search operation.

Sorted Set

The set interface and this interface are extremely similar. The only distinction is that this interface provides additional methods for maintaining the elements' order. The interface for handling data that needs to be sorted, which extends the set interface, is called the sorted set interface. TreeSet is the class that complies with this interface. This class can be used to create a SortedSet object because it implements the SortedSet interface.

TreeSet

Java TreeSet class implements the Set interface it uses a tree structure to store elements.

It contains Unique Elements.

TreeSet class access and retrieval time are quick.

It doesn’t allow null elements.

It maintains Ascending Order.

Map Interface

It is a part of the collection framework but does not implement a collection interface. A map stores the values based on the key and value Pair. Because one key cannot have numerous mappings, this interface does not support duplicate keys. In short, The key must be unique while duplicated values are allowed. The map interface is implemented by using HashMap, LinkedHashMap, and HashTable.

HashMap

Map Interface is implemented by HashMap.

HashMap stores the elements using a mechanism called Hashing.

It contains the values based on the key-value pair.

It has a unique key.

It can store a Null key and Multiple null values.

Insertion order isn’t maintained and it is based on the hash code of the keys.

HashMap is Non-Synchronized.

How to create HashMap.

LinkedHashMap

The basic data structure of LinkedHashMap is a combination of LinkedList and Hashtable.

LinkedHashMap is the same as HashMap except above difference.

HashTable

A Hashtable is an array of lists. Each list is familiar as a bucket.

A hashtable contains values based on key-value pairs.

It contains unique elements only.

The hashtable class doesn’t allow a null key as well as a value otherwise it will throw NullPointerException.

Every method is synchronized. i.e At a time one thread is allowed and the other threads are on a wait.

Performance is poor as compared to HashMap.

This blog illustrates the interfaces and classes of the java collection framework. Which is useful for java developers while writing efficient codes. This blog is intended to help you understand the concept better.

At Sanesquare Technologies, we provide end-to-end solutions for Development Services. If you have any doubts regarding java concepts and other technical topics, feel free to contact us.

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

You have been hired by a major supermarket chain to model the operation of a proposed supermarket by using a Discrete Event Simulation. The shop has several servers (or checkouts), each of which has a different level of efficiency due to the experience of the server operator. It also takes longer to serve credit card customers. The service time of each customer is calculated as follows: service_time = (tally_time x efficiency) + payment_time where: tally_time: time it takes to tally up the customer's goods efficiency: the efficiency of the server payment_time: 0.3 for cash or 0.7 for credit card The input file “ass2.txt” contains the records of each customer entering the shop and consist of: arrival time (at the server queue), tally time (time it takes to scan the customer's items and add up the cost) payment method (cash or card). Your program should: Open the text file “ass2.txt” (Note: “ass2.txt” should be a hardcoded as a constant.) 2. Read the efficiencies of each server. Read and process the customer arrival and service time data. Print service statistics on the screen. Note: This shop has a single queue of customers waiting to be served. The servers are initially all idle. If more than one idle server is available, the next customer is served by the server with the best efficiency (i.e. the smallest efficiency value). Customers must be served or queued in the order in which they arrive. You should not attempt to read in all the arrival data at the start of the simulation. At the end of the simulation, after the last customer in the file has been served, your program should print out the following information: The number of customers served. The time that it took to serve all the customers. The greatest length reached by the customer queue. The average length of the customer queue. The average time spent by a customer in the customer queue. (If a customer is served immediately, their queue time is 0.0). The percentage of customers who’s waiting time in the customer queue was 0 (zero). For each server: The number of customers they served The time they spent idle. You must choose appropriate data structures and algorithms to accomplish this task quickly. You will lose marks if you use STL, or equivalent libraries, to implement data structures or algorithms. Note: A larger input data file may be used for the final assessment of your program.

Step-1 (Week-7 demo, 2 marks)

Test your customer queue by declaring an instance of it in the main(). Use a for loop to add 10 records to the queue. Set the arrival time for each record between 1 and 100 using rand() or random(). The other fields can be set to 0 or false. Also, print the arrival times on the screen as you add them. Now use a while loop to remove all the records from the customer queue and print the arrival times on the screen. Is the output correct? Now implement the simulator's event queue (i.e. a priority queue). The event queue’s records should contain an event type (int or enum), event time & tally time (doubles), and payment method (boolean). You can assume the maximum number of events in the event queue is 100. The record with the minimum event time has the highest priority.

Test the event queue by declaring an instance of it in the main(). Use the while loop (implemented previously) to remove records from the customer queue and add them to the event queue. Set the event time with the customer's arrival time. Set the other fields to zero. Then implement a while loop in the main() to remove (dequeue) each record from the event queue and print the event time on the screen. Is the output correct? Note: For step-1 (to get the 2 demo marks) you can implement the customer and event queues using any method you like. However, for the final submission, to get full marks, you should ensure all data structures and algorithms are optimised for speed.

Step-2 (Server array implementation)

The server array should have a maximum of 20 servers. Each server should have a busy flag (boolean), an efficiency factor (double) and other data members for calculating the stats. C++ and Java coders should implement the server array with a class, preferably, and provide public functions for adding, and removing customers to/from the servers, finding the fasted idle server, etc. according to the specs on page 1.

Step-3 (Processing in the data)

When you have the customer queue, event queue and server array correctly completed, delete the main() test code from step 1 and replace it with code for reading the input data file “ass2.txt” and processing the data, as explained on page 1. The following algorithm shows how a typical discrete time simulator can be implemented: main() Declare variables and instances and do initialisations Open the input data file; if not found print error and exit Read first CustomerArrival event from file and add it to the event queue While the event queue is not empty . . . Get the next event from the event queue and set CrntTime to the event time If the event type = CustomerArrival event . . . if an idle server is available . . . Find fastest idle serve set the server’s idle flag to busy calculate the server’s finish time from event's customer data add ServerFinish event to the event queue Else Add event's customer to the customer queue End if If not EOF . . . Read next customer arrival from file add CustomerArrival event to the event queue End if Else // event type must be a ServerFinish event . . . Get server no. from event, set server to idle and do server's stats If customer queue is not empty . . . Get next customer from the customer queue Find fastest idle serve set the server’s idle flag to busy. calculate the server’s finish time add ServerFinish event to the event queue End if End if End while Print stats End main()

Step-4 (Optimisation and stats)

When you have the discrete time simulation working correctly, add the necessary data members and variables needed for calculating all the required stats, as explained on page 1, and optimise your simulator for speed.

Step-5 (Specifications)

In a comment block at the bottom of your program (no more than 20 lines of text) list all the data structures and algorithms used by your program to process the input data. Include any enhancements you did to speed up your program (if any). For this step, marks will be awarded based on how accurately and clearly you describe your program.

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

Marks will be awarded for the appropriate use of data structures and the efficiency of the program at processing the input and producing the correct output. Marks may be deducted for untidy or poorly designed code. Appropriate comments should be provided where needed. There will be a deduction of up to 4 marks for using STL, or equivalent libraries, rather than coding the data structures and algorithms yourself. You may use string or String type for storing words or text, if you wish. All coding and comments must be your own work. Submission: Assignments should be typed into a single text file named "ass2.ext" where "ext" is the appropriate file extension for the chosen language. You should run your program and copy and paste the output into a text file named: "output.txt" Submit your files via the submit program on banshee: submit -u user -c csci203 -a 2 ass1.ext output.txt - where user is your unix userid and ext is the extn of your code file. Late assignment submissions without granted extension will be marked but the points awarded will be reduced by 1 mark for each day late. Assignments will not be accepted if more than five days late. An extension of time for the assignment submission may be granted in certain circumstances. Any request for an extension of the submission deadline must be made via SOLS before the submission deadline. Supporting documentation should accompany the request for any extension. Read the full article

0 notes

codezclub · 8 years ago

Text

C Program to implement Deque using circular array

Implement Deque using circular array Write a C Program to implement Deque using circular array. Here’s simple Program to implement Deque using circular array in C Programming Language. What is Queue ? Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR, and the deletion of existing element takes place from the other end…

View On WordPress

#c data structures #c queue programs #dequeue in c using arrays #dequeue in data structure using c #dequeue in data structure with example #dequeue program in c using array #double ended queue in c #double ended queue in c using arrays #double ended queue in data structure #double ended queue in data structure program

0 notes

myprogrammingsolver · 6 years ago

Text

Programming Assignment 2: Randomized Queues and Deques Solution

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 inserting and removing items from either the front or the back of the…

View On WordPress

0 notes

knoldus · 7 years ago

Link

In our previous blog The Story of Trait – Part 3, we have discussed the mixin, one of the charming feature of traits. Now we are going to explore chaining of traits.

We have seen how can we mix more than one traits into classes. But what would happen if two traits have same method i.e same name and same signature?

This is where Multiple Inheritance fails. And Traits works really well in such scenario because Traits are Stackable.

What is meant by Stackability?

Suppose we have traits T1, T2 and class A. We have another class B which extends class A and mix traits T1 and T2.

class B extends A with T1 with T2

What will happen in this case?

Methods in T1 and T2 instead of colliding with each other they collaborate to form a chain.

An instance of B will chain with an instance of T1 which will chain to an instance of T2. So, when a method is invoked which has the same name in both traits, the first T2 will handle it and T2 could forward it to T1 which after doing some work could forward to an instance of B. And that removes the collision and ends up collaborating nicely.

Let’s take an example from Programming in Scala Book,

We have an abstract class Queue and implemented by a class QueueImplementation.

scala> abstract class Queue{ | | def dequeue(): Option[Int] | | def enqueue(x: Int) | | } defined class Queue scala> class QueueImplementation extends Queue { | | private val queue = new scala.collection.mutable.ListBuffer[Int] | | def dequeue = if(queue.isEmpty) { | println("Queue is empty") | None | } | else Some(queue.remove(0)) | | def enqueue(element: Int) = queue += element | | def showQueue = println(s"Queue: $queue") | } defined class QueueImplementation scala> val queue = new QueueImplementation queue: QueueImplementation = QueueImplementation@4e6ddf37 scala> queue.enqueue(1); queue.enqueue(2); queue.enqueue(3) scala> queue.showQueue Queue: ListBuffer(1, 2, 3) scala> queue.dequeue res26: Option[Int] = Some(1) scala> queue.showQueue Queue: ListBuffer(2, 3)

Well, that works fine. What we need to put the double elements in the queue. We don’t want to change the implementation of Queue. Because Future might demand different implementation like incrementing element. So, We could define traits to provide different modifications like incrementing and doubling the element of Queue. Let’s try creating a trait for double elements.

scala> trait Doubling extends Queue { | abstract override def enqueue(x: Int) = super.enqueue(x * 2) | } defined trait Doubling

Here extends does not mean inheriting from Queue. It is used as a constraint here. extends means that trait can only be used or mixin those classes which extend from Queue like QueueImplementation. For more info refer.

Likewise, super here does not mean going to base class in the context of the inheritance hierarchy. But it means going from right to left in chaining of traits. It performs the late binding of that call. And the method is declared abstract override, this is a deadly combination of abstract and override together. By using the keyword override means, we are telling Scala that we are providing an implementation of a known method from the base class. At the same time, we are saying that the actual final implementation of this method will be provided by a class that mixes in the trait.

Let’s define another trait which will increment the element of Queue.

scala> trait Incrementing extends Queue { | abstract override def enqueue(x: Int) = super.enqueue(x + 1) | } defined trait Incrementing scala> val queue = new QueueImplementation with Incrementing with Doubling queue: QueueImplementation with Incrementing with Doubling = $anon$1@35bcb2b4

We have created an object of QueueImplementation with mixing Incrementing and Doubling trait to it. What would be the output if we enqueue any element i.e 4. Will it get doubled or incremented? Will it be 8 or 5?

scala> queue.enqueue(4) scala> queue.showQueue Queue: ListBuffer(9)

We know traits are stackable, So when we enqueue the element 4, what it did first it went to Doubling, which doubled the elements and then went to Incrementing which increment doubled element by 1 and then went to QueueImplementation which enqueue the element in the queue.

scala> val queue = new QueueImplementation with Doubling with Incrementing queue: QueueImplementation with Doubling with Incrementing = $anon$1@532ef241 scala> queue.enqueue(4) scala> queue.showQueue Queue: ListBuffer(10)

Similarly, this time first call went to Incrementing which incremented the value and then went to Doubling to double the value and finally to QueueImplementation class to put the element in the queue.

We have seen how Scala Traits are Stackable. There is no diamond problem in Scala because methods don’t collide instead they start collaborating with each other to form a chaining. The method call is determined by linearization of the classes and traits that are mixed into a class. When we instantiate a class with new, Scala takes the class, and all of its inherited classes and traits, and put them in a linear order. And super call starts calling a method from right to left and net result is the stackable behaviour.

Please feel free to suggest and comment.

References:

Pragmatic Scala

Programming in Scala

#WordPress

0 notes

mlbors · 7 years ago

Text

Discovering C#

Through this article, we are going to take a look at the programming language named C#. Let's get into it!

Introduction

First of all, we are not going to look at C# in every single detail because it is not the purpose of this article and it would probably take a whole book. Our goal here is to simply get familiar with this very common language. We are going to have a look at the very basics of this language and go a little further after that. This article is some kind of introduction to this language.

What is C#?

C#, or C Sharp, is a programming language developed by Microsoft. We usually say that it is an object-oriented programming language, but in fact, it is a multi-paradigm programming language. It was designed to be used with the .NET Framework. It is derived from C and C++ and it is really similar to Java.

C# programs run on the .NET Framework through a virtual execution system called the Common Language Runtime (CLR). When we compile a program written in C#, it is transformed to an Intermediate Language (IL). That last code and all the resources a stored in an executable file called Assembly. When the program is executed, the Assembly is loaded into the CLR that will perform the Just-in-Time compilation (JIT) that will convert the Intermediate Language code to native machine instructions. In a very few words, we can say that the CLR is to .NET the same thing as the JVM is to Java.

Generalities and syntax

A source code written in C# is placed in a file that has ".cs" as extension. Lines written in this file have to be read from left to right, from top to bottom. Every instruction should be ended with a semicolon (;).

C# is case-sensitive.

We can add comments to our code using "//" for a single line, or "/" and "/" for multiple lines.

Variables

A variable is like a box where we store a value. It is a name given to a data value. The content of a variable can vary at any time. In C#, a variable has to be defined with a data type. A variable can be declared and initialized later or it can be declared and initialized at the same time.

// Declaring a variable string message; // Assigning a value the previously declared variable message = "Hello World!!"; // Declaring and initializing a variable string message = "Hello World!!";

Data Types

Because C# is a strongly typed language, we are required to inform the compiler about which data type we want to use with every variable we declare. A data type specifies the type of data that a variable can store.

The information stored in a type can include the following:

The storage space that a variable of the type requires

The maximum and minimum values that it can represent

The members (methods, fields, events, and so on) that it contains

The base type it inherits from

The location where the memory for variables will be allocated at run time

The kinds of operations that are permitted

The compiler uses type information to make sure that all operations that are performed in our code are type safe.

// Declaring a string string stringVar = "Hello World!!"; // Declaring a integer int intVar = 100; // Declaring a float float floatVar = 10.2f; // Declaring a character char charVar = 'A'; // Declaring a boolean bool boolVar = true;

Value Type and Reference Type

In C#, data types are categorized based on how they store their value in the memory. They could be a value type or a reference type.

Value Type

A data type is a value type if it holds a data value within its own memory space. It means variables of these data types directly contain their values.

The following data types are all of value type:

bool

byte

char

decimal

double

enum

float

int

long

sbyte

short

struct

uint

ulong

ushort

When we pass a value type from one method to another, the system creates a separate copy of that variable in the other method. So if the value is changed in one method, the value in the other method won't be affected.

Reference Type

A data type is a reference type if it stores the memory address where the value is being stored. In other words, a reference type contains a pointer to another memory location that holds the data.

The following data types are of reference type:

String

All arrays, even if their elements are value types

Class

Delegates

When we pass a reference type from one method to another, the system passes the address of the variable. It means that if the value is changed in one method, the value in the other method will also be affected.

Operators

An operator is a symbol that is used to perform operations. Some operators have different meanings based on the data type of the operand.

Condition

In C# programming, there are various types of decision-making statements:

if statement

if-else statement

Nested if statement

if-else-if statement

switch statement

If statements

The if statement contains a boolean expression inside brackets followed by a single or multi-line code block. At runtime, if a boolean expression is evaluated to true, then the code block will be executed.

// if statement if (a > b) { Console.WriteLine("a is greater than b"); } // if-else statement if (a > b) { Console.WriteLine("a is greater than b"); } else { Console.WriteLine("a is either equal to or less than b"); } // if-else-if statement if (a > b) { Console.WriteLine("a is greater than b"); } else if (a < b) { Console.WriteLine("a is less than b"); } else { Console.WriteLine("a is equal ton b"); } // Nested if statement if (a > 0) { if (a <= 100) { Console.WriteLine("a is positive number less than 100"); } else { Console.WriteLine("a is positive number greater than 100"); } }

Switch

The switch statement executes a code block depending upon the resulted value of an expression. It is like the if-else-if statement.

switch (a) { case 10: Console.WriteLine("It is 10"); break; case 20: Console.WriteLine("It is 20"); break; case 30: Console.WriteLine("It is 30"); break; default: Console.WriteLine("Not 10, 20 or 30"); break; }

Loops

A loop gives us the ability to repeat a block of code. In C#, there are four ways to achieve a loop.

While loop

A While loop is used to iterate a part of the program while a condition is true.

int i = 0; while (i < 10) { Console.WriteLine("Value of i: {0}", i); i++; }

Do-While loop

A Do-While loop is like a While loop, except that the block of code will be executed at least once because the loop executes the block of code first and then checks the condition.

int i = 0; do { Console.WriteLine("Value of i: {0}", i); i++; } while (i < 10);

For loop

A For loop executes a block of statements repeatedly until the specified condition returns false.

for (int i = 0; i < 10; i++) { Console.WriteLine("Value of i: {0}", i); }

Foreach loop

A Foreach statement provides a way to iterate through the elements of an array or any enumerable collection.

int[] numbers = { 4, 5, 6, 1, 2, 3, -2, -1, 0 }; foreach (int i in numbers) { System.Console.Write("{0} ", i); }

Arrays

In C#, an array is a group of similar types of elements that have contiguous memory location. An array is a special type of data type which can store a fixed number of values sequentially using special syntax. Array index starts from 0.

Like a variable, an array can be declared and initialized later or it can be declared and initialized at the same time.

// Declaring an array that contains strings string[] names; // Instantiating the array and defining its size string[] names = new string[2]; // Storing a value at index 0 names[0] = "John Doe"; // Displaying the value stored at index 0 Console.WriteLine(intArray[0]);

Collections

In C#, a collection represents a group of objects. Unlike an array, a collection doesn't have a fixed size. There are several types of collections.

ArrayList

An ArrayList stores objects of any type like an array.

// Declaring ArrayList ArrayList arrayList = new ArrayList(); // Adding elements arrayList.Add(1); arrayList.Add("Two"); // Add an element at a specific index arrayList.Insert(1, "Second Item"); // Removing element at a specific index arrayList.RemoveAt(1);

SortedList

A SortedList stores key and value pairs. It automatically arranges elements in ascending order of key by default.

// Declaring SortedList SortedList sortedList = new SortedList(); // Adding elements sortedList.Add(3, "Three"); sortedList.Add(4, "Four"); sortedList.Add(1, "One"); sortedList.Add(5, "Five"); sortedList.Add(2, "Two");

Stack

A Stack stores the values in LIFO style (Last In First Out). It provides a Push() method to add a value and Pop() and Peek() methods to retrieve values.

// Declaring Stack Stack stack = new Stack(); // Adding elements stack.Push("John Doe"); stack.Push(1); stack.Push(2); stack.Push(null); stack.Push(3); // Displaying the top item from the stack Console.WriteLine(stack.Peek()); // Removing and returning the item from the top of the Stack stack.Pop()

Queue

A Queue stores the values in FIFO style (First In First Out). It keeps the order in which the values were added. It provides an Enqueue() method to add values and a Dequeue() method to retrieve values from the collection.

// Declaring Queue Queue queue = new Queue(); // Adding elements queue.Enqueue(3); queue.Enqueue(2); queue.Enqueue(1); // Displaying the first item of the Queue Console.WriteLine(queue.Peek()); // Removing and returning the item from the beginning of the queue queue.Dequeue();

HashTable

A HashTable stores key and value pairs. It retrieves the values by comparing the hash value of the keys.

// Declaring Hashtable Hashtable hashtable = new Hashtable(); // Adding elements hashtable.Add(1, "One"); hashtable.Add(2, "Two"); hashtable.Add(3, "Three"); hashtable.Add("Fr", "Four"); // Accessing element string str = (string)hashtable[2]; // Removing element hashtable.Remove(3);

Tuples

A tuple is an ordered immutable sequence, fixed-size of heterogeneous objects. Tuples allow to return multiple values from a method.

// Declaring a tuple var numbers = ("One", "Two", "Three", "Four", "Five"); // Declaring another tuple (string, string, int) person = ("John", "Doe", 30); // Declaring another tuple and accessing values. var person = (firstName: "John", lastName: "Doe", Age: 30); person.firstName; We can also use a tuple as a return type. (int Val1, int Val2) Values() { int val1 = 1; int val2 = 2; return (val1, val2); } var values = GetValues();

Classes

A class is like a blueprint. It is a template from which objects are created. In an object-oriented programming language like C#, an object is like in the real world: it has properties and functionalities. So, a class defines the kinds of data and the functionalities that an object will have.

Access modifiers

Access modifiers are applied to the declaration of the class, methods, properties, fields and other members. They define the accessibility of the class and its members. There are four access modifiers:

public - allows a class to expose its member variables and member functions to other functions and objects

private - allows a class to hide its member variables and member functions from other functions and objects

protected - allows a child class to access the member variables and member functions of its base class

internal - allows a class to expose its member variables and member functions to other functions and objects in the current assembly

Fields

A field is a class level variable that can hold a value.

Properties

A property allows us to control the accessibility of a class variable. It encapsulates a private field and provides a level of abstraction allowing us to change a field while not affecting the external way they are accessed by the things that use our class.

Constructor

A class constructor is a special member function that is executed whenever a new object of that class is created. A constructor has exactly the same name as the class and it does not have any return type.

Methods

A method is a group of statements that perform a task. A method is basically written like so:

<Access Modifier <Return Type> <Method Name>(Parameter List) { Method Body }

Namespaces

A namespace is a container for a set of related classes. A class name declared in one namespace does not conflict with the same class name declared in another.

Example

Let's put what we saw together to create a simple class:

// Namespace namespace MyNamespace { // Declaring the class - access modifier, class keyword, class name public class MyClass { // Fields - access modifier, type, field name public string field = string.Empty; // Property private int propertyVar; // Property accessors public int Property { get { return propertyVar; } set { propertyVar = value; } } // Constructor public MyClass() { } // Method - acces modifier, return type, method name, parameters public void MyMethod(int parameter1, string parameter2) { Console.WriteLine("First Parameter {0}, second parameter {1}", parameter1, parameter2); } // Method - acces modifier, return type, method name, parameters public int MyMethod(int parameter1, int parameter2) { return parameter1 + parameter2; } } }

Interfaces

An interface is like a contract. Every class that inherits from a specific interface has to implement what is defined in the interface. An interface only contains the declaration of the methods and the properties that a class has to implement.

// Declaring the interface interface MyInterface { void MyMethod(string message); } // Implementing the interface class MyClass : MyInterface { public void MyMethod(string message) { Console.WriteLine(message); } }

An interface can also contain properties.

interface MyInterface { string Property { get; set; } void MyMethod(string message); } class MyClass : MyInterface { private string property; public string Property { get { return name; } set { name = value; } } public void MyMethod(string message) { Console.WriteLine(message); } }

Structs

A struct is mostly like a class, but while a class is a reference type, a struct is a value type data type. Unlike a class, it does not support inheritance and can't have a default constructor.

We can consider defining a struct instead of a class if instances of the type are small and commonly short-lived or are commonly embedded in other objects. The general rule to follow is that structs should be small, simple collections of related properties, that are immutable once created.

struct Point { private int x, y; public int XPoint { get { return x; } set { x = value; } } public int YPoint { get { return y; } set { y = value; } } public Point(int p1, int p2) { x = p1; y = p2; } }

Enums

An enum is a value type data type. It is used to declare a list of named integral constants that may be assigned to a variable. An enum is used to give a name to each constant so that the constant integer can be referred using its name.

enum Days { Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday } Console.WriteLine(Days.Tuesday); Console.WriteLine((int)Days.Friday);

Delegates

In C#, a delegate is like a pointer to a function. It is a reference type data type and it holds the reference to a method. When we instantiate a delegate, we can associate its instance with any method with a compatible signature and return type. Delegates are used for implementing events and callback methods.

// Declaring the delegate delegate int Calculator(int n); class Program { static int number = 1; public static int add(int n) { number = number + n; return number; } public static int mul(int n) { number = number * n; return number; } public static int getNumber() { return number; } public static void Main(string[] args) { // Instantiating the delegate Calculator c1 = new Calculator(add); // Instantiating the delegate Calculator c2 = new Calculator(mul); // Calling method using delegate c1(20); // Calling method using delegate c2(3); } }

Anonymous functions and Lambdas

An anonymous function is a type of function that doesn't have a name.

In C#, there are two types of anonymous functions:

Lambda expressions

Anonymous methods

Lambdas Expressions

A lambda expression is an anonymous function that we can use to create delegates. We can use a lambda expression to create a local function that can be passed as an argument.

class Program { delegate int Square(int num); static void Main(string[] args) { Square getSquare = x => x * x; int a = getSquare(5); Console.WriteLine(a); } }

Anonymous Methods

An anonymous method is quite like a lambda expression but allows us to omit the parameter list.

class Program { public delegate void AnonymousFunction(); static void Main(string[] args) { AnonymousFunction myFunction = delegate() { Console.WriteLine("This is an anonymous function"); }; myFunction(); } }

Generics

Generics allow us to define a class with placeholders for the type of its fields, methods or parameters. The compiler will replace these placeholders with the specified type at compile time. Generics increase code reusability.

// Declaring a generic class class GenericClass<T> { // Declaring a generic field private T genericField; // Declaring a generifc property public T genericProperty { get; set; } // Constructor public GenericClass(T value) { genericField = value; } // Declaring a generic method public T genericMethod(T genericParameter) { Console.WriteLine("Parameter type: {0}, value: {1}", typeof(T).ToString(),genericParameter); Console.WriteLine("Return type: {0}, value: {1}", typeof(T).ToString(), genericField); return genericField; } } class Program { static void Main(string[] args) { // Using the generic class GenericClass<int> genericClass = new GenericClass<int>(10); } }

We can use constraints to specify which type of placeholder is allowed with a generic class.

// Declaring a generic class specifying that T must be a reference type. class GenericClass<T> where T: class { ... }

Generic collections

We mentioned collections before. In C#, we can also have generic collections.

List - contains elements of specified type

Dictionary - contains key-value pairs

SortedList - stores key and value pairs in an ordered manner

Hashset - contains non-duplicate elements

Queue - a Queue containing elements of specified type

Stack - a Stack containing elements of specified type

Polymorphism

In C#, polymorphism can be used in different manners. There are two types of polymorphism in C#: compile time polymorphism and runtime polymorphism. Compile time polymorphism, also known as static binding or early binding, is achieved by method overloading and operator overloading. Runtime polymorphism, also known as dynamic binding or late binding, is achieved by method overriding.

Method overloading

It allows us to have the same method multiple times but with different parameters or return type.

public class Program { public int add(int a, int b) { return a + b; } public int add(int a, int b, int c) { return a + b + c; } public float add(float a, float b) { return a + b; } }

Method overriding

It allows a class to override a method that is inherited from a base class. We need to use the keyword "virtual" in front of the method in the base class to allow a derived class to override it.

public class Animal { public virtual void play() { Console.WriteLine("Playing"); } } public class Cat : Animal { public override void play() { Console.WriteLine("Playing like a cat"); } }

Abstract classes

An abstract class is a class that cannot be instantiated. It can contain concrete or abstract methods. An abstract method is a method that has no body and it must be implemented by the derived class.

public abstract class AbstractClass { public abstract void AbstractMethod(); public void Method() { Console.WriteLine("This is a method"); } } public class ConreteClass : AbstractClass { public override void AbstractMethod() { Console.WriteLine("Abstract method implementation"); } }

Attributes

An attribute is a declarative tag that is used to send information to runtime about the behavior of various elements like classes, methods, structures, enumerators or assemblies. Attributes are used to add metadata, such as compiler instruction or other information to a program.

Attributes are generally applied physically in front of type and type member declarations. They're declared with square brackets, "[" and "]", surrounding the attribute. In the following example, we use the "Obsolete" attribute which is a pre-defined attribute in the .NET Framework.

class Program { static void Main() { Test(); } [Obsolete("Test method is obsolete.", true)] static void Test() { } }

When we try to compile the program, the compiler generates an error.

Conclusion

Through this article we had an overview of the C# programming language and how we can use it. It was more like a theoretical article more than a practical article. Nevertheless, we now have the tools to dig a little deeper and to use C#.

One last word

If you like this article, you can consider supporting and helping me on Patreon! It would be awesome! Otherwise, you can find my other posts on Medium and Tumblr. You will also know more about myself on my personal website. Until next time, happy headache!

#programming #development #c #coding #code

0 notes

myquestionbank · 8 years ago

Text

C++ programming questions and answers

Vector vs. deques. Vectors are used to store contiguous elements like an array. However, unlike arrays, vectors can be resized Dequeues, are double ended queues that store elements in a linear order. They allow elements to be accessed at any position. Vector vs. deques. – Vector supports dynamically expandable array. – Deque is double ended queue. Deque elements can be accessed from both the ends…

View On WordPress

0 notes

iyarpage · 8 years ago

Text

Swift Algorithm Club: Minimum Spanning Tree with Prim’s Algorithm

The Swift Algorithm Club is an open source project on implementing data structures and algorithms in Swift.

Every month, Kelvin Lau, Ross O’Brien and I feature a cool data structure or algorithm from the club in a tutorial on this site. If you want to learn more about algorithms and data structures, follow along with us!

In this tutorial you will learn to implement a Swift minimum spanning tree, specifically using prim’s algorithm.

Prim’s algorithm was first implemented for the Swift Algorithm Club by Xiang Xin (thank you!), and has been presented here for tutorial format.

Note: If you have been follow along our SAC article series, last time you saw how to create a heap and priority queue. You will now use a priority queue to implement Prim’s algorithm.

Introduction

Prim’s algorithm was first discovered by a mathematician named Vojtěch Jarník, and later again by Robert Prim. This algorithm is also known as a greedy algorithm.

A greedy algorithm is used to find optimal solutions. It constructs a solution step by step, where at every stage it picks the most optimal path.

Prim’s algorithm constructs a minimum spanning tree. A minimum spanning tree is formed by a subset of connected undirected weighted edges, that connect all vertices together without forming a cycle. Also it has the minimum possible total edge weight. For example you might want to find the cheapest way to layout your water pipes effectively, to cut cost.

In Prim’s algorithm you create a minimum spanning tree by picking edges one at a time. It’s a greedy algorithm because every time you pick an edge, you always pick the smallest weighted edge that connects a pair of vertices.

For other applications of greedy algorithm check out this link by UT Dallas.

Getting Started

Before you start implementing prim’s algorithm, there are 6 steps to consider when performing it:

Let’s go through a simple example. Imagine the network graph below. It could represent any type of network! Let’s open up our imagination here!

Imagine a network of airports represented by the vertices. The weighted edges represents the cost and route for an airplane to fly from one airport to the next. RW Airways may want to adopt prim’s algorithm to get a minimum spanning tree giving them the most cost effective routes to fly between airports!

By the end of this tutorial you will save lots of dollar bills!

Working through an example

First, start by picking any vertex. Let’s say vertex 2.

Choose the shortest edge from this vertex. This vertex has edges with weights { 6, 5, 3 }.

You pick edge 3 since it’s the smallest, which routes to vertex 5.

You have now visited vertices { 2, 5 }.

Choose the shortest edge from these vertices. The next nearest edges are { 6, 5, 6, 6 }. You pick edge 5 since it’s the smallest, which routes to vertex 3.

Notice that edge 6 between vertex 5 and vertex 3 can be removed since these vertices have already been visited.

You now have visited vertices { 2, 3, 5 } .

Choose the shortest edge from these vertices. The next nearest edges are { 6, 1, 5, 4, 6 } . You pick edge 1 since it’s the smallest, which routes to vertex 1.

Notice that edge 6 between vertex 2 and vertex 1 can be removed since these vertices have already been visited.

You now have visited vertices { 2, 3, 5, 1 }.

Choose the shortest edge from these vertices. The next nearest edges are { 5, 5, 4, 6 } . You pick edge 4 since it’s the smallest, which routes to vertex 6.

Notice that edge 6 between vertex 5 and vertex 6 can be removed since these vertices have already been visited.

Finally you now have visited vertices {2, 5, 3, 1, 6 }.

Choose the shortest edge from these vertices. The next nearest edges are { 5, 5, 2 } You pick edge 2 since it’s the smallest, which routes to vertex 4 .

Notice that the rest of the edges { 5, 5 } connected to vertex 4 from vertex 1 and vertex 3 can be removed since these vertices have been visited.

RW Airways can now redirect their airplanes to fly these routes to cut cost! This means more profit! Are you starting to see the pattern here? Let’s move on to the implementation!

Implementation

Download the starter playground. Open the Project Navigator to see the list of files, and familiarize yourself with the Sources folder:

You will be using an adjacency list to create your graph network.

You will be using a Priority Queue (implemented using a Heap). This data structure will store edges adjacent to vertices you visit. The root of this heap will always have the smallest weighted edge.

Again, if you want more information on how these classes work, check out our Swift heap and priority queue tutorial.

Setup

Navigate to the root Playground and add the following code:

class Prim<T: Hashable> { // 1 typealias Graph = AdjacencyList<T> // 2 var priorityQueue = PriorityQueue<(vertex: Vertex<T>, weight: Double, parent: Vertex<T>?)>( sort: { $0.weight < $1.weight }) // 3 }

You have declared a class named Prim, you want this algorithm to be generic, so it can find the minimum spanning tree of any type, given that it's Hashable.

This class will use the AdjacencyList to hold your graphs.

You define a minimum priorityQueue, where it holds the current vertex, the weight of the edge between the vertices, and the parent vertex.

Next add the following after priorityQueue:

func produceMinimumSpanningTree(graph: Graph) -> (cost: Double, mst: Graph) { // 1 var cost = 0.0 // 2 let mst = Graph() // 3 var visited = Set<Vertex<T>>() // 4 return (cost: cost, mst: mst) // 5 }

Define a function produceMinimumSpanningTree(_:), that takes a Graph network, and returns the minimum total cost of all edges, and the minimum spanning tree.

Define the cost variable, used to aggregate all weights.

Create a graph to construct your minimum spanning tree.

Create a Set to store all vertices visited.

Once prim's algorithm is complete, return the results.

Initiate the algorithm

Add the following after the visited variable:

guard let start = graph.getAllVertices().first else { // 1 return (cost: cost, mst: mst) } priorityQueue.enqueue((vertex: start, weight: 0.0, parent: nil)) //2

Start by picking any vertex. In this case, we grab all vertices from the adjacency list, and pick the first one.

Add the start vertex into the priorityQueue. In this case since you haven't visit any other vertex, the edge weight is zero, and the parent is nil.

Step by Step and grab the smallest!

Next add the following code right after:

while let head = priorityQueue.dequeue() { // 1 let vertex = head.vertex if visited.contains(vertex) { // 2 continue } visited.insert(vertex) // 3 cost += head.weight // 4 if let prev = head.parent { // 5 mst.add(.undirected, from: prev, to: vertex, weight: head.weight) } if let neighbours = graph.edges(from: vertex) { // 6 for neighbour in neighbours { // 7 if !visited.contains(neighbour.destination) { // 8 priorityQueue.enqueue((vertex: neighbour.destination, weight: neighbour.weight ?? 0.0, parent: vertex)) } } } }

This is the main part of prim's algorithm where you select the smallest edge every time you visit a vertex. Let's go over how the code works:

Check to see if there is a set of vertices and weight in the priority queue. If the queue is empty, prim's algorithm is complete.

Note: Every time a (current vertex, weight, parent vertex) set is dequeued from the priority queue, you are guaranteed that the weight between two vertices is always the minimum.

Check to see if the current vertex you are visiting has been visited before. If it has been visited, restart the loop, and dequeue the next set of vertices and edge between them.

If it has been yet to visited, add it to the set of visited vertices

Add the weight between the set of vertices to the total cost.

Check to see if the current vertex you are visiting has a parent vertex. If there is, add it to the minimum spanning tree you are constructing.

Now go through all the neighbouring edges from the current vertex, and add it to the queue, as long as the destination vertex has yet to be visited.

That's all there is to it!

Testing it out

Add the following code after Prim class declaration:

var graph = AdjacencyList<Int>() let one = graph.createVertex(data: 1) let two = graph.createVertex(data: 2) let three = graph.createVertex(data: 3) let four = graph.createVertex(data: 4) let five = graph.createVertex(data: 5) let six = graph.createVertex(data: 6) graph.add(.undirected, from: one, to: two, weight: 6) graph.add(.undirected, from: one, to: three, weight: 1) graph.add(.undirected, from: one, to: four, weight: 5) graph.add(.undirected, from: two, to: three, weight: 5) graph.add(.undirected, from: two, to: five, weight: 3) graph.add(.undirected, from: three, to: four, weight: 5) graph.add(.undirected, from: three, to: five, weight: 6) graph.add(.undirected, from: three, to: six, weight: 4) graph.add(.undirected, from: four, to: six, weight: 2) graph.add(.undirected, from: five, to: six, weight: 6) let prim = Prim<Int>() let (cost, mst) = prim.produceMinimumSpanningTree(graph: graph) print("cost: \(cost)") print("mst:") print(mst.description)

You should see a string representation of the example below:

Where to go from here?

I hope you enjoyed this tutorial on prim's algorithm! Here is a playground with the above code. You can also find the original implementation and further discussion on the repo for prim's algorithm.

This was just one of the many algorithms in the Swift Algorithm Club repository. If you're interested in more, check out the repo. It's in your best interest to know about algorithms and data structures - they're solutions to many real-world problems, and are frequently asked as interview questions. Plus it's fun!

Stay tuned for many more tutorials from the Swift Algorithm club in the future. In the meantime, if you have any questions on implementing trees in Swift, please join the forum discussion below.

Note: The Swift Algorithm Club is always looking for more contributors. If you've got an interesting data structure, algorithm, or even an interview question to share, don't hesitate to contribute! To learn more about the contribution process, check out our Join the Swift Algorithm Club article.

The post Swift Algorithm Club: Minimum Spanning Tree with Prim’s Algorithm appeared first on Ray Wenderlich.

Swift Algorithm Club: Minimum Spanning Tree with Prim’s Algorithm published first on http://ift.tt/2fA8nUr

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly.

Marking Guide

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

For step 1 you are to implement the simulator’s customer queue and event queue. Implement the customer queue (FIFO queue). It should have a maximum size of 500 records. Each record in the customer queue should contain two doubles and a boolean (i.e. arrival time, tally time and payment method). Your customer queue should have functions for adding an item (enqueue), removing an item (dequeue), and for testing if the queue is empty. (Note: C++ and Java coders should also add a constructor for initialsing the queue.) FIFO Queue Test your customer queue by declaring an instance of it in the main(). Use a for loop to add 10 records to the queue. Set the arrival time for each record between 1 and 100 using rand() or random(). The other fields can be set to 0 or false. Also, print the arrival times on the screen as you add them. Now use a while loop to remove all the records from the customer queue and print the arrival times on the screen. Is the output correct? Now implement the simulator's event queue (i.e. a priority queue). The event queue’s records should contain an event type (int or enum), event time & tally time (doubles), and payment method (boolean). You can assume the maximum number of events in the event queue is 100. The record with the minimum event time has the highest priority. Test the event queue by declaring an instance of it in the main(). Use the while loop (implemented previously) to remove records from the customer queue and add them to the event queue. Set the event time with the customer's arrival time. Set the other fields to zero. Then implement a while loop in the main() to remove (dequeue) each record from the event queue and print the event time on the screen. Is the output correct? Note: For step-1 (to get the 2 demo marks) you can implement the customer and event queues using any method you like. However, for the final submission, to get full marks, you should ensure all data structures and algorithms are optimised for speed.

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly. Read the full article

0 notes

felord · 6 years ago

Text

CSCI203/CSCI803 ASSIGNMENT 2 Solved

Step-1 (Week-7 demo, 2 marks)

Step-2 (Server array implementation)

Step-3 (Processing in the data)

Step-4 (Optimisation and stats)

Step-5 (Specifications)

Compilation

All programs submitted must compile and run on banshee:

C: gcc ass2.c C++: g++ ass2.cpp Java: javac ass2.java Python: python ass2.py

Programs which do not compile on banshee with the above commands will receive zero marks. It is your responsibility to ensure that your program compiles and runs correctly. Read the full article

0 notes