Lecture 42 (Tychonievich) - Exam Review

Lecture Date: Monday, April 27

See Final Exam Review Guide

Created during questions about recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Exam3Review {
  public static int fib(int i) {
      if (i < 1) {
          return 1;
      } else {
          int x = fib(i - 1);
          int y = fib(i - 2);
          return x + y;
      }
  }

  public static void main(String[] args) {
      System.out.println(fib(6));
      /*
      * fib(6) = fib(5) + fib(4) = 13 + 8 = 21
      * fib(5) = fib(4) + fib(3) = 8 + 6 = 13
      * fib(4) = fib(3) + fib(2) = 5 + 3 = 8
      * fib(3) = fib(2) + fib(1) = 3 + 2 = 5
      * fib(2) = fib(1) + fib(0) = 2 + 1 = 3
      * fib(1) = fib(0) + fib(-1) = 1 + 1 = 2
      * fib(0) = 1
      * fib(-1) = 1
      */
  }
}

Notes created during Q&A



Final Exam Review Guide

General Information

Where and When

All students (except those that have been pre-approved for an alternate time) will take the final Saturday, May 2, 7:00-10:00 PM.
Location - All students should report to their normal classroom (Gilmer 130, Maury 209, or Olsson 009)
The Review Session is Friday, May 1, 6:00-7:30 PM in Gilmer 130.

Conflicts

All conflicts should have been reported to Prof. Sherriff. If you have not received a response, you should contact Prof. Sherriff directly.

What to bring

You only need a writing utensil - pen or pencil. No laptops, calculators, scratch paper, backpacks, books, or anything else should be brought. These items will be left in the back of the room if you bring them. It is also highly recommended to dress in layers. Some classrooms do not have good A/C after hours.

Test Specifics

We are writing the test to be 1 ½ times the length of the previous two tests. So, we are writing the test to take 1 ½ hours, but you will have all 3 hours.

This test will have considerably more multiple choice questions compared to previous tests. However, there will be many questions that involve reading and evaluating code alongside the typical concept-type questions.

Major things you can expect:

  • A “long” coding question, one that asks you to solve a problem and will encourage you to use the various tools you’ve picked up this semester
  • Reading and evaluating methods / code snipits
  • Some questions related to material from the first two thirds of the class
  • Some questions specifically about the final third of the class
  • No questions about JOptionPane or other topics that were covered only in lab
  • No questions regarding the Image Chase or Professor AMAs

Final Third Major Topics

Classes

  • Creating classes
  • Constructor methods - how to create them and why they are important
  • Objects have state and behavior - how does this translate into code
  • Making classes talk to each other (like Department and StudentSchedule do)

Recursion and Algorithms

  • Base Cases - the simplest version of a problem for which you have an answer for
  • Call itself - a recursive method must call itself
  • Change the input - you have to make the method calls approach the base case to terminate
  • Fib sequence
  • Bubble sort vs. Merge sort (idea of algorithms; relative speed; you will not have to code this)
  • Linear search vs. Binary search (idea of algorithms; relative speed; you will not have to code this)

Under the Hood

  • How memory works in Java; the stack and the heap
  • What does it mean for code to be “better?” - speed, easier to read, fewer bugs, quicker to write

Images

  • The concept of a picture and pixel as represented in Java (basically, a 2D array of pixels, where a pixel is a single color point)
  • General complexity of most image algorithms we looked at (n2)
  • General idea of the various image algorithms worked (you will not have to code them; you may have to read them)

Previous Major Topics

The Case for CS

  • Where do we see computing in the world?
  • Why is it important for people to have a basic understanding of computing?

The Parts of a Program

  • Be able to identify the different parts of a program including:
  • import statement
  • public class statement
  • public static void main statement
  • the following special characters: {} for code blocks, () for giving information to methods to use, ; for ending lines, a period for calling a method from an object

Primitive Data Types

  • In general, you should know about the 8 primitive data types and how they are used
  • Most importantly, though, know how the main ones work (int, double, char) since you’ll be coding with them
  • Know how casting works between types (i.e. how we turned a char into an int and back)
  • Review basic math in Java: how things like ++, +=, etc. all work, what integer division does versus double division
  • Test saving values of a different type than the variable you are using - such as what happens when you try to store a double in an int
  • Know some of the important methods in Math that we used, like pow() and sqrt(), and how we called them in the program

Decision Structures

  • Know specifically how if and if-else statements work and how to interpret them
  • Know how the scope of a variable is affected by declaring a variable inside an if statement (or any code block), such as an if statement or a loop
  • Know in general why we should use switch statements in certain circumstances

Loops

  • Know the construction of for, while, and do-while loops
  • Know when and how to use each of these types of loops

