Sit-in Lab 4

Books

Problem Description

Given a list of books represented as a stack (or a pile of books), sort the books based on either one of these three criteria:

1. Sort by Size
2. Sort by Subject
3. Sort by Subject (but for the same Subject, sort by Size) [also called Sort by Size-Subject in the question]

However, the list is not static, it can be changed by adding or removing elements to or from the top of the stack. In this explanation, the input and output will not be discussed. The main problem lies in the sorting algorithm using only stacks (or series of stacks in this case). Adding and removing elements to or from the top of the stacks should be trivial by now, especially when using the Java API command. For those who need to know how to do it, please refer to my previous post about implementation of Stack and Queue.

Idea

From the description in the question, we can see that the range of sizes of the book is from 1 to 5 (inclusive) and the subjects can only be Math (M), Biology (B), or Physics (P). So, the possible combinations of books are:

1M, 2M, 3M, 4M, 5M,

1B, 2B, 3B, 4B, 5B,

1P, 2P, 3P, 4P, 5P.

Intuitively, if we can put each book in its proper BOX, and retrieve from the BOXES, the books in the proper order, we can have the desired sorted order that we want. Having 15 BOXES will then solve the sort by size-subject, but can we do better? What about sort by size or subject?

Using the same idea from sort by size-subject, we can solve sort by size if we use 5 BOXES, one for each size. However, there is the second criteria which is for within books of the same sizes, the order is based on the original ordering. That is to say, the following sequence: 3M – 2P – 1M – 3P – 1B will yield: 1M – 1B – 2P – 3M – 3P (the relative order within size 1 is the original, and similarly with 3). How, then, do we satisfy this criteria? To rephrase the question, what, then, should the data structure for the BOX be?

Looking from the position of the top of the stack (because the pile of books is represented as a stack), we have to preserve the original ordering for each BOX. If you remember from the Stack/Queue Primer article, pushing every elements in the stack to auxiliary stack and followed by pushing every elements from auxiliary stack to the original stack will yield the original sequence. On the other hand, if we use auxiliary queue, the order of the sequence will be reversed. Knowing that, it is a best bet to use stack as the BOX. In fact, since we can only use stack and/or queue, it is the only data structure able to preserve the ordering.

So, right now, we have the idea of using multiple BOXES, each BOX is a STACK, and the number of BOXES depends on the number of possible partition of the book pile. How do we convert it into a pseudo-code?

Algorithm

Using the idea from the previous section, clearly the first thing we have to do is create the auxiliary stacks. Since the number of stacks is finite and known initially, we can state everything in our pseudo-code. After we create the auxiliary stacks, we just then need to put the element at the top of the stacks into the respective BOXES. At the end, we just collected from the BOXES, the pile of books in each BOX in the right order. So, for the sort by subject, the pseudo-code is as such:

• create 3 auxiliary stacks:
  • stack 1 to store B
  • stack 2 to store M
  • stack 3 to store P
• WHILE main stack is not empty DO:
  • check the element at the top of the stack:
    • IF subject is B THEN stack1.push(mainStack.pop())
    • IF subject is M THEN stack2.push(mainStack.pop())
    • IF subject is P THEN stack3.push(mainStack.pop())
• // returning to main stack is done in the reverse order because higher valued subject is put at the bottom
• WHILE stack3 is not empty DO mainStack.push(stack3.pop())
• WHILE stack2 is not empty DO mainStack.push(stack2.pop())
• WHILE stack1 is not empty DO mainStack.push(stack1.pop())

The same thing can be constructed for sort by size. Now, what remains is to sort by size-subject. As the name imply, this last sort can be done by simply doing:

• sort by size
• sort by subject

The brute-force way of doing the sort by size-subject can also be done by allocating 15 BOXES and retrieving from the respective order. However, the above code will do the correct way too because our last sorting is by subject. That means, eventually, the pile of books will be ordered by subject. However, before that, all the books are sorted by size. Since the sorting is stable (i.e. preserve original order) then within the subject, the books will be sorted by size. This is the exact behavior that we expect from our stack sorter.

 

 

HAPPY HACKING!
Adi Yoga S. Prabawa

Stack/Queue Primer

Stack and Queue

Stacks and queues are two data structures which can be thought of a limited form of linked list. It is a form of data encapsulation where only one elements are known at any single time, called the head (of the stack, or of the queue). Contrast this with linked list where you, as a user of the data structure is allowed to get the data from any index in the linked list without altering the content at all. In a stack or a queue, getting into the n-th element in it often involves removing the first n-1 elements from the data structure.

In a logical view, one way to describe a data structure is to define the operations that are allowed to be performed to it without considering how the data is actually represented or stored. For example, one logical view of a linked list is the operations 1) Insert at index, 2) Remove from index, and 3) Iterating the elements. However, these operations should be able to be performed without knowing the initial maximum number of elements to be put inside. Thus, we cannot represent such data with an array.

With such an informal definition of what a data structure can be, let us go into the two data structure that is the topic of this article.

Stack

Definition

A stack is a data structure that simulates last in first out (LIFO) abstract data types. In such a structure, it is useful to visualize the data like a stack of paper, with each paper containing the information that we need. However, we can only look into the data on the top of the stack of paper. To look into the middle of the stack, you have to remove the pile of papers from the top of the stacks (and possibly store them in another data structure since you don’t want your paper to disappear!) before you can read the information written on the paper. Similarly, to put new information (such as new sheet of paper), you just pile in on top of the stack of paper (lifting the whole stack of paper to put the new sheet at the bottom would waste your energy).

The visualization above is a brief description of what a stack is. More specifically, stack has two characteristic functions, namely push (putting new data on top of the stack) and pop (removing data from the top of the stack). Some authors give the function peek (looking at the top of the stack without removing it from the stack), but that can be simulated using a pop and a push sequence. Notice that both push and pop only accessed the elements from the top of the stack. Other operations that can get you the middle of the stack can be considered a violation of the stack data structure.

Implementation

As a stack only allows operations on top of the stack, we can think of a stack as a linked list where all operations involves the head and only the head of the linked list. As such, we can simply implement a stack using a basic linked list. Pushing into a stack then simply becomes adding into the head element of the linked list and similarly, popping from the stack simply becomes removing element from the head of the linked list. Both operations can be done in a single operation without iterating through the elements in the stack.

However, using linked list requires pointer operation (which is hidden if you are using Java) which requires memory access into the heap structure of the program. This can be considered to be a slower operation than using array which although may be put into a heap, some compiler does optimization so that the data is stored in the stack section of the program (notice that this is a different stack than the stack data structure we are talking about, although the stack segment of a program is implemented as –you guessed it– a stack). The question is then, can we use an array to implement a stack, especially when we know the maximum possible number of elements in the stack.

Array implementation of stack can be done using an integer index to simulate the top of the stack. Assuming that we have the index of the top of the stack, called TOP, which is the index of the next available slot of array to be inserted, how do you insert an element into this array-stack such that the variable TOP always point to the top of the stack. Since the TOP in the index of the next available slot, we can insert the new element pushed into the stack into the index pointed by TOP. The next operation is to restore the property of array-stack that TOP points to the top of the stack, which is to increment TOP (assuming that it starts from 0 instead of size-1). Thus, we have just inserted the new elements into the stack.

Similarly with pop, we can do the operation using this single index TOP. Now, TOP points to the next available slot, therefore, to pop elements from the stack, we have to decrement TOP first. With TOP now points to the last element we inserted, we can now retrieve the top of the stack. No further operation is needed since TOP already points to the next available slot. We have to be careful since when we use array to implement stack, the stack may be full (because array is fixed size). Thus, we have to know when the stack is full. It is also a good thing to know when the stack is actually empty.

