[SOLVED] Csc6010 programming assignment 1 to 6 solutions

Credit card numbers follows certain patterns. A credit card number must have between 13 and 16 digits. It must start with:

o 4 for Visa cards
o 5 for Master cards
o 37 for American Express cards
o 6 for Discover cards
In 1954, Habs Luhn of IBM proposed an algorithm for validating credit card numbers. The algorithm is useful to determine whether a card number is entered correctly or whether a credit card is scanned correctly by a scanner. Credit card numbers are generated following this validity check, commonly known as the Luhn check or Mod 10 check, which is described as follows ( for illustration, consider the card number 4388576018402626):

1. Double every second digit from right to left. If double of a digit results in a two-digit number, add up the two digits to get a single digit number.

2. Now add all single-digit number from the step above (Step 1 ).
4 + 4 + 8 + 2 + 3 + 1 + 7 + 8 = 37

3. Add all digits in the odd places from right to left in the card number.
a. 6 + 6 + 0 + 8 + 0 + 7 + 8 + 3 = 38

4. Sum the results from the above two step ( Step 2 and Step 3).
37 + 38 = 75

5. If the result from the above step ( step 4 ) is divisible by 10, the card is valid; otherwise, the card is invalid. For example, the card number 4388576018402626 is invalid, but the card number 4388576018410707 is valid.

Design and Implement the above algorithm in Java Recursively. Your algorithm should prompt the user to enter a credit card number as a long integer. Display whether the number is a valid or invalid credit card number. Design your program to use the following methods: These methods should be done recursively… Make sure you have several runs, i.e. several testing conditions.
//Return if the card number is valid
Public static Boolean isValid(long number)

//Get the result from step 2
Public static int sumOfDoubleEvenPlace( long number )

//Return this number it is a single digit, otherwise, return the sum of the two //digits
Public static int getDigit( int number )

//Return sum of sumOfOddPlace( long number )
Public static int sumOfOddPlace( long number )
//Return the number of digits in digit
Public static int getSize( long number )

//Return the first k number of digits from the number. If the number of digits in number is less than k, return number
Public static long getPrefix( long number, int k )

Here are some runs of the program

Enter a credit card number as a long integer

4388576018410707
4388576018410707 is a valid credit card number.

Enter a credit card number as a long integer

4388576018402626
4388576018402626 is a valid credit card number.

Infix to Postfix Conversion and The Evaluations of the Postfix Expression.
You are to design and implement and algorithm in Java, to input an Infix expression , convert to a postfix expression and finally evaluate the postfix expression… Follow the examples done during class lectures…
Problem description:
1. We are used to infix notation – ”3 + 4” – where the operator is between the operands. There is also prefix notation, where the operand comes before the operands. A Reverse Polish Notation calculator uses postfix notation, and was one of the first handheld calculators built. At first, it seems confusing, but is very logical once you think about it. Instead of doing ”2 + 3 + 4”, you may do ”2 [enter] 3 [enter] 4 [enter] + +”.
2. You will be implementing a conversion from infix to RPN and then perform an RPN calculator for this assignment.

3. How does an RPN calculator work? It is quite simple in principle. The calculator keeps a stack – a list of numbers. When you type a number and hit ”enter”, it pushes, or appends the number to the stack. So you build up a stack of numbers. Whenever you click an operand, it applies the operator to the top of the stack. In the previous example, it builds a stack like [2, 3, 4]. When you hit the first ”+”, it pops off the top/most recent two elements off the list and ”pluses” them. Lastly, it pushes the result back on the stack, so it looks like [2, 7]. When you hit plus again, it pops off the two elements (so the stack is temporarily empty), adds them, and pushes it back on the stack, so you get [9] .
3 What you need to do
For the first part of this assignment, think about what classes you need. Java has a Stack class for you, but write your own ( do nt use the Java Stack class). Use encapsulation, think about what methods it should have, and call it something like CalculatorStack. Add an option to ”roll” the stack; shift it left or right by one (and the end number rollls) to the other end). Other classes may include Controller, Handler, or SpecialOperationsHandler.
4 Why?
• It’s one of the better assignments I can think of as a teaching tool
• RPN calculators are awesome – they’re far more logical than infix calculators once you get used to them
• You should learn RPN calculators; besides the historical importance, it forces you to think differently. Several example done during class lectures.
The following code below is a sample on how to evaluate the RPN expression …