File I/O

  • Reading CSV files
  • Know how to read lines from a file and how to split a line on a comma into a String array

Methods

  • You WILL be asked to write methods on this test
  • Know the parts of the method signature and what each part means/does
  • Know the difference between a void return and a method that returns a data type of some kind (and when you would use each)
  • Know pass by value vs. pass by reference and how each is used
  • Be able to handle method level scope as parameters are passed and used in methods

Classes

  • You will be asked to write a class
  • Know what fields and methods are
  • Know what getters/setters are
  • Know why we make fields private and methods public
  • Know how to write default constructors and constructors that take parameters
  • Know how constructors are call, what they do, and why they are important

Arrays / ArrayLists

  • Know how to initialize and use 1D and 2D arrays
  • Know how an ArrayList is different than an array and how you use one

Coding Tips - Your “toolbox”

Throughout the semester, you have been adding to your programming “bag of tools.” There’s not a good way to only ask programming questions specific to one part of what we’ve talked about. You’re going to have to be able to adapt and use different tools together to solve problems. Some tools you should know include (but are not limited to):

To print a literal out to the screen (like asking someone for information):

1
System.out.print("Please enter a number: ");

To print out a literal concatenated with a variable:

1
System.out.println("Hi!  My name is " + name + "!");

where name here is a variable that has some information stored in it.

To read in information from the keyboard, first you have to setup/activate/initialize a Scanner:

1
Scanner keyboard = new Scanner(System.in);

Remember - if you have a red line under Scanner, roll over it and then choose “import java.util.Scanner” from the Quick Fix list!

Now that you have activated the Scanner, use this to actually get what the user is typing:

1
2
3
String name = keyboard.nextLine();  // This is if you are reading TEXT, like a name
int value = keyboard.nextInt();  // This is if you are reading AN INTEGER, called an int in java
double decimalValue = keyboard.nextDouble();  // This is if you are reading A DECIMAL NUMBER, called a double in java

Comparing Strings - To do this, you need to use the .equals function that comes with the String class:

1
2
3
String name = "Mark";
String name2 = "Jose";
boolean sameName = name.equals(name2);

if-else-if statements - This will check each option and have an else statement at the bottom that is the “in case of anything else” option:

1
2
3
4
5
6
7
8
if (x > 5)
   System.out.println("x is bigger than 5!");
else if (x > 0)
   System.out.println("x is bigger than 0!");
else if (x > -5)
   System.out.println("X is bigger than -5!");
else
   System.out.println("x is bigger than.... negative infinity?");

switch statements - Switch statements read in a value and then effectively work like a big if-else statement:

1
2
3
4
5
6
7
8
9
10
11
12
switch (letterGrade) {
   case 'a':
   case 'A':
      System.out.println("Your grade is an A!");
      break;
   case 'b':
   case 'B':
      System.out.println("Your grade is a B!");
      break;
   default:
      System.out.println("Your grade is… something else.");
}

for loops - for loops are great when you know how many iterations you want the loop to run:

1
2
3
for ( int i = 0; i < someValue; i++ ) {
    // Code here that gets run i times
}

Note that the for loop has the initialization of i, the test of i, and then the incrementing of i.

while loops - while loops are good when you don’t know how many iterations you need to go, or for input validation

1
2
3
4
5
String input = myKeyboard.nextInt();
while ( input != -1 ) {
     // do something with input
     input = myKeyboard.nextInt();  // make sure to read the next int in for the next check!
}

do-while loops - do-while loops work just like while loops, except you always run the loop once, since you do the check at the end of the loop, and not the beginning

1
2
3
do {
     // do some stuff
} while ( input != -1 );

files and scanners - opening files and reading them with Scanners (maybe even using split() to read a csv)

1
2
File myFile = new File("list.csv");
Scanner openedFile = new Scanner(myFile);

methods - you should know how to write a method and what every part of the signature/header line does

1
2
3
4
5
6
7
public static String reverse(String str)
// public - anyone can use it
// static - can be called without instantiating the class
// String - return type
// reverse - name of method
// String - type for parameter
// str - parameter variable name

arrays and arraylists - knowing how to create an array or arraylist, adding and removing, and looping over all the items is a very very good thing to know

1
2
3
4
5
6
int[] myArray = new int[10];
myArray[0] = 4;
myArray[1] = 3;
ArrayList<Integer> myArray2 = new ArrayList<Integer>();
myArray2.add(4);
myArray2.add(3);

Things to do to study for the test

No. 1 - Practice your coding without Eclipse!

Let’s be honest - we’ve done a lot of coding in this class so far because that’s really the first step. You’ve got to learn the basics. So, yes, there are going to be coding questions on the test. And, no, you won’t have Eclipse to use!

