Courses > AP Computer Science 2 >
Konstantinovich
20170216
Trip forms: print and try to get them signed and handed in by end of Monday, or end of today. The deadline is a hard deadline and if you miss it, that is your fault for waiting until the last minute! Quiz the Wed after break. Extra Credit: Make a folder EC01/ on your repo. Place a copy of your extra credit KnightBoard.java in this folder if you would like it to be graded. You must have an additional public method: solveFast(). If you do not have EC01/KnightBoard.java , and the method is not named solveFast(), you will not get credit. You must find a tour using a much faster method than plain brute force. I will test on boards with sizes between 16 and 50. Goal: Reminder: Files are useful. Checked vs. Unchecked exceptions. import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class ReadFile { public static void main(String args[]) throws FileNotFoundException { //instead of a try/catch, you can throw the FileNotFoundException. File infile = new File("input.txt");// can be a path"/full/path/to/file.txt" Scanner inf = new Scanner(text); int lineNumber = 1; while(inf.hasNextLine()){ String line = inf.nextLine(); System.out.println(line); } } } Place this maze into a text file, and read it into Maze1.txt #################################### # # # # # # #E# 
20170214 HW03 + Terminal Things
Full day trip to NYU, where you listen to several interesting lectures by NYU CS professors. The topics are interesting, and food will be provided. It is not open to Seniors (sorry...) If you are and interested JUNIOR please fill out this form: Your goal is to write a knight's tour solver. This is due the Tuesday after break. Place it in your git repo: 03*/KnightBoard.java KnightBoard has 2 public methods and a constructor, a private helper is needed as well. public KnightBoard(int startingRows,int startingCols) public String toString() //blank if you never called solve or when there is no solution public void solve() private boolean solveH(int row ,int col, int level) // level is the # of the knight *Use the following format for toString: (THESE ARE NOT VALID SOLUTIONS, They JUST TO DEMONSTRATE FORMAT) Single spaces between numbers, but leading spaces on single digit numbers: 1 2 5 3 4 6 7 8 9 When there are two digit numbers (rows*cols >= 10) Put a leading space in front of single digit numbers: (spaces replaced with _ to show the difference) _1 _2 15 _6 _3 _4 _7 11 _8 _9 10 12 13 14 _5 16 So it looks like this: 1 2 15 6 3 4 7 11 8 9 10 12 13 14 5 16 *I will not be testing boards that have a rows*cols that is >= 100, as the program would take a long time to complete. You only have to step on every square exactly once, starting on the 1st square counts. You do not have to come back to where you started. This is called a closed tour (it is a loop that is closed) and closed tours take much longer to find (potentially). From Wikipedia: Any m × n board with m ≤ n, a closed knight's tour is always possible unless one or more of these three conditions are met:
This also means an open tour is certainly possible when none of those are true!!!!! Your solve should work on 7x7 easily. Here is something as a bonus:

20170208 HW02
HW02 on github: (due Tuesday!!!!! 8am) 02NQueens/QueenBoard.java You should not write any code until you:  write pseudocode written to outline your solving method. (the recursive helper not the wrapper)  have 2 of your classmates read over your pseudocode public class QueenBoard{ private int[][]board;private int solutionCount;} Discussion on what you need to have working requirements: *see below* Optional: Animation of nqueen solver (do this after you get the homework!) You need a few public methods: public void solve()  find the 1st solution it can and stop, this updates the board to be displayed in toString() public void countSolutions()  look for all solutions, and update the instance variable solutionCount to reflect the number found. public int getSolutionCount()  return the instance variable solutionCount, which should be 1 if the countSolutions was never run. public String toString()  when solve was run, this shows you the solution, otherwise a blank board. Constructor: QueenBoard(int size) Private methods you will want to test before writing other parts of the code: addQueen(r,c) removeQueen(r,c) public class QueenBoard{ private int[][]board;private int solutionCount; public QueenBoard(int size){ board = new int[size][size]; } /** *precondition: board is filled with 0's only. *@return false when the board is not solveable. true otherwise. *postcondition: *if false: board is still filled with 0's *if true: board is filled with the *final configuration of the board after adding *all n queens. Uses solveH */ public boolean solve() { return solveH(0); } private boolean solveH(int col){ return false; } /** *@return the number of solutions found, or 1 if the board was never solved. /**toString *and all nunbers that represent queens are replaced with 'Q' *all others are displayed as underscores '_' */ public String toString(){ return ""; } } N queens number of solutions:
"Adequate"
} 
20170207 *HW
Homework: FILLOUT WITH NEW REPO: "The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general nqueens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 or n=3." A top down design of an NQueen solver. Top Down design: Many of the functions and programs you write are simple enough to complete without designing them. This is because you can easily understand the whole algorithm. A formula, or a simple set of if statements don't seem to require a design. As you write more complex code, you cannot understand the whole algorithm/process AND all of the consequences of the code you need to write all at once. This is why it is a good idea to DESIGN your program rather than just hack it together by writing code until it works, even though it may seem like a waste of time for now. Your design will be in plain English, which makes it faster and easier to write than actual code. It is also easier to find errors in your logic, and faster to fix than after you have coded the algorithm. (This is why rubber ducky debugging works because it forces you to state your algorithm in plain English) Start with the big ideas and no code at all. After you do that you can write pseudocode and use highlevel* function calls then refine each part as you plan it. *high level meaning, placeholder methods that describe complex things, rather than the code to do the complex things: swapParts(list); x=getNextElement(); addQueen(x); Afterward, you can think about how to represent the data, and how you will implement the code you planned. 
20170206 HW01
Goal: Basic Recursion + Getting stuff done! Lab + Homework: Deadline is Wed Feb 8th 8am. I will clone everyone's repo by then. I will grade and post results. No late submissions will be graded without prior permission/approval. Discussion and working on Recursion2 problems. 1.0 BEFORE WE START: How do you compare floating point values for equality? Why is this different than integers? 1.1 You are writing a class called Recursion for grading purposes this must be exact. IMPORTANT NOTE: The methods will be static. You are solving 1 problem recursively: sqrt public static double sqrt(double n); throws an IllegalArgumentException when n < 0. Now to think a little: There is a formula to calculate square root Guess any number for the sqrt of n. (like n/2, or even 1) n = 100 guess = 1 Make a better_guess this way: better_guess = ( n / original_guess + original_guess) / 2 guess = 50.5 (then do it again, then do it again) guess = 26.24009900990099 guess = 15.025530119986813 guess = 10.840434673026925 guess = 10.032578510960604 guess = 10.000052895642693 ... Notice how fast this converges onto the correct value (10). ** You MUST make a helper function because you need a function with two parameters (n, and the guess) even though the sqrt function only takes 1 parameter. What is a good base case? How do you know you found the square root? 1.2 Make your class matches the following: public class Recursion{ public static String name(){...}; public static double sqrt(double n){...}; } Note: name(): return your name: format: "Last,First" as it appears on your school documentation without spaces, or special symbols. 2. Need to study longer? (You are doing it wrong) Let me end with a link to a video about how to study for less time and get more out of it. Even if you only watch the first 510 minutes you will be much smarter. You can watch as little or as much of this video as you want, I won't ever check... but you won't increase your GPA either. If this video helps you do better please let me know! This pairs nicely with every article about sleeping more to remember things better... 
20170203
Override a method > replace a superclass method with a child class by naming it the same (e.g. toString() ) Polymorphism: objects and methods can have more than one form objects: If shark extends fish, a shark can be treated 3 different ways because a shark isa fish, a shark isa shark, a shark isa object functions: By overloading the methods they can have several forms. e.g. foo(int x) foo(int x, int y) foo(char c) Recursion1: count8 Recursion2: groupSumClump splitArray splitOdd10 split53 
20170201
Goal: Miracles (recursion) Yesterday we talked about:
Today We will develop some algorithms together: sumDigits(int n) isPrime(int n) countx() Homework: 1. Make a new github repo for this semester's homework. MKS22XHW or something similar. You will make a new folder on the TOP LEVEL OF YOUR REPO* for each homework starting with a 2 digit homework number. *Do not make a folder and put all of your homework assignments into it. The repo IS your "folder". MKS22X 01Blah 02Bl 2. Complete the recursion1 problems on codingbat: changeXY, array6, allStar, countPairs, StringClean, nestParen 
18 of 8