Design and Implement an Algorithm in Java to solve the following problem in solving linear equations using the Gaussian Elimination method.
Definition:
A system of linear equations can be placed into matrix form. Each equation becomes a row and each variable becomes a column. An additional column is added for the right hand side. A system of linear equations and the resulting matrix are shown.
Sample of linear equations …
3x + 2y – 4z = 3
2x + 3y + 3z = 15
5x – 3y + z = 14
becomes the augmented matrix … (transform the Linear Equation into Matrix form)
x y z Constants
3 2 -4 3
2 3 3 15
5 -3 1 14
The goal when solving a system of equations is to place the augmented matrix into reduced row-echelon form, if possible.
There are three elementary row operations that you may use to accomplish placing a matrix into reduced row-echelon form.
Each of the requirements of a reduced row-echelon matrix can satisfied using the elementary row operations.
• If there is a row of all zeros, then it is at the bottom of the matrix.
Interchange two rows of a matrix to move the row of all zeros to the bottom.
• The first non-zero element of any row is a one. That element is called the leading one.
Multiply (divide) the row by a non-zero constant to make the first non-zero element into a one.
• The leading one of any row is to the right of the leading one of the previous row.
Multiply a row by a non-zero constant and add it to another row, replacing that row. The point of this elementary row operation is to make numbers into zeros. By making the numbers under the leading ones into zero, it forces the first non-zero element of any row to be to the right of the leading one of the previous row.
• All elements above and below a leading one are zero.
Multiply a row by a non-zero constant and add it to another row, replacing that row. The point of this elementary row operation is to make numbers into zero. The difference here is that you’re clearing (making zero) the elements above the leading one instead of just below the leading one.
Definition of pivoting?
The objective of pivoting is to make an element above or below a leading one into a zero.
The “pivot” or “pivot element” is an element on the left hand side of a matrix that you want the elements above and below to be zero.
Normally, this element is a one. If you can find a book that mentions pivoting, they will usually tell you that you must pivot on a one. If you restrict yourself to the three elementary row operations, then this is a true statement.
However, if you are willing to combine the second and third elementary row operations, you come up with another row operation (not elementary, but still valid).
• You can multiply a row by a non-zero constant and add it to a non-zero multiple of another row, replacing that row.
So what? If you are required to pivot on a one, then you must sometimes use the second elementary row operation and divide a row through by the leading element to make it into a one. Division leads to fractions. While fractions are your friends, you’re less likely to make a mistake if you don’t use them.
What’s the catch? If you don’t pivot on a one, you are likely to encounter larger numbers. Most people are willing to work with the larger numbers to avoid the fractions.
The Pivot Process
Pivoting works because a common multiple (not necessarily the least common multiple) of two numbers can always be found by multiplying the two numbers together. Let’s take the example we had before, and clear the first column.
x y z Const
3 2 -4 3
2 3 3 15
5 -3 1 14
Selecting a Pivot
• Pick the column with the most zeros in it.
• Use a row or column only once
• Pivot on a one if possible
• Pivot on the main diagonal
• Never pivot on a zero
• Never pivot on the right hand side
Since there is no one in the first row, we have two options: Either we divide the first row by three and work with fractions, or we pivot on the three and get large numbers. That is the option I’m going to use. I’ll pivot on the three in R1C1. Go ahead and circle that as the pivot element. Depending on your browser, you may see the pivot elements circled in red or just with a * in front of it.
x y z Const
*3 2 -4 3
2 3 3 15
5 -3 1 14
The idea is to make the boxed numbers into zero. Using the combined row operation that could be done by 3R2 – 2R1 → R2 and 3R3 – 5R1 → R3.
The only row not being changed is the row containing the pivot element (the 3). The whole point of the pivot process is to make the boxed values into zero. Go ahead and rewrite the pivot row and clear (make zero) the pivot column.
x y z Const
*3 2 -4 3
0
0
To replace the values in row 2, each new element is obtained by multiplying the element being replaced in the second row by 3 and subtracting 2 times the element in the first row from the same column as the element being replaced.
To perform the pivot, place one finger on the pivot (circled number), and one finger on the element being replaced. Multiply these two numbers together. Now, place one finger on the boxed number in the same row as the element you’re replacing and the other finger in the pivot row and the same column as the number your replacing. Multiply these two numbers together. Take the product with the pivot and subtract the product without the pivot.

x y z Const
*3 2 -4 3
2 3 3 15
5 -3 1 14

To replace the 3 in R2C2, you would take 3(3) – 2(2) = 9 – 4 = 5.
To replace the 3 in R2C3, you would take 3(3) – 2(-4) = 9 +8 = 17.
To replace the 15 in R2C4, you would take 3(15) – 2(3) = 45 – 6 = 39.
To replace the -3 in R3C2, you would take 3(-3) – 5(2) = -9 – 10 = -19.
To replace the 1 in R3C3, you would take 3(1) – 5(-4) = 3 + 20 = 23
To replace the 14 in R3C4, you would take 3(14) – 5(3) = 42 – 15 = 27.

