# Data Structures

### CSc - 2720

Fall 2018

**E-Mail:**

`aahmadzadeh1[-at-]cs[-dot-]gsu[-dot-]edu`

**Office:**

`25 Park Place, 645`

**Grader:**

`picer1[-at-]student.gsu.edu (`

*Pelin Icer)*

**[**CS, 225]

`[LH, 415]`

`[LH, 415]`

### Student Evaluation of this lab >

# LABs

### Final notes:

**When will the grading of the labs be completed?**- All the labs are already graded by your grader, Pelin Icer.

**For which labs should I have received any grades?**- All the labs that there is a submission folder created for in iCollege. In total, 7 labs (2,3,5,7,9,11,13), plus the bonus lab. The rest of the labs were preparation labs only and you did not even submit them. I don't know why some of you are looking for grades for those labs.

**How will my total lab grade be calculated?**- Without bonus lab: sum(7_labs) / 7
- With bonus lab: (sum(7_labs) - min_lab + bonus_lab) / 7

**What if I had an excused absence approved by Azim?**- Without the bonus lab: sum(6_labs) / 6
- With the bonus lab: (sum(6_labs) + bonus_lab) / 7

**What if I think there is a mistake in one of my grades?**- Look at the calendar, first. If it's after midnight of Dec 9th, then it's too late!
- If it is not too late, please write a clear e-mail (possibly with evidence that proves your point) to Pelin Icer. She has been trying very hard to make sure you all get fair grades.
- I think we all can agree that context-less e-mails (e.g., "
*I got zero for lab 3, I don't know why!?*") should be ignored! If you care about your situation, you need to elaborate on your case.

### Today's plan:

You know all you need. Do as follows:

- Sign the sheet. Pull the project.
- In the class Main, finish section 1, which is just a review of our last lab.
- Continue the remaining sections.

Today, we will implement the methods on the right (NEW).

`DLine getRoot();`

`int getNumberOfNodes();`

`void insert(DLine dl);`

`int `**getTreeLevel**(DLine dl); //NEW

`void `**traverseInorder**(); //NEW

`void `**traversePreorder**(); //NEW

`void `**traversePostorder**(); //NEW

`void `**traverseLevelOrder**(); //NEW

`DLine `**find**(DLine dl, int len); //NEW

Help: [`getTreeLevel`

]

`Algorithm:`

`1. call this function (recursively) on the left child of dl.`

`2. call this function on the right child of dl.`

`3. return the maximum of what was returned on the last two lines.`

Help: [`traverseLevelOrder`

]

`queue.add(root)`

`while (queue is not empty):`

` last = q.dequeue()`

` print(last)`

` if(last has left):`

` q.add(left of last)`

` if(last has right):`

` q.add(right of last)`

For, `traverseInorder()`

, `traversePreorder()`

, and `traversePostorder()`

, see the above examples.

### Tree:

A general tree *T* is a set of one or more nodes such that *T* is partitioned into disjoint subsets:

- A single node
*r*, the root - Sets that are trees, called
*subtrees*of*r*

### Binary Tree:

A binary tree is a set *T* of nodes such that either:

*T*is empty, or*T*is partitioned into 3 disjoint subsets:- A single node r, the root
- A possibly non-empty set that is a binary tree, called
of**left subtree***r.* - A possibly non-empty set that is a binary tree, called
of**right subtree***r.*

### Binary Search Tree:

A binary search tree is a binary tree *T* with the following conditions for each node *r*:

`r.value`

is greater than or equal to all values in its*left subtree*.`r.value`

is less than all values in its right*subtree*.

Most of the methods in the Binary Search Tree class are recursive.

`Insertion`

, `Deletion`

, `Traversal`

, `Display`

, etc.

To get some intuition about this, you can play with some interactive visualizations:

### Today's plan:

- A quick review of Lab X.
- Warm up steps in the main class.
- Starting with the new methods.

Previously, we implemented the following methods together:

`void enqueue(DLine dl);`

`DLine dequeue();`

`DLine peek();`

`int size();`

Now, we want to continue with:

`void enqueueAll(IDQueue dq);`

`void transfer(IDQueue dq);`

`DLine last();`

`void empty();`

### An Experiment:

At the end of this assignment, there is a simple experiment waiting for you. We would like to try other implementations of queues as well. Namely, LinkedList and PriorityQueue.

`public class `**LinkedList**<E>

`extends AbstractSequentialList<E>`

`implements List<E>, Deque<E>, Cloneable, Serializable`

`public class `**DQueue**<E>

`implements IDQueue<E>`

Let's add 100,000 instances of `DLine`

and check which collection can deal with this task faster.

### Today's plan:

- Let's talk about Queues and their applications.
- Review the theory and turn it into code right away.
- We will pick up from where we leave today, next week.

A **queue** is a particular kind of collection in which the entities are kept in order.

The main operations are:

*enqueue*: addition of entities to the rear terminal position (tail),- dequeue: removal of entities from the front terminal position (head).

We use our favorite objects (DLines) as the nodes of this data structure. Then, similar to what we did for implementation of our own LinkedList (DLList), we start working on the queue methods one by one.

On the right, you see a visualization of the main operations of a queue: enqueue and dequeue.

See: Queue in Java 10

### First,

Sign the attendance sheet, please. Then, pull the project.

### Today's plan:

- Let's quickly review what we have implemented before (
`DAList`

). - Think about the idea behind the remaining methods.
- You know all you need. Start working on the project.