Are we going to be overly concerned about exact syntax? No, not really, because right now you’re still learning and Eclipse is helping you out a lot. What we’re after is if you’re starting to figure out how to think computationally - can you look at a problem and then figure out what the proper algorithm is to solve that problem using a program.

If it’s really off will we still take off points? Yes, we will, because we still expect you to know that a semicolon comes at the end of each line, etc.

For each coding question, we will most likely give you the class statement and let you write the code inside it. For example, we might give you this:

1
2
3
4
5
6
7
import java.util.Scanner;

public class Question2 {
     public static void main(String args[]) {

     }
}

and let you fill in the rest.

How should you practice? CodingBat.com is a really great idea. The programming challenges from chapters are good. Reviewing assignments and labs is good.

And always remember: a question with at least some reasonable attempt at an answer is always better than a question that’s left blank!

No. 1a - Reading programs!

Writing programs is good, but reading them and understanding them is good too! Be able to trace through code and know what’s happening as you’re working through it!

No. 2 - Review the lecture notes!

If we talked about it in class, then we think it’s important. If we skipped something in the book, then there’s a very good chance we’re not going to ask about it. We only get a limited amount of time to ask you questions on the test!

No. 3 - Listen to the podcasts!

If there’s a topic that has been really tough for you, go back and re-listen to the lecture!

No. 4 - Review the labs and homework assignments!

Go back and look at the (labs and) homework assignments. I think you’ll get a good idea of what types of questions we like to ask. Labs were intended to reinforce ideas in interesting context, but if an idea showed up in lab and never in homework (such as JOptionPane) we didn’t think it important enough to be worth testing.




Lecture 40 (Tychonievich) - Ask Me Anything

Lecture Date: Wednesday, April 22

We had a Q&A today:

How did I learn so many languages?
One at a time (usually)
How much more do I have to learn to be a pro coder?
Nothing?
1110 + 2110 + 2150 (+ 4102) is our coding sequence (2102 etc useful but not required to code)
How much more do I have to learn to be a web dev?
HTML, CSS, Javascript, + one server lang (ruby or PHP or node) – Most people learn these on their own
Courses: Web + Mobile (4720), Web PL (currently a 4501)
BA vs BS (pro and con)
Are you in the college or the school?
Most employers don’t care
How do you create a new language?
public static String compile(String code), with input in one language and output in a different language (one the computer already knows)
What is Java best at?
Making large and maintainable systems
(also becoming one of the faster languages)
How do you count cards?
Gambling is mostly discrete math (and game theory)
What langs are best for making RPGs?
Most graphics-intensive large games are written in C++ (and Lua, asm, Cuda/GLSL, OpenGL/DirectX, …)
Will it rain Saturday?
Yes (but I don’t know which Saturday or where on Earth)
Is X on the test?
Yes (but we don’t ask you to write windowing code, and we don’t ask about specific class activities)
Can I take discrete in Math instead of CS?
No (unless your advisor says yes)
What about a CS focus in major X?
1. good luck getting into CS classes
2. likely won’t be hired by software companies
3. but you almost certainly can code at another company
Why are we using Python next semester?
Python is easy to start with (less to type)
We decided not to have OO (classes) in 1110
Other E-school departments where OK with Python (numpy)
Why is SIS so bad, and why haven’t I written a replacement?
Brittleness: code gets changed so much it stops being easy to change
It would be a lot of work to build a replacement
What is quantum computing?
Doing two things at once using Schrödinger equation
Some things that are “provably hard” with silcone are “easy” with Qcomps… but QComps are hard to build
What is the coolest thing CS has enabled me to do?
Teach 1110
… you can work doing anything
How does the cloud work? What is my political ideology?
I believe in local politics
How does language talk to hardware?
using 1s and 0s encoded as voltages; more in 2330 and 3330
How do you make calculators in minecraft?
Take 3102 (and 2330)

There is no audio for today (I neglected to turn on my recording device).




Lecture 25 (Edwards) - Edge Detection and Image Difference

Lecture Date: Monday, April 20

Today we will talk about how to detect edges in an image and image difference.

We can think of edge detection as figuring out when adjacent pixels change color by a sufficient amount. What’s sufficient, that’s up for use to decide.

Image difference is looking at two pixels of supposedly similar images and seeing if we can spot a difference.

Code & Files:


Lecture 39 (Sherriff) - Images 3

Lecture Date: Monday, April 20

Another day of image algorithms! These are a bit trickier than the last few days…

The algorithms for today are:

  • Edge Detection
  • Image Subtraction

Edge Detection

The edge detection algorithm will show us where the edges of objects are in an image and highlight them. The basic idea is that we can look at every pixel and then see if the pixels next to it are substantially different in intensity. To do this, we will apply a set of convolution matrices called Sobel operators to each pixel. The set consists of two matrices: one that looks for differences on the x axis and one on the y axis.