In the linked list implementation, checking for stack to be full depends on the operating system. Should the operating system allow the program to increase its memory (up to the maximum the computer is physically capable), the linked list can only be full when the operating system cannot increase it further. However, we can check if the linked list is empty, which is to check if the head element is a NULL element. Similarly in array-stack, we can check if the stack is empty if TOP is equal to zero. Furthermore, we can check if the array is full when TOP is equal to the size of the stack.

When using the Java API for linked list to implement a stack, we can directly map the necessary operations:

1. Pop: LinkedList.addFirst (or similarly LinkedList.addLast)
2. Push: LinkedList.removeFirst (or similarly if LinkedList.addLast is used for Pop, use LinkedList.removeLast for Push)
3. Peek: LinkedList.getFirst (or similarly use LinkedList.getLast)
4. Check Empty: LinkedList.size() == 0

When array is used, assuming we have the index called TOP and the maximum size called SIZE, the following are the algorithm to implement stack using array called ARRAY of object of class Object (can be any user-defined object):

1. Pop:
   public Object pop() {
   TOP–;
   return ARRAY[TOP];
   }
2. Push:
   public void push (Object obj) {
   ARRAY[TOP] = obj;
   TOP++;
   }
3. Peek:
   public Object peek() {
   return ARRAY[TOP-1];
   }
4. Check Empty:
   public boolean isEmpty() {
   return TOP == 0;
   }
5. Check Full:
   public boolean isFull() {
   return TOP == SIZE;
   }

Note that in Pop and Push, I did not check if the stack is empty or full respectively. You should change the code above so that before popping, the checking of emptiness should be done (you should not pop from empty stack) and similarly before pushing, the checking of fullness should be done (you should not push to full stack).

Java API Stack

Unlike Queue Interface in Java API, Stack is implemented as a class in java. Creation of a Stack using this API is very much similar to using any template class. Notice, however, that there is a method for search (Stack.search(Object o)) in the API. Does this violate the stack operation where we can only access the elements from the top of the stack? The answer can be yes or no depending on the method to implement this. If the searching is done using iterative search by looping through the list, then it is strictly no. So, how do they implement this search?

While the detailed implementation of Java API is hidden from us, we can guess how they implement this search (which can be generalized into a function to get the data from the specific index of the stack). One simple idea to implement this search is to have another auxiliary stack to store the temporary data when we popped from the main stack. Thus, the sequence is to pop the data from main stack and push it into auxiliary stack until we find the desired object index or until the main stack is empty. At the end, we pop everything out from the auxiliary stack and back to the main stack. Can we do it without any auxiliary data structure?

At first it seems to be an impossible task. Any pop operation that is followed by another pop operation immediately lose the data from the first pop. So any pop should be accompanied by a push, since we allow no auxiliary data structure. But any sequence of pop followed by a push will only access the first element. The answer is through the use of recursion. Notice that during a pop operation, the remaining stack is exactly the original stack minus the data that is popped out. So, calling the search operation on this stack will search the object on a smaller sub-problem. But without any auxiliary data structure, we cannot store the top data unless the do it using recursion. Thus, we need an auxiliary method which is the recursive search to be called from the non recursive search function. The pseudo-code is given below:

• function Search (Object obj): return int index
  • return RecursiveSearch(obj, 0)

• function RecursiveSearch (Object obj, int idx): return int index
  • if (stack is empty) then return -1;  // if it passed this, then the Stack is non-empty
  • Object temp ← Pop();
  • if (temp is equal to obj) then
    • Push(temp);  // return the object into the Stack
    • return (idx+1);  // Java Stack is abnormally 1-based indexing from top of stack
  • int retIdx ← RecursiveSearch(obj, (idx+1));  // recursively search for the data, but keep the index first
  • Push(temp);  // return the object into the Stack
  • return retIdx;

From the pseudo-code above, we only use a fixed size Object Class temp to store the top of the stack without having any auxiliary data structure (such as another stack or queue or linked list). However, we simulate having an auxiliary stack by using the program stack. This program stack is created when the program calls the recursive function. In the call to the recursion function, the old data is pushed into this program stack and the new data is created on top of this program stack. This is the basis of activation record in a function call a.k.a. Call Stack.

Modification of this to get the object at the desired index is simple to do. Instead of putting the object as the argument, put in an integer index and have the function return an object instead of returning index, have the function to return the object. This last example shows illustration on what stack is used for in real program. Since we can use recursion to simulate having another stack, the reverse is also true, we can use stack to simulate recursion (albeit not all recursion can be simulated using only stack). However, in depth discussion will be the topic of another article.

Queue

Definition

Contrary to stack, a queue is used to simulate first in first out (FIFO) abstract data types. This object can be seen in many real life example like queues (as the name suggest), buffer, etc. Similar to stack, a queue is also a limited form of linked list. However, unlike stack –which can only be accessed from the top/head– a queue can be accessed from head or tail. Insertion can only be done at the tail of the queue while removal can only be done from the head of the queue, thus FIFO.

Implementation

We can skip the long-winded argument in stack in this section because I believe you should have an idea on how to implement this using a linked list. Below is the mapping of queue function (enqueue and dequeue) to a Java linked list function:

1. Enqueue: LinkedList.addLast (or LinkedList.addFirst)
2. Dequeue: LinkedList.removeFirst (or LinkedList.removeLast if LinkedList.addFirst is used for enqueue)

The implementation using array is also similar to stack but instead of having just TOP index, we should have HEAD and TAIL index. The naming is just a convention, you can call it TOP and BOTTOM if you want, but the more important thing is, they have to point to the first and the last element in the queue. Let’s stick to having HEAD and TAIL index.

Before going further with the implementation –since there are several– we have to clearly state the initial arrangement of the HEAD and TAIL index. Since we know the maximum size of the queue, let us assume that the HEAD is pointing to the earliest element position in the queue (or right before TAIL if the queue is empty) and the tail to point to the first empty position. Thus, we can define the queue to be empty if the (HEAD+1) and TAIL points to the same location. Unlike stack, checking both to value 0 is meaningless because they can move about. In stack, the index grows proportional to the size of the stack. Here in queue, the size is proportional to the difference between the HEAD and the TAIL index. However, the HEAD and TAIL index can be anywhere in the queue. What matters is their difference must be equal to the size of the queue.

While the above argument sounds simple, there is one slight problem. What happen when the TAIL index hits the value SIZE of array (note that the size of array is different from the size of the queue, we may have not inserted anything into the queue but the SIZE variable of array is fixed to be the number of elements that can potentially be filled in the array). When the TAIL is equal to SIZE, we simply have to reset it back to zero. Now, that causes the problem because to know the size, we cannot just take the difference between them using minus operation (in fact, |HEAD – TAIL| will not work too even if the returned value is always positive). With the complicated expression to calculate the size of the queue, let’s just opt to know when the queue is full in a different way.

In fact, knowing when the queue is full can simply be calculated from the position of the HEAD and TAIL index. Since the HEAD points to the earliest element inserted and the TAIL points to the last available position, we can know the queue is full if the last available position is exactly the HEAD. So, the queue is full when HEAD is equal to TAIL. As I said previously, that when any of the index is equal to SIZE, we reset it back to zero. We now have a real clear definition of what incrementing the index means (I put HEAD+1 two paragraphs above while brushing this issue aside, I now clearly define that plus operation). So, instead of just using + operation, we have to combine both + and % (modulus) operator. Thus, incrementing the index simply becomes HEAD = (HEAD+1)%SIZE. The same operation applies to TAIL.

In short, these are the operations for queue using array:

1. Enqueue:
   public void Enqueue (Object obj) {
   ARRAY[TAIL] = obj;
   TAIL = (TAIL+1)%SIZE;
   }
2. Dequeue:
   public Object Dequeue() {
   HEAD = (HEAD+1)%SIZE;
   return ARRAY[HEAD];
   }
3. Check Empty:
   public boolean isEmpty() {
   return ((HEAD+1)%SIZE)==TAIL;
   }
