Data Structures

CSc - 2720

Fall 2018

E-Mail: aahmadzadeh1[-at-]cs[-dot-]gsu[-dot-]eduOffice: 25 Park Place, 645
Grader: picer1[-at-]student.gsu.edu (Pelin Icer)

[CS, 225]

[08:00-08:50 am]

[LH, 415]

[09:30-10:20 am]

[LH, 415]

[11:00-11:50 am]

Student Evaluation of this lab >

LABs

All assignments, as well as their solutions are now publicly available in my repository (click on the blue icon).

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.

LAB XIII: Binary Search Tree (2)

Due: Nov 28, 2018 by 11:30 pm.

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]

Follow the steps below:

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]

follow the pseudo code below:

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.

LAB XII: Binary Search Tree (1)

Due: Not for now.

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:
  1. A single node r, the root
  2. A possibly non-empty set that is a binary tree, called left subtree of r.
  3. A possibly non-empty set that is a binary tree, called right subtree of 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:

https://www.cs.usfca.edu/~galles/visualization/BST.html
https://visualgo.net/bn/bst [On the right]

LAB XI: Queues (2)

Due: Nov 07, 2018 by 11:30 pm.

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 PriorityQueue<E>

extends AbstractQueue<E>

implements 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.

LAB X: Queues (1)

Due: Not graded (project + all we did today)

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

LAB IX: Array Lists (cont'd)

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

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 (LinkedList) 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()

LAB VIII: Array Lists (ours)

Due: not graded

Today's plan:

Quick review of previous lab:
- What did we learn about LinkedList collections?
- When should we use them instead of Object[] or ArrayLists?
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.

LAB VII: Linked Lists (ours) II

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

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! :)

LAB VI: Linked Lists (ours)

Preparation lab.

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.

We will be doing something along this video.

If you are more of a casual person, and learn better when talking to someone.

Interactive Visualization

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, to do so.)
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: - IFunctions for the class Functions - ISortMethods for SortMethods - and now, IList 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

LAB V: Sorting

Due: Sep 26, 2018 by 11:30 pm.

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

After you finished each method and verified the output, you need to answer one question.

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

If you have implemented all three sort methods, run 2 experiments.

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!

LAB IV: Getting Ready for Sorting

Code + solutions to the warm-ups:

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:

Clone (Let your class implement Clonable) {Example]
Copy (Add a copy constructor to your class.) [Example]
Clone vs Copy. See this.

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

LAB III: Revision (Recursion)

Due: Sep 11, 2018, by 11:30 pm.

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.

> A recursive animation <

Learn it like a computer scientist does.

Professor Brailsford - University of Nottingham

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 results

Note:

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)

Some good readings and practice resources:
- 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.

(This last bullet point is in fact the main reason that you are reviewing this concept in this lab.)

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]:

The method below searches for 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.

@Overridepublic 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]

Can you implement the same method but this time using loops? There is a method called searchByDividing in the interface IFunctions. Start by implementing that method. It dost the same thing as searchByDividingRec, but iteratively.

Problem:

Recursive in Action

You have to stand in a line to get into a night club. You really want to know how many people are in the line but since the music is crazy loud, people can only hear the ones right after and before them. How do you do it?
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 45
Adding spaces, although is not hard, is not required.

LAB II: Revision (Basics)

Due: Sep 4, 2018, by 11:30 pm.

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 I: Intro

What to submit: Nothing for now.

Today's plan:

Brief talk about this lab.
Start with the document on the right. Grade yourself.
Create a Bitbucket account. [Remember the user-name and password]
Pull the first project from here.
Start coding.

A you_kidding_me List

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.]

Google Sites

Report abuse