Here’s how the process looks.
x y z rhs
pivot row, copy
3 pivot row, copy
2 pivot row, copy
-4 pivot row, copy
3
pivot column, clear
0 3(3) – 2(2)
5 3(3) – 2(-4)
17 3(15) – 2(3)
39
pivot column, clear
0 3(-3) – 5(2)
-19 3(1) – 5(-4)
23 3(14) – 5(3)
27
Or, if you remove the comments, the matrix after the first pivot looks like this.
x y z rhs
3 2 -4 3
0 5 17 39
0 -19 23 27
It is now time to repeat the entire process. We go through and pick another place to pivot. We would like it to be on the main diagonal, a one, or have zeros in the column. Unfortunately, we can’t have any of those. But since we have to multiply all the other numbers by the pivot, we want it to be small, so we’ll pivot on the 5 in R2C2 and clear out the 2 and -19.
x y z Const
3 2 -4 3
0 *5 17 39
0 -19 23 27

Begin by copying down the pivot row (2nd row) and clearing the pivot column (2nd column). Previously cleared columns will remain cleared.
x y z Const
0
0 *5 17 39
0 0
Here are the calculations to find the next interation. Pay careful attention to the 3rd row where we’re subtracting -19 times a value. Since we’re subtracting a negative, I went ahead and wrote it as plus 19.
x y z rhs
5(3) – 2(0)
15 pivot column, clear
0 5(-4) – 2(17)
-54 5(3) – 2(39)
-63
pivot row, copy
0 pivot row, copy
5 pivot row, copy
17 pivot row, copy
39
previously cleared
0 pivot column, clear
0 5(23) + 19(17)
438 5(27) + 19(39)
876
And the resulting matrix.
x y z Const
15 0 -54 -63
0 5 17 39
0 0 438 876
Notice that all the elements in the first row are multiples of 3 and all the elements in the last row are multiples of 438. We’ll divide to reduce the rows.

x y z Const
5 0 -18 -21
0 5 17 39
0 0 1 2
That had the added benefit of giving us a 1, exactly where we want it to be to pivot. So, we’ll pivot on the 1 in R3C3 and clear out the -18 and 17. Circle your pivot and box the other numbers in that column to clear.
x y z Const
5 0 -18 -21
0 5 17 39
0 0 *1 2
Copy down the pivot row and clear the pivot column. Previously cleared columns will remain cleared as long as you don’t pivot in a row or column twice.
x y z Const
0 0
0 0
0 0 *1 2
Notice that each time, there are fewer calculations to perform. Here are the calculations for this pivot. Again, since the value in the pivot column in the first row is -18 and we’re subtracting, I wrote it as + 18.

x y z rhs
1(5) +18(0)
5 previously cleared
0 pivot column, clear
0 1(-21) + 18(2)
15
previously cleared
0 1(5) – 17(0)
5 pivot column, clear
0 1(39) – 17(2)
5
pivot row, copy
0 pivot row, copy
0 pivot row, copy
1 pivot row, copy
2
And the resulting matrix.
x y z Const
5 0 0 15
0 5 0 5
0 0 1 2
Notice that the first and second rows are multiples of 5, so we can reduce those rows.
x y z Const
1 0 0 3
0 1 0 1
0 0 1 2
And the final answer is x = 3, y = 1, and z = 2. You can also write that as an ordered triplet {(3,1,2)}.
Hopefully, you noticed that when I worked this example, I didn’t follow the hints I gave. That’s because I wanted you to see what happens if you don’t pivot on a one. There was a one, on the main diagonal, in the original matrix, and it would have been better to start there.

Summary
• Pick your pivot element wisely.
• Picking a column with zeros in it means less pivoting.
• Picking a one as the pivot makes the numbers smaller, the multiplication easier, and leaves the non-zero elements in a cleared column the same (less pivoting)
• Pivoting on the main diagonal means you won’t have to switch rows to put the matrix into reduced row-echelon form.
• Do not pivot on a zero.
• Do not pivot on the right hand side.
• Only use a row or column once
• Take the product with the pivot minus the product without the pivot
Special Cases
If you get a row of all zeros except for the right hand side, then there is no solution to the system.
If you get a row of all zeros, and the number of non-zero rows is less than the number of variables, then the system is dependent, you will have many answers, and you need to write your answer in parametric form.