4. Check Full:
   public boolean isFull() {
   return HEAD==TAIL;
   }
5. Create new Queue:
   public Queue (int size) {
   SIZE = size;
   HEAD = size;
   TAIL = 0;
   Object[] ARRAY = new Object[size];
   }

Again, checking for full or empty should be done before Enqueue and Dequeue respectively.

Java API Queue

Java API does not implement Queue. Queue in Java API is merely an interface. Since you cannot instantiate an interface, there are two ways to go about this problem. One way is to instantiate a class which implements the interface but declare such object as having the class Queue. Using this way, the code would look like:

Queue<Object> queue = new LinkedList<Object>();

where Object can be replaced by any object you are using currently. However, note that the function Enqueue is called Queue.add while the function Dequeue is called Queue.remove.

Another implementation that can be done using Java API is to create your own class such as MyQueue with a Linked List inside. In the class MyQueue you provide the function Enqueue and Dequeue which calls the LinkedList.addLast and LinkedList.removeFirst respectively. Whichever implementation you are using, make sure your program is modular.

 

Happy Hacking!

Adi Yoga S. Prabawa

Extra Linked List Problem: Editor

Editor (a.k.a. Text Editor with Linked List)

Problem Description

Simulate a text editor (e.g. Notepad) with Linked List. A line in the text editor is indefinitely long (as long as there are enough memory inside). However, to simplify the problem, we are only allowing limited number of operations as described below based on the input:

1. If the input is Alphanumeric: insert the Alphanumeric symbol into the left of the cursor and move the cursor to the right
2. If the input is “<”: move the cursor to the left (simulate keyboard arrow ←)
3. If the input is “>”: move the cursor to the left (simulate keyboard arrow →)
4. If the input is “^”: delete the Alphanumeric symbol to the right of the cursor without moving the cursor (simulate keyboard DEL)

Input

The input is given as a single line, the whole operations on the keyboard that are being pressed, separated with whitespace. Read until there are no more input.

Output

The String displayed in the Editor.

Simulation and Algorithm

Simulation and discussion on Algorithm can be found here.

Note: The same problem can be done by simulating using 2-stacks

 

 

Happy Hacking!

Adi Yoga S. Prabawa

Take Home Lab 3

Balls Problem

Problem Description

There are N balls labelled with 1, 2, 3,.., N, from the left to the right. Now, we want to do two kinds of operations:

1. “A x y“: move the ball labelled x to the left of the ball labelled y, where x ≠ y. Reminder: if x is on the left of y, you may ignore this operation.
2. “B x y“: move the ball labelled x to the right of the ball labelled y, where x ≠ y. Reminder: if x is on the right of y, you may ignore this operation.
3. “R x“: remove the ball labelled x.

Print the final arrangement after M operations.

Input

• First line contains [INTEGER] N (0 < N ≤ 1,000) and [INTEGER] M (0 < M ≤ 1,000) which is the number of balls and the number of operations respectively
• Next M-lines are the operations in the format above

Output

The final arrangement of the balls with whitespace in between each labels

Algorithms

To perform the operation, assume we have the balls in a Linked List arrangement with the Linked List called ballList. The operations add(index, ball), remove(index), and indexOf(ball) is as defined in the Java Linked List specification. You should already know how to use Java API and/or implement your own Linked List implementation.

For those in need of studying the implementation of LinkedList, follow my previous article which describes LinkedList here. No code is given, only pseudo-code.

1. A x y

Informally, we can describe the implementation for this operation as these separate methods:

1. Remove X and store it in temp
2. Find index of Y
3. Put X in the index of Y (thus moving Y one position behind, and now X is on the left of Y)

Given the three functions above, we can now write the code for the operation A x y

• ball temp = ballList.remove(ballList.indexOf(x))
• int indexY = ballList.indexOf(y)
• ballList.add(indexY, temp)

One thing to note here is that finding the index of Y have to be done after the removal of X for the simple reason that the position of Y (i.e. values returned from inedxOf(y)) may changes after the removal of X if X is before Y.

2. B x y

By the symmetric property between the operation B x y and A x y, the pseudo-code for both operations will be largely the same. One main difference between them is the final position (or index) of the ball X when it is to be inserted into the ballList. While in the previous case, inserting it at index of Y will result in ball Y being moved one behind, in this case, we should not do that. Thus, the final index of X should be index of Y plus 1. Therefore, the code will be:

ballList.add((ballList.indexOf(y)+1), ballList.remove(ballList.indexOf(x)))

3. R x

Removal is actually trivial as it is already implemented by the remove (index) operation. Just need to call:

ballList.remove(ballList.indexOf(x))

to remove the desired ball.

Josephine

Problem Description

Josephine is a beautiful princess. She’s so beautiful that there are N princes proposing to her (needless to say, N could be as large as 100). After lots of consideration, Josephine and her parents realized that all these princes are perfect, so that it is impossible to choose one person and reject others with a good reason. They decided that Josephine would not reject the one chosen by Fate, while other princes could not ask for a fairer decision.

N princes, numbered from 1..N, are asked to stand in a circle. Our beautiful princess would choose a random number K and begin to find her fiance with that number. Starting from the first person, she counted to K, and removed that K-th person from the circle. Then, she starts counting from the next person and removes the K-th person. This process is repeated until all candidates are removed but The Chosen One.

Everything has been prepared, except one minor problem. To be sure that the processes are random enough, Josephine chose a large number K (around 100). As the result, counting and removing one princess after another would be a painful process. She leaves this work to you – the Royal Programmer.

Given N and K, your program should print out the numbers of princes in the order that they are removed from the circle. The last number would be the Chosen One.

NOTE: In short, this problem is merely a simulation problem

Input

• First line is [INTEGER] T (0 < T ≤ 100) which is the number of test cases
• Next T-lines contains [INTEGER] N (0 < N ≤ 100) and K (0 < K ≤ 100) which is as described above in the problem description

Output