There are only 4 methods to implement. It shouldn't be very time consuming.After you are done, take a moment and try to review the differences between

**DLList**(

`LinkedLis`

t) and **DAList**(

`ArrayList`

).`int size();`

`DLine get(int index);`

`void set(DLine dl, int index);`

`void add(DLine dl);`

**int addAfter(DLine dl, int index); **//NEW

**void removeAt(int index); **//NEW** **

**void removeAll(int from, int to); **//NEW

**public void removeAll(); **//NEW

`void ensureCapacity();`

`void resize();`

`int size()`

### Today's plan:

- Quick review of previous lab:
- What did we learn about
`LinkedList`

collections? - When should we use them instead of
`Object[]`

or`ArrayList`

s?

- What did we learn about
- Theory of ArrayLists. (Object[], size, capacity)
- Starting coding together to implement
`DALine`

(our version of`ArrayList`

) together.

## BONUS LAB I

Due: Oct 18, 2018 by 11:30 pm.

> Postponed from 16th to 18th.**This is optional. Why should I do this?**

- Your grade for this project could be replaced with your lowest grade in any of the labs or even with the one that you missed or you are going to miss in future!
- Tbh, this is almost as simple as redoing Lab VII, just with different names for classes and fields. But with a lot more freedom in changing stuff as much as you want.
- If you were looking for a chance to implement a project from scratch but you didn't have time or motivation for it, today is your day. Do this and improve your programming skill, as well as your final grade.

**Task:**

Develop a Java project that can be used to keep track of different routs of a metro system and its stations. You need to have the following components:

`class`

**Station**`class`

**Route**`Interface`

**IRoute**`class`

**Main**

### Station:

... is an object representing a metro station with one or more letters indicating its **name**. For example "A", "BA", "ZTR", etc. Each station has only one link to its **next** station. (This object should act like a node.) In addition to its name and the link, each station has a number showing its **distance** (in miles) to the next station.

### Route:

Is a collection of the stations, linked together. A route is initially with no stations, but user should be able to add or remove as many as stations as they desire and make a route with them.

The last station of a route is linked to null and its distance to the next station is of course 0.

### Want more info?

The details of the project, as to what methods should be implemented, and what are their arguments and everything else, can be answered with one sentence: "*Follow Lab VII for every small piece of this project.*"

**Note: **The class Route needs a method to display the route. No matter how you do this, two pieces of information must be there:

- Name of each station.
- Distance from the next station.

**A suggestion:** for a route with 3 stations,

`------[AC]----[DF]--------------[KJ]-----`

### Important check list:

**Bottom-up:**Start your project as we practiced before: Create a bunch of empty classes and interfaces, make plans in an interface, let a class implement the interface, implement the methods in that class, and test them on at a time, in the main class.**Naming:**Feel free to name class fields and methods whatever you want. Just make sure those names make sense. Remember, good naming makes thinking easier. (*Points will be deducted for names that are copied from previous labs but make no sense in this new context. This simply means the author of the code does not understand what is going on.*)**A complete Main:**Your project will be graded for each of the methods that you get to test in the main class, and not only for your implementation. The tests must be there, and they should test all possible scenarios. Again, see the class`Main`

in Lab VII for that.**Explanation:**You have seen enough examples of comments (in green) and javadocs (in blue) in my implementations. Now it is your turn.*Without at least the same amount of comments, you may lose a lot of points.*

### Today's plan:

Remember what we practiced in Lab VI? Now, use that to implement the following methods for the objects of type `DLList`

.

`add(DLine dl);`