You will implement an algorithm developed by Edsger Dijkstra (1930-2002) to solve the network shortest path problem in this lab.
In addition to the algorithm, there are several other things required to make a program that solves the shortest path problem.
First, it needs an interface that a user can interact with the program so that the program is “userfriendly.”
Second, you need to create a “digital” network in the computer memory that the program can access. In this lab, you will first create the GUI of the program. Then, you will read a text file that defines the network into the computer memory and finally implement the Dijkstra algorithm. You have three lab sessions to complete this lab.
The learning goals for you are to learn how to read from/write to text files and to use List and HashTable to implement the Dijkstra algorithm.
The Dijkstra algorithm, developed a half century ago, finds the shortest path between a vertex and every other vertex on a network graph by constructing and searching a shortest path tree. The algorithm is widely used in modern routing applications that you encounter in everyday life (e.g., on Google map).
The algorithm outlined on the wikipedia website has the following steps. Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.
Let the node at which we are starting be called the initial node.
Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.
1. Assign to every node a distance value: set it to zero for our initial node and to infinity for all other nodes.
2. Mark all nodes as unvisited. Set initial node as current.
3. For current node, consider all its unvisited neighbors and calculate their tentative distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.
4. When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal.
5. If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node, considering all nodes in graph) as the next “current node” and continue from step 3.

Figure 1 and Table 1 show the network on which you will find the shortest paths.

PART 2: FILE I/O
1. First you need to create a text file that defines the network depicted in Figure 1.
2. We will use a simple edge definition format for this lab. Each edge on the network is recorded as having an ID, Node1, Node2, and Length (Table 1).
3. Two-way traffic is allowed on all edges. Use an ASCII text editor (e.g., Notepad.exe) to create the file and save it with a .txt extension name. Please refer to Tuesday’s lecture slides on how to use OpenFileDialog and SaveFileDialog controls to read from/write to a text file.

We can define an abstract data type for single-variable polynomials (with non-negative exponents) by using a list. Let . If most of the coefficients ai are nonzero we could use a simple array to store the coefficients and write routines to perform addition, subtraction, multiplication, differentiation, and other operations on these polynomials.

An array implementation would be adequate for dense polynomials, where most of the terms are present, but if and , then the running time is likely to be unacceptable. One cans see that if arrays were used, then most of the time is spend multiplying zeros and stepping through what amounts to nonexistent parts of the input polynomials. This is always undesirable.

An alternative is to use a singly linked list. Each term in the polynomial is contained int one cell, and the cells are stored in decreasing order of exponents. For instance, the
Assignment

Starting with the class Skeleton, below, Implement the Polynomial ADT using linked lists. You are Not to use the Java LinkedList class, you should “roll your own” list/node data types.
Your project will be graded automatically, so you must make the Polynomial ADT it’s own class. However, you must include an application that demonstrates and tests the key functionality of your implementation. Your write/documentations up should include a discussion of what you used and the documentation html files generated by javadoc.

public class Literal {

// various constructors & accessors (not shown)

double coefficient;
int exponent;

//if you roll your own list, then include “Literal next;”
}

public class Polynomial {

private List terms ; // A list of literals
// if you roll your own, then “private Literal head;”

public Polynomial() {
// constructor to be implemented
}
public void insert term(double coef, int exp){
// to be implemented
}
public Polynomial add(Polynomial rhs) {
// to be implemented
}
public Polynomial multiply(Polynomial rhs) {
// to be implemented
}
public String toString(){
// to be implemented use “^” to signify exponents
}
}

GRADING :
Documentations 10%
Code Style 15%
Functionality 75% ( 15% for each base operation supported +.-./,*,())
Extra Credit :do not require blanks (i.e. allow users to input “5+7*2” as well as “5 + 7 * 2″ ) 5% must be documented – it’s your responsibility to point it out)
Extra Credit : support negative and positive numbers – unary +/- (i.e.allow users to input ” -5 + -7 * +2″ ) 5% must be documented – it’s your responsibility to point it out)
Extra Credit : exponentials (use “^” operator associating right to left) 5% must be documented – it’s your responsibility to point it out)
Extra Credit : modulo (use “%” operator same association as in JAVA ) 5% must be documented – it’s your responsibility to point it out)

Banks lend money to each other. In tough economic times, if a bank goes bankrupt, it may not be able to pay back the loan. A bank’s total assets are its current balance plus its loans to other banks. The diagram in Figure 8.8 shows five banks. The banks’ current balances are 25, 125, 175, 75, and 181 million dollars, respectively. The directed edge from node 1 to node 2 indicates that bank 1 lends 40 million dollars to bank 2.