For each test case, output the sequence of princes being removed (inclusive of the last prince removed, which is the bridegroom-to-be for the princess.

Algorithm

The algorithm will be much easier should we implement the Linked List in a circular fashion (describe in my previous post on the improvement for Linked List section). However, we might want to implement using the Java API LinkedList already written for us, which does not guarantee circular property (in fact, the Java API is more likely than not to implement Doubly Linked List than Circular Linked list). We will describe both cases of the algorithm starting from assumption of having Circular Linked List.

Further assumption that we need is that the princes are already inserted into a list of princes called princeList. The following two algorithms describes the algorithm for implementation of a single test case.

A. Circular Linked List

Given that we have a Circular Linked List implemented, the simplest algorithm we can have can be described in English to be the following:

While the number of Prince is not zero, we call princeList.getNext() for K-times and remove the Prince from the list and repeat the process until number of Prince is zero

In pseudo-code, the algorithm will be:

• size = N
• Prince current = head
• while size– > 0 do:
  • iteration = K
  • while iteration– > 0 do:
    • current = current.getNext()
  • Print (princeList.get(princeList.indexOf(current)))
  • princeList.remove(princeList.indexOf(current))

B. Java API Linked List

Since in Java API we do not have Circular Linked List, we have to simulate the circularity of the Linked List using the index. Remember that most programming language provide the modulo operation using the operator %. Modulo operation can be likened to be a circular number. Thus, we will exploit the fact that iteration of number = (number+1)%MAX will create a sequence of number as follows:

0, 1, 2, …, MAX-2, MAX-1, 0, 1, 2, …

Exploiting this property, we can have the following algorithm to calculate the next index given an index, a K-value, and the current size of the princeList:

index = (index+K)%princeList.size()

Therefore, the final algorithm will look like the following:

• size = N
• index = 0
• while size– > 0 do:
  • index = (index+K) % princeList.size()
  • Print (princeList.get(index))
  • princeList.remove(index)

Alternating List

Problem Description

A list is alternating if its elements alternate between positive and negative. For example:

You are given a linked list (original) and Q updates. For each update, check if the updated linked list is alternating. It is guaranteed that the elements in the linked list before and after update will not be 0.

There are 3 valid update operations, as explained below. Note that the indices of a list begin with one, not zero.

1. M <index> <size>: Move a block of elements of length <size> starting at index <index> to the back of the list. For example, let the current linked list be [1, 3, 5, 4, 2, 6]. The operation “M 2 3″ moves [3, 5, 4] to the end of the linked list. The updated linked list is [1, 2, 6, 3, 5, 4].
2. R <index> <size>: Remove a block of elements of length <size> starting at index <index> from the linked list. For example, let the current linked list be [1, 3, 5, 4, 6, 7]. The operation “R 2 4″ removes [3, 5, 4, 6] from the list. After performing the operation, we will have [1, 7].
3. A <index> <size> <value>: Add the elements between index <index> and <index size – 1> (inclusive) with <value>. For example, let the current linked list be [1, -3, -5, 6, 10]. The operation “A 1 3 4″ adds [-3, -5, 6] with value 4. The updated linked list is [1, 1, -1, 10, 10].

* It is guaranteed that <size> will not cause the index to go beyond the size of the Linked List (i.e. size index – 1 = LinkedList.size). For every operation, <size> is positive.

Input

• First line is [INTEGER] N (0 < N ≤ 100) and Q (0 < Q ≤ 100) where N is the number of elements in the original list and Q is the number of queries/operations to be performed to the list
• Next line consists of N x [INTEGER] separated by whitespace which is the original elements in the list
• Next Q-lines are the operations as described in the problem description above

Output

For each operation, output “YES” is the resulting list is alternating and “NO” otherwise

Algorithms

In this algorithmic solution, we will be using Java API Linked List exclusively. All operations performed here can be found in the Java API for Linked List. Assume the list is stored as Linked List called alternateList.

In addition, since this operation relies on Java API, we have to simulate the movement of List of Numbers from possibly anywhere in the Linked List to the end of the Linked List. There are many variations, and I will explain two choices made here. The first choice is to utilize the Java Linked List API method addLast (Collection c) which will append a list into the end of this current list. Thus, we need to create an auxiliary list to store all the elements we want to move to the end.

The second choice is to exploit the nice property that once we move the element at the current index to the back, the next element occupies the index of the elements we have just moved. Thus, we can just iterate the move/remove operation on the current index for the number of times as the size specify. This exploit fails on the add command, although with a simple hack, it can be made to work.

To illustrate, assuming we have the original list arranged as: 1 → 2 → 3 → 4 → 5 and operation M 2 3, the first choice of operation is the following sequence of operation:

• 1 → 2 → 3 → 4 → 5
• 1 → 3 → 4 → 5 || 2
• 1 →  4 → 5 || 2 → 3
• 1 → 5 || 2 → 3 → 4
• 1 → 5 → 2 → 3 → 4

Notice the use of || to separate the original list and the auxiliary list. The second choice is the following operations:

• 1 → 2 → 3 → 4 → 5
• 1 → 3 → 4 → 5 → 2
• 1 → 4 → 5 → 2 → 3
• 1 → 5 → 2 → 3 → 4

Whichever the choice of operation used, both produce the same end result. Note however, that the index used in this question is 1-based while Java API uses 0-based indexing.

1. Move

A. Auxiliary LinkedList

• LinkedList temp
• while size– > 0 do:
  • temp.add(alternateList.remove(index-1))
• alternateList.addAll(temp)

B. Single LinkedList

• while size– > 0 do:
  • alternateList.add(alternateList.remove(index-1))

2. Remove

No Auxiliary Linked List is needed in this operation because we do not even need to remember the elements we have removed. Thus, the code is simply:

• while size– > 0 do:
  • alternateList.remove(index-1)

3. Add

A. Auxiliary Linked List

• LinkedList temp
• while size– > 0 do:
  • temp.add(alternateList.remove(index)+value) // add the value while insert to Auxiliary Linked List
• alternateList.addAll(index, temp)

B. Single Linked List

• while size– > 0 do:
  • alternateList.set(index, alternateList.get(index)+value) // get value, add, and set the old value to new one
  • index++

4. Check for Alternating

Again, there is no need for Auxiliary Linked List because we are just doing a simple traversal. The code is given below

• if alternateList.size() == 0 then return TRUE
• else if alternateList.size() == 1 then return TRUE
• else:
  • for i=0 to size-1 do:
    • if alternateList.get(i) and alternateList.get(i+1) have the same sign then return FALSE
  • return TRUE // as we have iterated through the whole list

In checking for the same sign, there are several ways to do it, one is to use bruteforce to check all possible combinations of signs while the second one we exploit the arithmetical property that multiplication of two numbers of the same sign produces positive number and we are sure that none of the numbers will be zero in the end.

Thus, assuming we have two numbers X and Y, we can do the checking for the same sign by using these next two algorithms. SAME SIGN and DIFFERENT SIGN can be encoded into TRUE or FALSE depending on the usage and need of such boolean value.

A. Brute Force Sign Check

• if X > 0 && Y > 0 then return SAME SIGN
• if X < 0 && Y < 0 then return SAME SIGN
• return DIFFERENT SIGN

B. Arithmetic Exploit

• if (X*Y) > 0 then return SAME SIGN
• return DIFFERENT SIGN

 

HAPPY HACKING

Adi Yoga S. Prabawa

Linked List

List of Elements Chained with Links

Informal Explanation of Linked List

Linked List, as the name suggest, is based on chaining of non-sequential memory location (e.g. objects) through the use of links (e.g. pointers). Unlike Array, which is a sequential memory location, getting from one element of Linked List to the next involves following the links to the next elements. Contrast that with Array, where the memory location is sequential, getting from one element to the next involves only arithmetic operations on the memory address because the start addresses are sequential. In fact, in Array, getting into any addresses is just a simple arithmetic operation on the memory address which can be done in constant time. In Linked List, on the other hand, getting to the N-th elements requires us to follow the links for N-times because we do not know the start of the memory address, which can be anywhere.

With that basic idea of Linked List, we can now design the Linked List class and the element in the Linked List (called List Node). Firstly, based on the description above, at the very least, Linked List should have the link to another location (we call it the next element). This next element might be undefined (or NULL in most programming language) which indicates this element is the last List Node. Theoretically, the next element should still be List Node.

Intuitively, a List Node is like having a group of people to call each other for a roll call but instead of one person calling the rest, each person only need to call the next person (i.e. he only needs to remember the next person he has to call). Then, even if their houses (in this case, the houses are memory locations and the phone is the link) aren’t located consecutively in the same neighborhood, they can still maintain links with one another (or with just the next person).

Formal Explanation of Linked List

For those more mathematically inclined, a Linked List may be recursively defined as:

• Empty Linked List is a Linked List
• If L is a Linked List, and L.next is the next element, then L.next is also a Linked List

Design of Linked List

Given such informal explanation of Linked List, how do we code the Linked List then? Let us start with the lowest-level class in the design, the List Node before moving up on the logical elements and operations performed on Linked List.

1. List Node

As stated before, List Node should at the very least know the next element in the Linked List. The next element, which is another List Node, should be stored inside this class which yields the code:

class ListNode {

ListNode next;

}

Although the code looks like it will lead to infinite regress (because when we want to create a ListNode, we have to first create the next ListNode, which contains the next next ListNode), most programming language implementation allows for lazy evaluation. Lazy evaluation is to create the ListNode next element itself only when it is actually created (with new command). Initially, it is just a placeholder saying that there may be next element.

2. Linked List

In the Linked List class, we should only concern at having to first point to the first List Node in the Linked List. This is akin to the teacher-in-charge of the club (i.e. Linked List supervisor) remembering only the president of the said club (i.e. the head of the Linked List). Thus, the code for Linked List class is:

class LinkedList {

ListNode head;

}

The basic operations supported by LinkedList are: insertAt (index, node), removeAt (index), and get (index). We will discuss each of them separately.

A. get (index)

To implement get (index), we need to be able to traverse from the head to the element at specified index. This method is essential for other operations, so we will implement this function first. The intuition for this function is just to follow through the Linked List from the head List node down to the element at the specified index. Assuming we use 0-based indexing (which is common in Java API), we get the following code in the LinkedList class:

• function get (index): return ListNode
  • if index == 0 then return head
  • ListNode curr = head; // we let curr to do the traversal for us
  • while curr <> NULL && index– > 0:
    • curr = curr.next
  • return curr; // which may be NULL if index is smaller than the size

At the end of the execution of this function, we should get either NULL, or the correct element at the specified index.

B. removeAt (index)

Intuitively, viewing from the informal explanation of the group above, to remove someone from the group is just to let the person which have to call the person to be removed to call the next person instead. In code, we do that by setting the next ListNode pointed by the person at (index-1) to point to the person at (index+1), thus skipping the person at index. Writing it into code we get:

• function removeAt (index): return ListNode removed
  • if head == NULL:
    • specify an error and return NULL
  • else if index == 0: // Removal of head
    • ListNode temp = head  // Otherwise we cannot return this ListNode
    • head = head.next         // Remove
    • return temp
  • else:
    • ListNode prev = get (index-1)    // Either one of these
    • ListNode curr = get (index)       // may actually be
    • ListNode skip = get (index+1)  // NULL
    • if prev == NULL then return NULL  // if prev is NULL, ignore the operation
    • prev.next = skip; // Skip may be NULL, in which case, prev becomes the last element
    • return curr

After the call to the function, the element at index is removed from the list if the index is within the range and returned. If it is outside the range, then no operation needs to be done and the return value is NULL.

C. insertAt (index)

Intuitively, to insert at a specified position, we just have to make sure someone in the position before him (i.e. (index-1)) calls this new person instead of his usual next person. In addition, we instruct this new person who just join to just remember he should call next. In code, we get the following:

• function insertAt (index, node):
  • if head == NULL:
    • head = node
  • else
    • ListNode prev = get (index-1)
    • if prev == NULL: // Find the Last Element
      • ListNode temp = head
      • while temp.next <> NULL
        • temp = temp.next
      • prev = temp
    • ListNode curr = prev.next
    • prev.next = node  // Put node into the correct position
    • node.next = curr  // After prev, before curr

After the call, either node is inserted to the back of the Linked List (when the index is outside the range) or the node is inserted at the proper index.

Improvement to Linked List

While the basic implementation of Linked List is enough for any extended Linked List implementation (i.e. all extended implementation of Linked List can be simulated using this basic implementation), sometime we wants fewer operations to be performed. For example, during insertion, we have to find the previous elements, and current elements, which involve traversal for each operation. We can improve the implementation by doing only a single traversal and return the two values <prev, curr> in another data structure. However, that improvement still results in a fundamentally the same data structure as List Node and Linked List described above.

An improvement that results in a slightly difference data structure is the Circular Linked List. In this case, the last element in the Linked List point to the first element in the Linked List. As such, get (index) operation may result in a loop operation when overflow. insertAt and removeAt also need to take into account this possibility of inserting/removing the head or the last element which may rearrange the circularity of the Linked List. In addition, removal from a single element Linked List or insertion into an empty or single element Linked List may need special cases.

Another improvement is to extend the job of each List Node to remember not just the next person, but the previous person. This way, we can actually move back and forth in the Linked List. While there is fundamentally no change in get (index) operation, removeAt and insertAt can be more efficient. Removal and insertion only need to know the element at the specific index, without knowing at all where the previous or the next elements are because they can be inferred directly. As such, the operations become:

• function removeAt (index): return ListNode removed
  • if head == NULL:
    • specify an error and return NULL
  • else if index == 0: // Removal of head
    • ListNode temp = head  // Otherwise we cannot return this ListNode
    • head = head.next         // Remove
    • head.prev = null           // Forget the previous person
    • return temp
  • else:
    • ListNode curr = get (index)
    • if curr == NULL then return NULL
    • curr.prev.next = curr.next
    • if (curr.next <> NULL) then curr.next.prev = curr.prev
    • return curr

• function insertAt (index, node):
  • if head == NULL:
    • head = node
  • else
    • ListNode prev = get (index-1)
    • if prev == NULL: // Find the Last Element
      • ListNode temp = head
      • while temp.next <> NULL
        • temp = temp.next
      • prev = temp
    • ListNode curr = prev.next
    • prev.next = node  // Put node into the correct position
    • node.prev = prev
    • node.next = curr  // After prev, before curr
    • if curr <> NULL then curr.prev = node

Properties of Linked List

To end the discussion about Linked List, let us describe the properties of the Linked List in more details. In a Linked List, the data is non-sequentially laid out in the memory as such, no arithmetic operation can determine the start of a block of List Node (unlike in Array). The advantage over array is that the initial number of elements in the Linked List need not be known from the start, while in Array, the initial size have to be known because addresses have to be allocated before.

In addition, an Array requires a fixed size of memory (which is known from the start) while Linked List allow the use of minimum memory which can shrink or grow depending on the need. However, for the same number of elements in the Linked List and Array, a Linked List contains more book-keeping variables and thus, consumes more memory per element.

The disadvantage of Linked List is the access of elements is non-trivial. We have to traverse through the links to get to the correct elements. In an Array, we just need to indicate the displacement in memory address from the start of the Array to get the desired element.However, to insert into an Array, we have to move all the subsequent elements in the array one memory location below. In a Linked List, we just need to update the links (e.g. pointers) to point to the correct sequence. The same comparison is the same for removal. However, there is a hidden cost of finding the index to be inserted first before doing the operation in a Linked List. Thus, overall, the number of operations are the same for insertion and removal between Array and Linked List. Nevertheless, improvement is possible through the use of Hashed indexing, but that is a topic for another day.

 

 

HAPPY HACKING!

Adi Yoga S. Prabawa

Sit-in Lab 2

Phone Problem

Problem Description

You are looking for an internship for your summer holiday. Hendy’s Mobile Corporation (HMC) called you for an interview at their company. HMC is a renowned company with multiple breakthrough innovations in the past few years. HMC is developing a smartphone with multiple storages functionality and they are looking for programmers to be part of the project.
As part of the interview questions, you are asked to create a program to analyze how an application interacts with the multiple storages in a phone.

Input

• First line is [INTEGER] N (0 < N ≤ 100) and [INTEGER] S (0 < S ≤ 1,000,000) where N is the number of storage and S is the size of each storage in KB
• Second line is [INTEGER] A (0 < A ≤ 100) where A is the number of applications to be installed
• Next A-lines is [STRING] <application name> and [INTEGER] <application size> to be installed

Output

• First A-lines is the result of each installation: “Added to storage <storage number>” on success or “Failed to be added” on failure
• Next line is the smallest application installed followed by its size
• Next line is the largest application installed followed by its size
• Next line is “Remaining storage size:”
• Next N-lines is the remaining size of each storage: “Storage <storage number>: <remaining size in KB> KB”

Class Design

1. Application Class

This class should store the <Application Name> and the <Application Size>. Operations in this class may include getting the name and getting the size. However, note that both class variables should be private and should not have setter function (i.e. application cannot change name in the middle from the result of being changed –from function call from another objects– by another objects in the phone).

2. Storage Class

This class should maintain the list of Applications installed in this storage. The remaining size is optional to be stored, because the total size of the storage can be computed and coupled with the initial storage size stored in the Phone class, the remaining size of each storage can be computed. However, as remaining size can be a frequent operations in the program, it is better to designate a variable specifically for it, updated on installation of new applications.

Lastly, the storage number is purely optional. One reason why it should be inside the storage class is that its number is generally cannot be changed. Thus, it warrants having a variable to store the number. One reason why it should not be inside the storage class, but to be stored/computed by the phone class instead is that the phone may need to move the storage around for efficiency (e.g. sort the storages based on the remaining size). Either way, the phone should be able to get the storage number.

Operations in this class may include checking whether an application can be installed into it although this logic checking can be done by phone class instead. However, at the very least, adding the application (i.e. installing the application) should be performed by this class. In addition, partial computation of remaining size (through computing the total size of applications installed in this storage) and/or full computation of remaining size should also be performed in this class.

3. Phone Class

This class should store the list of storages. As stated above, maintaining the number attached to each storage can be stored in this class. Operations in this class should include adding new storage, logic checking for installation of applications (mostly on the loop), and displaying information.

Algorithms

1. Installation:

• for each Storages:
  • if current storage can install application (remaining size > size of application):
    • install the application
    • return success
• return failure (because no storage can install the application successfully)

2. Finding the Smallest & Largest Application

• smallest = NIL; largest = NIL;
• for each Storages:
  • for each Applications in the current storage:
    • if smallest == NIL || application size < smallest size:
      • smallest = application
    • else if largest == NIL || application size > largest size:
      • largest = application
• return smallest & largest

3. Get the Remaining Size

• List of storage size: Sizes
• for each Storages:
  • Sizes = remaining size of current storage
• return Sizes

 

Social Network Problem

Problem Description

In this problem, you are asked to simulate the process in social network. You can add friend (send friend request), approve request, count the mutual friends between 2 people and count the number of pending requests.
The valid operations are:

1. Add <person1> <person2>
   • <person1> adds <person2> as friend
   • <person2> adds <person1> into the list of pending request
   • Output “<person2> is already a friend of <person1>” if <person1> and <person2> are already friends before this, otherwise, output nothing
2. Approve <person1> <person2>
   • <person1> will approve the request of <person2>. After this operation, <person1> is a friend of <person2>, and <person2> is also a friend of <person1>
   • <person1> remove <person2> from the list of pending request
   • It is guaranteed that there is an “Add <person2> <person1>” operation before “Approve <person1> <person2>” operation
   • There is no output from this operation
3. Mutual <person1> <person2>
   • Output the number of mutual friends that <person1> and <person2> have

• It is guaranteed that if A has a pending request from B, A won’t add B

Input

• First line is [INTEGER] N (0 < N ≤ 100), denoting the number of people in the Social Network platform
• Next N-lines contains [STRING] <names of the people> in the Social Network platform guaranteed to be unique
• Next line is [INTEGER] M (0 < M ≤ 1,000), indicating the number of operations
• Next M-lines will be the operations in the format described above

Output

The result of each query in a separate line (note that some of the operations do not produce output t all)

Class Design

1. People Class

This class should contain the name of the user of the Social Network platform. In addition, it should also maintain the list of pending request and list of friends. The checking for symmetric nature of list of friends (i.e. A friend B iff B friend A) should not be in the logic of this class. Other logic such as checking if B is already the friend of this user before adding B into the list of pending request may be done in this class. However, better design will be to check for friendship in Social Network class instead although the paradigm of Defensive Programming dictates that both this class and Social Network class checks for this violation.

2. Social Network Class

This class should maintain the list of People (i.e. user of Social Network). The logic of this program should be mainly handled in this class. Logic such as counting the number of mutual friends is better not to be given to the Person class for security reason (e.g. Person class should not know the complete list of friend of another user). However, logic such as checking for whether two users are already friends before adding the request can be done in both this and Person class. Operations in this class can be mapped directly into the list of operations that should be supported based on problem description above.

Algorithms

1. Add Request

• get person A, get person B
• if A and B already friend:
  • return failure
• add request from A to B
• return success

2. Approve Request

• get person A, get person B
• remove person B from A’s list of pending request
• add person B into A’s list of friend
• add person A into B’s list of friend

3. Count Mutual Friend

• get person A, get person B
• get friends of A, get friends of B
• set intersection algorithm:
  • for each user in list of friends of A:
    • if the user is also in list of friends of B:
      • number of mutual friends + 1
  • return number of mutual friends

Lab 0

1. HelloWorld

A. Problem Statement

This is a simple arithmetic problem of binary operation AND and OR. In an AND operation, the result is 1 if and only if both bits are 1. In an OR operation, the result is 0 if and only if both bits are 0.

B. Input Reading

The first line is an integer TYPE which indicates which type of input (1, 2, or 3) should be read next.
You should read the primer about input reading in CS1020 before continuing.

Besides processing the very first line, the rest of the input reading method is already discussed in the link above. Please refer to it when in doubt. I will now discuss the pseudo-code for the input reading of the first line and minor processing into the various types.

1. TYPE = integer;
2. if (TYPE == 1):
3.     // Read type 1 input here
4. else if (TYPE == 2):
5.     // Read type 2 input here
6. else:
7.     // Read type 3 input here

Now, converting this to the code is straightforward. I will give two versions –one using if-statements similar to the above pseudo-code, and the other using switch-case-statement– of the code for your practice.

1. int TYPE = sc.nextInt();
2. if (TYPE == 1) {
3.     // Type 1 Input
4. } else if (TYPE == 2) {
5.     // Type 2 Input
6. } else {
7.     // Type 3 Input
8. }

1. int TYPE = sc.nextInt();
2. switch(TYPE) {
3.     case 1: // Type 1 Input
4.         break;
5.     case 2: // Type 2 Input
6.         break;
7.     default:  // Type 3 Input
8. }

Notice two things about the switch-case-statement. One is after every cases, we separate the cases with break-statement such as in line 4 and 6. However, in line 7, we do not put break because it is already the last case. Second, we do not need to put case 3 (which corresponds to having (TYPE == 3) statement) because the case goes to default when there are no other cases which fit into it. This is similar to the else-block in the if-statement variant. It goes to the else-block if there are no other cases which fit into it.

C. Algorithm

Whenever you are in doubt, always think of the simplest solution. Every problem has a natural brute-force algorithm to solve it. Although we may not learn much from the brute-force algorithm, it may gives us an insight on how to solve the problem more efficiently. I am giving two variants on how to solve this problem. One variant is using nested if-statements and the other is using table to solve the problem.

IF-Statements

In the natural brute-force solution, all we have to do is enumerate all the possible solution. Therefore, the solution to this problem will be:

1. if (operation.equals(“AND”)) {
2.     if (bit1 == 0 && bit2 == 0) {
3.         System.out.println(0);
4.     } else if (bit1 == 0 && bit2 == 1) {
5.         System.out.println(0);
6.     } else if (bit1 == 1 && bit2 == 0) {
7.         System.out.println(0);
8.     } else {
9.         System.out.println(1);
10.     }
11. } else {
12.     if (bit1 == 0 && bit2 == 0) {
13.         System.out.println(0);
14.     } else if (bit1 == 0 && bit2 == 1) {
15.         System.out.println(1);
16.     } else if (bit1 == 1 && bit2 == 0) {
17.         System.out.println(1);
18.     } else {
19.         System.out.println(1);
20.     }
21. }

With the above algorithm, we are enumerating all the possible solution space. However, notice that most of the solutions are the same with only one of the cases print differently. We can compact the condition to only those that are different:

1. if (operation.equals(“AND”)) {
2.     if (bit1 == 1 && bit2 == 1) {
3.         System.out.println(1);
4.     } else {
5.         System.out.println(0);
6.     }
7. } else {
8.     if (bit1 == 0 && bit2 == 0) {
9.         System.out.println(0);
10.     } else {
11.         System.out.println(1);
12.     }
13. }

Now, in this improved algorithm, the three cases that are the same are combined into one case in the else-block. Why didn’t we put it in then-block is because we have to enumerate the three cases in the if-statement to put it there. It is easier to just put the odd one out in the if-statement. Can we further improve it? The answer is yes. The if-condition to print 1 becomes:

if ((operation.equals(“AND”) && bit1 == 1 && bit2 == 1) || bit1 == 1 || bit2 == 1)

Table Algorithm

This second variant of the solution uses table to solve the problem. In this solution, instead of doing an if-statement, we encode the solution in a table form. We initialize the table (2×2 array) such that the first index correspond to the first bit and the second index correspond to the second bit. The value in the cell depends on the type of the table. I’ll illustrate the construction of AND_table:

1. int[][] AND_table = new int[2][2];
2. AND_table[0][0] = 0;
3. AND_table[0][1] = 0;
4. AND_table[1][0] = 0;
5. AND_table[1][1] = 1;

Construct the OR_table in a similar manner to get the corresponding value on the table. The usage of this table then becomes straightforward:

1. if (operations.equals(“AND”)) {
2.     System.out.println(AND_table[bit1][bit2]);
3. } else {
4.     System.out.println(OR_table[bit1][bit2]);
5. }

2. Matrix

A. Problem Statement

This is a problem of simple looping over the row or column of a matrix. This also illustrate the difference between 0-based and 1-based indexing in an array.

B. Input Reading

Input statement:

1. The first line of the input contains two integers, N (1 <= N <= 100) and M (1 <= M <= 100).
2. The next line is an array with size N x M.
3. The next line is the query with format “ROW x“, (1 <= x <= N) or “COLUMN y”, (1 <= y <= M).

A simple look at the description reveals that the input is of type matrix (type 1 with type 1 variant). However, it is immediately followed by a single other input not befitting any type because it is just a single input. Refer to the link above to read more about matrix type input.

C. Algorithm

Remember that the array in a computer has an index that starts with 0. However, in the problem, our array (or matrix, in this case) starts the index with 1. We have to take care of the difference between these two indexing mode in our algorithm.

Naturally, the algorithm has to differentiate between the row and the column. With a simple trial and error, the row corresponds to the maximum value of N while the column corresponds to the maximum value of M (okay, I lied, it is stated in the questions). Now, to sum up the row, we then have to iterate from 1 to M (since the row has the maximum value of N, that means the sum in that row corresponds to the sum of each column in that row) and vice versa, when it’s column, we iterate from 1 to N. Thus, the algorithm looks like the following:

1. int sum = 0;
2. if (operations.equals(“ROW”)) {
3.     for (int i=0; i<M; i++) {
4.         sum += matrix[index+1][i];
5.     }
6. } else {
7.     for (int i=0; i<N; i++) {
8.         sum += matrix[i][index+1];
9.     }
10. }

A few things to note from the code above is the shorthand notation +=. This operator is a combination of two operators (+ and =). The interpretation of such shorthand notation is: sum = sum + matrix[index+1][i]. Secondly, the index is incremented by 1. This is because, as we have discussed above, the array is natively indexed in JAVA starting from 0 while in our problem, it should be indexed starting from 1.

3. Palindrome

This problem is to practice simple String manipulation. Operations using String such as concatenation, reversal, character extraction, etc should be used widely here. In addition, I will skip the input and problem statement here because they are trivial. The solution to this problem is more challenging than the input part.

As a primer to solve this problem, notice that the two Strings given are of equal length. Thus, the problem is reduced into the problem of checking if one String the reversal of the other. This simplified problem can be done much easier than when the String are of different length.

I propose a simple palindrome checker which works as follows:

1. LOOP: from i=0 to length of String
2.     if (character at position i from left of String 1 != character at position i from right of String 2)
3.         NOT PALINDROME

The algorithm above is a simple checker that assumes the Strings are palindrome until it finds a case where it is not. Translating it into code is harder than simple translation. The code is as follows:

1. boolean palindrome = true;
2. for (int i=0; i<word1.length(); i++) {
3.     if (word1.charAt(i) != word2.charAt(word2.length() – i – 1)) {
4.         palindrome = false;
5.         break;
6.     }
7. }

At the end of the algorithm above, the result is stored in the variable called palindrome.

Input Reading in CS1020

Primer in Reading Input for CS1020

Types of Input Reading

Although there can be theoretically infinitely many ways to read input in CS1020, many of the sit-in lab problems can be reduced into three basic block. From these three basic blocks of input reading methodology, many combinations can be made. Practice these three input types carefully and know when to use them appropriately.

1. Type 1: Given N, Read The Next N Lines

The first input reading is the easiest among the three. So, it is good if we start with this one first. In this input type, the description is as follows:

The first line is N which is the number of next inputs. The next N lines consists of the inputs.

The format generally reduces to such statements. In essence, you are given the number of elements you are supposed to read.

So, directly from the statement, we know that there should be a loop in our input reading. This loop should go for N times, regardless of the way we do the looping. Inside the loop, we should read the input based on the format of the input (which is ignored in this abstraction to show you the barebone of the input reading method).

A direct translation of the description above into a pseudo-code will yield the following:

1. N = integer;
2. LOOP: from i = 1 to N
3.       // Read the rest of the input

To translate this pseudo-code into a working code, we have to do it step-by-step. Starting from the first line “N = integer”, we convert it to read from the Standard Input using Scanner Class. Since the type is integer, we have to use the method: Scanner.nextInt() which returns exactly what we need, an integer type. The code becomes: “int N = sc.nextInt();” where sc is declared as Scanner sc = new Scanner(System.in).

The second line is a loop. There are two useful loop-construct available in JAVA (or in most other programming languages). The first construct is called the for-loop. In the for-loop, we specify three statements: 1. The initial condition, 2. The continuing condition, and 3. The end statement (what statement is executed at the end of each for-loop block). To iterate for N-times, the usual method is: “for (int i=0; i<N; i++)”. Notice that although in the pseudo-code we specify that we are looping from 1 to N, in the for-loop construct, we are looping from o to N-1. Both are equivalent.

Now, combining both, we will get the following:

1. int N = sc.nextInt();
2. for(int i=0; i<N; i++) {
3.   // Read the rest of the input
4. }

2. Type 2: Read Until Special Character/Number

In this second type of input reading, we do not know how many inputs will be available. However, we will know that in the input, there will be special characters/numbers which signals the end of input sequence. The input specification might be written as follows:

Read the input until you read 0.

It is very important to elaborate about the underlined part. The statement above may as well be written to be “Read the input until you read -1″ or “Read the input until you read exit”. Nevertheless, you should know what the terminating sequence is.

After you know what the terminating sequence is, it is important to know the data type of the terminating sequence. When you read until 0 or -1, it is easy to assume that we should read integer. This, in fact, might lead to an error. The data type of the terminating sequence cannot be determined independently by itself but it has to follow the more general between the terminating character and the first input in the input format.

To explain this, let’s take a look at the following input specification:

The input consists of the following: Name (in String), Age (in Integer), and Height (in Double). Read the sequence until you read -1 in the input.

The bracket is what you should highlight yourself, it might not be given in the question. Now, what should the data type of the terminating character -1 be? To answer that, notice that the input sequence will start with Name, which is a String. -1 will appear in the place of Name. So, we should be taking the more general of the two, which is the String. As such, the terminating character should be regarded as a String.

After determining the data type of the terminating character, the next step is to write the pseudo-code. Rephrasing the problem helps to design the pseudo-code too. The following two rephrases are equivalent to the input statement above:

A. While the input is not [terminating character], read the input sequence.

B. Read input sequence unless we encounter [terminating character], if so, exit the loop.

Let’s follow the method A first. In method A, we can write the pseudo-code as follows:

1. name = String;
2. LOOP: while name is not “-1″
3.     age = integer;
4.     height = double;
5.     // since we will go back to loop after this
6.     // we should read name one more time to be checked at line 2
7.     name = String;

What you should note in the above pseudo-code is that the checking is done at line 2. So, before we execute line 2, the variable name has to reflect the latest value so that age and height is not read at all. That’s why at line 7, we re-read the name because in a while-loop, we will go back to line 2 after we execute the last statement in the block. In addition, the checking of -1 should be done as String comparison, which in JAVA, should use String.equals(String) method. Lastly, because we are rewriting the value of name at line 7, in between line 4 (where all the inputs have been collected) and line 7 (where we rewrite the value), the data should be processes (either used, or stored). The code will then look as follows:

1. name = sc.next();
2. while(!name.equals(“-1″)) {
3.     age = sc.nextInt();
4.     height = sc.nextDouble();
5.     // PROCESS THE DATA HERE
6.     name = sc.next();
7. }

Now, following the method B, we arrive at the following pseudo-code:

1. LOOP: infinitely
2.     name = String;
3.     if (name is “-1″)
4.         exit the loop;
5.     age = integer;
6.     height = double;

In this second method, we do not know when will the terminating character is encountered. As such, the loop should run possibly infinitely. The exit from the loop itself is done at line 4. The checking of the terminating character should be done right after the reading of the first input (which is name). Lastly, the data can be used/stored anywhere after line 6 as long as it is still inside the while-loop block. The code would look like the following:

1. while (true) {
2.     name = sc.next();
3.     if (name.equals(“-1″)) {
4.         break;  // exit from the loop
5.     }
6.     age = sc.nextInt();
7.     height = sc.nextDouble();
8.     // PROCESS DATA HERE
9. }

3. Type 3: Read Until End-of-File

This last basic block of input reading is notably where most of the past students have problems. One reason is because of the rarity in which it occurs in past sit-ins that when it comes, most have forgotten how to use it. Another reason is the lack of available practice in this type of input because again, the rarity on which it occurs. Nevertheless, it may still come out in sit-in labs, or other scenarios as well. This type of input will have input statement similar to the following:

Read the input sequence until there’s no more input.

The phrase “until there’s no more input” indicates that you should read until End-of-File character (or EOF) is read. The difference between this input type and the previous one is that in this third type, there’s no terminating character at all. So how do we know when we have reached the end of the input? The good news is JAVA provide exactly such function:

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/Scanner.html#hasNext%28%29

Firstly, recognize that the hasNext method has several variants which corresponds to the data type (similar to Scanner.next() variants). Afterwards, we can construct the following pseudo-code:

1. LOOP: until there’s no more input
2.     // Read input and process

hasNext method returns a boolean, which is perfect to use in a while loop as follows:

1. while(sc.hasNext()) {
2.     // Read input and process
3. }

This last input type is not too hard once you understand the basic of input reading. You should practice on these three input reading methodology well as they can come in several variants, each of which is related to these three basic building block in making complex input reading.

Combining Input Reading Method

1. Matrix Type: Two Type 1 Input Reading

In this matrix type variants, the essence is that, the first two numbers dictates the size of the matrix. The input will be in the shape of a matrix, and we have to process it as such. For example, the following input statement is matrix type:

The first line consists of two numbers, N and M. The next N lines will consists of M numbers.

The visualization of such input is this:

1.1   1.2   1.3   …   1.M
2.1   2.2   2.3   …   2.M
…
N.1   N.2   N.3   …   N.M

So, we know that we need two loops, since we are given a matrix. The problem is, how to construct the loop. Fortunately, we should know the size of the matrix in advance. So, we should have created the following matrix: int[][] matrix = new int[N][M];. Now, all we need is just to loop twice like in this pseudo-code:

1. N = integer; M = integer;
2. LOOP: from i=1 to N
3.     LOOP: from j=1 to M
4.         // Read input and put in matrix

which can be easily transformed into the following code:

1. int N = sc.nextInt(); int M = sc.nextInt();
2. for (int i=0; i<N; i++) {
3.     for (int j=0; j<M; j++) {
4.         matrix[i][j] = sc.nextInt();
5.     }
6. }

2. Combination of Type 2 and Type 1

In this combination, there can be two possibilities: 1. Type 2 is outside, type 1 is inside type 2, or 2. Type 1 is outside, type 2 is inside type 1. We will discuss both here.

A. Type 2 Outside, Type 1 Inside

In this input reading method, the input is further divided into smaller cases. One possible input statement is as follows:

You should read the number of input until you encounter -1. If it is not -1, it means it will be greater than 0. Let this number be N, this number indicates in the next N-lines will be the items.

Visualization of the input is as follows:

N1
item 1
item 2
…
item N1
N2
item 1
item 2
…
item N2
…
-1

Notice that we can just put the block corresponding to type 1 input inside the type 2 directly. The following pseudo-code does exactly that:

1. N = integer;
2. LOOP: as long as N != -1
3.     LOOP: for i=1 to N
4.         // Type 1 Input
5.     END LOOP
6.     N = integer;  // for next check
7. END LOOP

The outer loop is of type 2 input while the inner loop is of type 1. We can easily convert this to the following code:

1. int N = sc.nextInt();
2. while (N != -1) {
3.     for (int i=0; i<N; i++) {
4.         // Type 1 Input
5.     }
6.     N = sc.nextInt();
7. }

B. Type 1 Outside, Type 2 Inside

The same idea also applies for the reverse. However, we end up with the following pseudo-code:

1. N = integer;
2. LOOP: for i=1 to N
3.     term_char = String;
4.     LOOP: while term_char is not equal to [terminating character]
5.         // Type 2 Input
6.         term_char = String;
7.     END_LOOP
8. END_LOOP

and end up with the following code:

1. int N = sc.nextInt();
2. for (int i=0; i<N; i++) {
3.     String term_char = sc.next();
4.     while (!term_char.equals(TERMINATING_CHARACTER)) {
5.         // Type 2 Input
6.         term_char = sc.next();
7.     }
8. }

3. Combination of Type 3 and Type 1/2

Unlike the point above, this type cannot have type 3 inside the type 1 or type 2 for the simple reason that type 3 reads until there’s no more input, so it has to be outside. I hope by now you should be familiar with this kind of combination that you can easily construct this. As such, I will just give the code directly.

A. Type 3 Outside, Type 1 Inside

1. while (sc.hasNext()) {
2.     int N = sc.nextInt();
3.     for (int i=0; i<N; i++) {
4.         // Type 1 Input
5.     }
6. }

B. Type 3 Outside, Type 2 Inside

1. while (sc.hasNext()) {
2.     while(true) {
3.         name = sc.next();
4.         if (name.equals(“0″)) {
5.             break;
6.         }
7.         // Type 2 Input (the rest)
8.     }
9. }

Conclusion

The basic building block of input reading is the three simple block (named Type 1, Type 2, and Type 3). From these three basic building block, we can combine them into a more complex input reading. These three are expected in the sit-in lab, but there are more variants of input reading when you take Competitive Programming. More advanced input reading includes having whitespaces separating legal input (which will cause the Scanner.nextInt() to only read partial value, which is wrong), having non-whitespace as delimiter (so you cannot use Scanner.next() correctly), etc.

However, for the purpose of CS1020, in most cases, the combination of these three will suffice. Make sure you master them.

UNIX and VIM Command

UNIX Commands:

1. Change Directory: cd directory_name
2. List Contents: ls [-all]
3. Remove Entries: rm file_or_folder_name
4. Copy Entries: cp original_file destination_file
5. Edit in VIM: vim file_name
6. Java Compile: javac *.java
7. Running Java Program: java class name [< input_file] [> output_file]
8. Checking File Difference: diff file_one file_two

VIM Commands:

1. Delete Current Line: dd OR :d
2. Exit without Save: :q!
3. Write file: :w
4. Save and Exit: :wq OR ZZ
   • DO NOT USE: : x
   • Because it is very similar to :X (save with encryption)
5. Search for Patterns: /(patterns)
   • Next Item: n
   • Prev Item: N
6. Auto Indentation: gg=G

Hello

World!