`add(DLine dl, int index);`

**Hint:** Make sure the value of `index`

is valid:

- Is
`index`

positive? - Is
`index`

within the size of the list?

**Hint:** Don't forget to update the size of the list.

`append(IList<DLine> ls);`

**HowTo:** This is very similar to `add(DLine dl)`

, except that here instead of adding a single node to the end of a list, we add the first element of `ls`

to the end of the list.

**Hint:** Don't forget to update the size of the list after append.

`append(IList<DLine> ls, int index);`

**HowTo:** This is very similar to `add(DLine dl, int index)`

. Suppose you want to append `d`

to `ls`

at position 3. First, make the first element of `ls`

be the next of the node at position 3. But then, instead of making the first element point to the node at position 3+1, let the last element of ls point to that node.

**Hint:** Don't forget to update the size.

`remove(int index);`

**Hint:** You don't need to do anything for erasing a node. Just rearrange the links so that it does not belong to the list anymore.

**Hint: **Don't forget to ... ? You said it.

`empty();`

**HowTo:** Be creative. This can be done by a very simple change. Just let the head point to null;

**Hint: **There is something else that you should not forget! :)

**This lab is very important. **We will start talking about Data Structures.

If you have time, watch one of these short videos and let your brain get ready for digesting this.

Wanna see it in action? Click on the button above, and play with it.

### Today's plan