Masks

The steps of the algorithm are:

  • Convert the original image to grayscale
  • Create an empty image of the same size as the original
  • Then, for each pixel:

  • Convolve the pixel with the x_mask, resulting in an int called gX

  • Convolve the pixel with the y_mask, resulting in an int called yY
  • Compute the square root of the sum of squares of gX and gY called g
  • Based on the value of g, assign the corresponding pixel in the new image to black or white

One example would be if g > 175, make the pixel black and otherwise white.

Edge Algorithm Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public static Picture edges(Picture pict) {
  Picture grayImage = grayscaleImage(pict);
  Picture edgePic = new Picture(pict.getWidth(), pict.getHeight());
  
  int[][] xMask = \{\{-1,-2,-1\},\{0,0,0\},\{1,2,1\}\};
  int[][] yMask = \{\{1,0,-1\},\{2,0,-2\},\{1,0,-1\}\};
  
  for(int row = 1; row < grayImage.getHeight()-1; row++) {
      for(int col = 1; col < grayImage.getWidth()-1; col++) {
          int gx = convolve(grayImage, row, col, xMask);
          int gy = convolve(grayImage, row, col, yMask);
          double g = Math.sqrt(gx*gx + gy*gy);
          
          if(g > 175){
              edgePic.getPixel(col, row).setColor(Color.black);
          } else {
              edgePic.getPixel(col, row).setColor(Color.white);
          }
      }
  }
  
  
  return edgePic;
  
  
}

public static int convolve(Picture pict, int pixelRow, int pixelCol, int[][] kernel) {
  int kernelColBase = pixelCol - 1;
  int kernelRowBase = pixelRow - 1;
  
  int sum = 0;
  
  for(int row = kernelRowBase; row < kernelRowBase+3; row++) {
      for(int col = kernelColBase; col < kernelColBase+3; col++) {
          int kColIndex = col-kernelColBase;
          int kRowIndex = row-kernelRowBase;
          
          Pixel pix = pict.getPixel(col, row);
          int intensity = pix.getRed();
          
          sum = sum + intensity * kernel[kRowIndex][kColIndex];
      }
  }
  
  return sum;
}

Image Subtraction

Image subtraction shows us the difference between two images, highlighting what has changed. The Pixel class provides a method to determine the distance between two colors. We can use this to loop over the images.

Difference Code 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static Picture imageDifference(Picture v1, Picture v2) {
  
  Picture diff = new Picture(v1.getWidth(), v2.getHeight());
  
  for(int j = 0; j < v1.getHeight(); j++) {
      for(int i = 0; i < v1.getWidth(); i++) {
          Pixel p1 = v1.getPixel(i,j);
          Pixel p2 = v2.getPixel(i,j);
          
          if(p1.colorDistance(p2.getColor()) > 20) {
              diff.getPixel(i, j).setColor(Color.black);
          }
      }
  }
  
  
  return diff;
}
Difference Code 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Converts a value between 0 and 1 to a false-color heatmap
 * @param number; 0.0 will be black and 1.0 will be white
 * @return a Color object based on a heatmap white->yellow->red->purple->blue->black
 */
public static Color fromNumber(double number) {
    if (number >= 1) return Color.WHITE;
    else if (number <= 0) return Color.BLACK;
    else if (number > 0.8) return new Color(255, 255, (int)(255*(number-0.8)/0.2));
    else if (number > 0.5) return new Color(255, (int)(255*(number-0.5)/0.3), 0);
    else if (number > 0.2) return new Color((int)(255*(number-0.2)/0.3), 0, (int)(255*(0.5-number)/0.3));
    else return new Color(0, 0, (int)(255*number/0.2));
}

/**
 * Creates an image based on the difference between two other images
 * @param a One image
 * @param b The other image
 * @return An image that it the size of the smaller of the two parameters representing the difference of the two
 */
public static Picture difference(Picture a, Picture b) {
    Picture result = new Picture(Math.min(a.getWidth(), b.getWidth()), Math.min(a.getHeight(),b.getHeight()));
    double maxDifference = 0;
    for(int x = 0; x < result.getWidth(); x += 1) {
        for(int y=0; y < result.getHeight(); y+=1) {
            double diff = a.getPixel(x, y).colorDistance(b.getPixel(x, y).getColor());
            if (diff > maxDifference) maxDifference = diff;
        }
    }
    for(int x = 0; x < result.getWidth(); x += 1) {
        for(int y=0; y < result.getHeight(); y+=1) {
            result.getPixel(x, y).setColor(fromNumber(a.getPixel(x, y).colorDistance(b.getPixel(x, y).getColor())/maxDifference));
        }
    }
    return result;
}