- What are Lists? (nodes, linked nodes, and lists)
- Modify the class
**DLine**to become a**node**. - List what methods are expected for our LinkedList (called
`DLList`

) to have. (Use an interface,`IList`

, - Implement The methods and test them, one by one.

[img: source]

# 0

### Setting the Goals

To implement a List we need 2 classes; a `Node`

class, and a `List`

class.

On the right, you can see the general structure of those classes.

**Note:** Notice the self-reference (recursive) structure in class `Node`

.

`class `**Node**{

` Object data;`

` Node `**next**;

`}`

`class `**List**{

` int n;`

` Node `**head**;

` void `**add**(int i){...}

` void `**remove**(int i){...}

` void `**get**(int i){...}

`}`

# 1

### DLine as a Node

Let's start by expanding our `DLine`

class to behave like a Node.

- Add the extra field:
`DLine next;`

- Modify the constructors to act appropriately about the new field.
- It is better to keep this field,
`private`

. So we would need a getter for that.

As the result, something like the object on the right will be formed.

# 2

### Plan in IList

Declare what our List class must have, in the form of an **interface**, called `IList`

.

`void add(DLine dl);`

for adding a`DLine`

to the end of the list.`int add(DLine dl, int i);`

for adding a`DLine`

at a specific position.`DLine get(int i);`

getting the`i`

-th element of the list.`int remove(int i);`

for removing the`DLine`

at the`i`

-th position.`void empty();`

for making the list empty.`int size();`

for getting the size of the list, i.e., the number of elements.

**A Side note:**

perhaps this is a good time for you to recall how we have been using Interfaces in our projects. We usually keep the blue-print (the raw idea) of our plan in an interface. Interface is NOT a place for "HOW", but a place for "WHAT".

Do you remember: -

**I**Functions

for the class `Functions`

- **I**SortMethods

for `SortMethods`

- and now, **I**List

for `DLList`

.* "

**I**" as a naming convention indicates that a file contains an interface.

# 3

### Implement the plan

I suggest you implement the methods in the following order. This may make more sense, but if you want to do it in different order, make sure you implement `get()`

before adds and remove.

1. `size`

, 2. `get()`

, 3.`add(int)`

, 4..`add(DLine, int)`

, 5.`remove`

, and 6)`empty`

### Today,

we want to implement three simple sort algorithms by following their pseudo code.

The goal is to sort the following set of lines in the **ascending** order:

**myList:** < --------------------|----------|-----|---------------|---|- >

**sortedList:** < -|---|-----|----------|---------------|-------------------- >

### Start with...

Start with the preparation section in the class `Main`

. By following those steps you should be able to create 2 lists and display them.

# 1

Read the instruction for each section in `Main`

, and implement the corresponding sort method.

Below, you can see all the three pseudo codes. (You can also see them in the javadoc of those methods inside your IDE.)

**Sort_1**

` i <-- 1`

` `**while** i < length(A)

` x <-- A[i]`

` j <-- i - 1`

` `**while** j >= 0 and A[j] > x

` A[j+1] <-- A[j]`

` j <-- j - 1`

` end while`

` A[j+1] <-- x`

` i <-- i + 1`

` end while`

**Sort_2**

` n <-- length(A)`

` `**while** n > 0

` nn <-- 0`

` `**for** i = 1 to n-1 inclusive do

` `**if** A[i-1] > A[i] then

` `**swap**(A[i-1], A[i])

` nn <-- i`

` end if`

` end for`

` n <-- nn`

**Sort_3**

` n <-- length(A)`

` `**for** i = 0 to n-1 exclusive do

` min <-- i`

` `**for** j = i+1 to n exclusive do

` `**if** A[j] < A[min]

` min <-- j`

` end if`

` end for `

` if min != i`

` `**swap**(A[i], A[min])

# 2

### What is the name of the sort method you just implemented?

**Help:** You can display your `List<DLine>`

, right? So, you should be able to display the list as it is being sorted (at each iteration). Looking at the results and recalling your lecture notes might help you to tell what sort method you have implemented.

# 3

### Experiments:

- Create a list of DLines following the set
`{1000, 999, ..., 1`

}. Run each of your sort methods and report the execution time. Which one is fastest? - Create another list following the set
`{1, 2, ..., 1000}`

. Report the execution time for each method. Which one is fastest now?

**What is your conclusion? **

(Don't forget to answer the questions. Those are for points!)

### Hint 1.

After each section, make sure your inputs are not already sorted!

`sortedList.`**clear**();

`sortedList.`**addAll**(myList);

### Hint 2.

Before you start the experiments, make sure you have commented out all calls of `displayList()`

inside your sort methods. Otherwise, you will see every step of a list of 1000 elements being sorted!

### Today's plan:

- Sign the sheet. Pull the project.
- Let me walk you through different classes and interfaces.
- We want to brush up on our programming skills with Lists, classes and interfaces.
- At the end of this lab, you should be all set to implement one sort method.
- We will continue this subject in the next lab.

**Basic API of List:**

`List<Object> myList = new LinkedList<>();`

- Get the size of the list:
`myList.size(i)`

- Get the i-th element of the list:
`myList.get(i)`

- Set an object as the i-th element of the list:
`myList.set(i)`

(copy over) - Append an object to the end of a list:
`myList.add(myObject);`

- Append an object to the list, after the i-th element of a list:
`myList.add(i, myObject);`

**An Important Lesson:**

Copy an object, or a reference to an object?

`Object ob1 = new Object();`

`Object ob2 = ob1;`

`//Now any changes to ob1 will affect ob2 as well!!!`

This is specially an issue when we are dealing with lists of objects (not primitive types such as `int, double`

, ...).

Solution:

### Let's understand this:

`int[] A = new int[]{4,3,2,1}`

How can we sort this in the ascending order?

`i ← 1`

**while** i < length(A)

` x ← A[i]`

` j ← i - 1`

` `**while** j >= 0 **and** A[j] > x

` A[j+1] ← A[j]`

` j ← j - 1`

` `**end while**

` A[j+1] ← x`^{[4]}

` i ← i + 1`

**end while**

### Today's plan:

- Sign the attendance sheet and pull the project from bitbucket, as we always do.
- We start working on the first method together.
- Then you continue implementing the rest. (Implementation of the 5th method is given below. Understand that to be able to implement the 6th one.)
- The last method is a fun problem to solve using recursion. It is explained below, but I will also walk you through the problem in the lab.

Learn it like a computer scientist does.

### What is recursion?

- [in Math] occurs when a concept is defined in terms of itself.
- [in Computer Science] occurs when a function needs to call itself to solve a problem.

In other words:

A programming technique that breaks down a complex problem into smaller, manageable pieces.Recursive solutions solve a problem by applying the same algorithm to each piece and then combining the resultsNote:

Any recursive algorithm can be rewritten to use loops instead. The opposite is also true. Any iterative algorithm can be written in terms of recursion only. (here)- https://introcs.cs.princeton.edu/java/23recursion/- [Animation] mathwarehouse.com & blog.penjee.com- https://www.cs.cmu.edu/~adamchik/15-121/lectures/Recursions/recursions.html

### Advantages of recursive methods:

- It could be easy and intuitive to read a recursive algorithm. (Some algorithms are just natural to be recursive.)
- In some known cases, recursive methods run faster compared to their iterative implementation.
- When it comes to search, sort, and fold, you may want to try recursion.
- It is appropriate to be considered when the underlying data structure is defined recursively, such as
`LinkedList`

and`TreeMap`

.

### Disadvantages of recursive methods:

- It could (also) be extremely difficult to understand a recursive algorithm. (Hence, always prone to error.)
- For general purpose tasks, it is almost always slower than the iterative approach.
- It is proven that for any recursive solution, there is an iterative alternative.
- Any system is bounded to a certain stack size. For large number of recursions,
`stackoverflow`

exception is very likely to be thrown.

### Given

**Search By Dividing [Recursive]:**

`x`

in the given array, recursively. The array is assumed to be sorted in ascending order. **Method:**Find the middle of the array (

`middle = (to - from)/2`

). If the array at `middle`

is larger than `x`

, since the array is sorted in ascending order, search only the first half of the array. Otherwise, search only the second half. Repeat (recursively) until `arr[middle]==x`

, and then return `middle`

or `-1`

.`@Override`

`public int `**searchByDividingRec**(long[] arr, int from, int to, long x) {

` if (from > to) {`

` return -1;`

` }`

` int middle = (from + to) / 2;`

` if (arr[middle] == x)`

` return middle;`

` else if (arr[middle] < x)`

` return `**searchByDividingRec**(arr, middle + 1, to, x);

` else {`

` return `**searchByDividingRec**(arr, from, middle - 1, x);

` }`

`}`

### Problem

**Search By Dividing [Iterative]**

**searchByDividing**in the interface

*IFunctions.*Start by implementing that method. It dost the same thing as

**searchByDividingRec**, but iteratively.

### Problem:

**Recursive in Action**

Look at the animation on the right -->

Implement the method

`howManyInLine`

as provided in the interface `IFunctions`

.Below, you see a sample output of this method for a list of 5 elements.

`How many?`

`Me and the guys behind me!`

` Me and the guys behind me!`

` Me and the guys behind me!`

` Me and the guys behind me!`

` Just me!`

` 2`

` 3`

` 4`

`5`

Adding spaces, although is not hard, is not required.

### Today's plan:

- Sign the attendance sheet.
- Pull the code from my repository (the blue icon on the right).
- Make the class
`Function`

implement the interface`IFunctions`

. (This is where everything starts.) - Follow the tasks explained in the class
`Main`

.

[] Read the explanations carefully. This can save you time and points.

**Note:**

- The values your methods return matters. Don't try arbitrary inputs if they are provided for you.

**Meanwhile:**

- See how I am using
**Javadoc**to explain my code to others (to you). I expect you to do the same.

## Lab Rules

Each week is either a preparation or a graded lab.

### Requirements:

- One of the prerequisites for this course is 1302. If you don't feel comfortable with programming in Java, it is high time you reviewed and did practices what you should have learned by now. To have all the students on the same page, I consider the first two labs as a quick revision of Java. It is highly recommended that you use this time to catch up with the expected programming level. The topics of this course (2720) are extremely important and it is not possible to spend time on the basics of Java.

### General points:

**Attendance:**Attendance to both the preparation and the graded labs is a MUST. Otherwise, your code will not be graded.**Deadline:**Submission of each lab must take place before 11:30 pm of the Tuesday after the graded lab. (Fri + Sat + Sun + Mon + Tue)**Late Submission:**There is none! The tasks are designed in such a way that it should not take more than 2 days for students to carry out each of their assignments. The extra 2 days should be considered only as a safety margin for unexpected incidents.**Documentation:**Each class, constructor, and method, MUST have javadoc.**Valid submissions:****Compression:**Compress your entire project and submit the`.zip`

file to iCOllege.**Files:**Extra files such as`.class`

,`.txt`

,`.docx`

,`.pdf`

will be ignored in the process.

### Plagiarism:

*I know that this has rarely been taken seriously in GSU, but in my lab, cheating will not be tolerated whatsoever. * I will do my best to help you in the process of learning the topics and try to keep the difficulty of the tasks in a fair level. In exchange, I expect you to do your best in this course and avoid any short cuts.

Please read the following bullet-points and make sure you follow them carefully.

**No random check:**Student's code will ALWAYS be plagiarism-checked against other students' code as well as online resources.**No team-work:**Team-work with anyone (such as classmates, family members, friends, etc) is NOT allowed and will be considered plagiarism.**All parties:**For any plagiarism case, all parties are equally responsible. (Keep this in mind when a friend kindly asks you to share your code with them.)**Zero-tolerance policy:**There is no second chance. (You will be immediately dismissed from the class and your case will be reported to the authorities for formal follow-ups.**Not familiar with the rules?**Take a look at GSU Student Code of Conduct.**[Rule of thumb:**If not sure about something, it is better to ask rather to try.]