ICS4U Grade 12 – Computer Science – Exam

Grade 12 – Computer Science

 

Object Oriented Programming – A Guide to Programming in Java Ch 8

 

Intro

 

  • Objects are defined classes where different tasks can be grouped into classes, and distinguished with objects.
  • Object oriented programming is highly reusable where objects can be copied and used for multiple tasks at hand
  • The programs become modular where pieces are put together to accomplish a greater task
  • “Messages” can be passed between methods and objects to tell it to perform different methods.
  • State: the data an object stores determine it’s state
  • Behavior: the actions and communications which are defined by methods
  • Objects can be used to model real world things in a computer program
  • Objects are instance of a class
  • Class: a data type that defines variables for the state of an object and methods for an object’s behavior
  • Encapsulation: objects can hide data from things happening outside the class.
  • Client Code: application that uses one or more classes. Usually the file that has the main method

 

Writing a class

  • Class declaration: consists of the access level, keyword “class”, and the class name.
    • Class name’s first letter of every word is capitalized
    • Names are usually a noun and contain no spaces
  • Access Level: the restrictions when accessing this class or classes
    • private: makes this variable only accessible within it’s own object. Different private variables can be used for each object.
    • public: makes the class available to anywhere
    • static: makes the variable the same and accessible throughout the entire class
  • Class body: can have variables, constructors, and methods
  • Constructor: used to initialize variables in a class.
  • Members: variables and methods in a class are the members of the class

 

  • Accessor Methods: methods used to determine the value of a variable
  • Modifier Methods: used to change values of variables
  • Helper Methods: private access level classes called from within a class to help accomplish tasks.

 

Constructors

  • Constructors: are run once an object is created to initialize variables
  • Upon creation, objects can pass variables into the class by using overloading constructors
  • A class with the same name as the class can set variables, or accept parameters as well.
    • The constructors are defined as shown: public <class name> { }, without the need of “class” keyword, as with any other class. Constructors do not return values.
  • Different constructor methods with different parameters can be used to overload it.

 

Instance and Class Members

  • Instance Variable: are variables which has it’s own copy in every object.
    • Declared with private <variable type> <variable name>;
  • Class Variable: are variables where one copy is maintained for all objects
    • Declared with private static <variable type> <variable name>;

 

  • Instance Methods: require an instance of that class in order to run
    • Declared with public <return type> <name>(<parameters>);
    • Called by <object name>.<method name>(<arguments>);
  • Class Methods: do not require an instance of that class to run (or from class itself)
    • Declared with public static <return type> <name>(<parameters>);
    • Called by <class name>.<method name>(<arguments>);

 

The Object Class

  • Superclass: superclasses can be referred in sub classes.
    • Object Class is a super class of all classes
    • Methods in the Object Class can be called in subclasses
    • Sub classes can Inherit super classes by calling them

 

  • Object Class has 2 methods which can be used
    • equals(Object obj) – returns true of obj is equal to the object
    • toString() – returns a String that represents the object

 

  • Overriding: taking a method from a superclass and redefining it in a subclass
    • Object class (equals() for example) with the arguments as the object
      • public boolean equals(Object c) {
    • Make a variable from the class (circle) and object case the argument to that type
      • Circle testObj = (Circle)c;
    • Make class do it’s thing and return as necessary

 

  • Println(): the toString can be used to tell what println what to print
    • When println(<object>) is called, the toString() will run and output whatever toString makes it do.

 

has-a relationship

  • A class can make objects of other classes, tying together multiple class files
    • Meaning an object can have a variable that’s an object of another class
    • Together they can get tasks done more effectively and store information more organized
    • this: used to distinguish between a parameter and a member variable
      • method parameter and member variables in a class might have the same name
      • in such case, the member variable is referred to as “this”
        • If a class variable’s name was “balance” and a class (getBalance) decided to use to have parameter of “double balance”, then you can refer to it in getBalance as “this.balance ..” referring to the “double Balance” in the parameters of getBalance

 

 

Grade 12 – Computer Science

 

Polymorphism and Inheritance – A Guide to Programming in Java Ch 9

 

Intro

 

  • Inheritance extends on an existing class
  • Polymorphism is something you can do to classes that are being inherited
  • You might want to extend a class by adding more specific items into the object
    • A car class might be extended to “BMW” class where it has BMW specific methods and variables
    • Or a Circle class might be extended to “Disk” and accepts the input of height.

 

Inheritance

  • Inheritance: when you extend classes from a “super class” to make it do more specific things
    • “allows a class to define a specialized type of an already existing class”
    • Is-a relationship: an extended class “is a” type of another class
      • BMW “is a” type of a car class. Disk “is a” type of circle class.

 

  • Implementation:
    • extends: a keyword you must use to declare a “sub class”
      • this keyword will make it refer to the super class
      • public class <name> extends <superclass_name> { … }
    • base class: or “super class: is the class which this sub class is based on
    • derived class: or “sub class” often contains overridden methods or new data from the base class
    • super: is a keyword used to access methods in the base class
      • Ex. super(r) from the BMW class will call the constructor of the super class (car) , and pass variable r into it.
    • Members that are private cannot be accessed by derived classes
      • Hence, accessor methods are used to get values (ie getWeight(), getRadius())
    • Inherited Methods can be called directly.
      • If M3 is the object of BMW class, and you call carStart() from client code. If BMW class doesn’t have it’s own carStart() method, but Car class does, since BMW inherited the Car class, the client code doesn’t care and still executes carStart().

 

Polymorphism

  • Polymorphism: an OOP property where objects have the ability to assume different types.
    • Polymorphism is based on inheritance
    • Since a subclass is derived from a super class, a super class object can reference an object of the subclass

 

 

ie Car honda;

BMW 320i = new BMW(<arguments>);

honda = 320i  //honda now references 320i

  • Since BMW is inherited from Car class, any object made from Car can be “morphed” into another object made by a subclass of Car, in this case, a BMW 320i object.

 

  • Overridden methods from the super class can be called from the sub class.
    • From the earlier example, the method toString() originally in Car was overridden in BMW. Even though honda was made by Car class, then later morphed into a BMW object, I can still call the toString() method overridden by BMW.

 

Abstract Classes

  • Abstract Classes: are used to model abstract concepts.
    • For example, a “vehicle” is an abstract object, you cannot have a “vehicle” vehicle. You can have cars, trucks, BMWs, Hondas which are in the form of vehicles.
    • Abstract classes are instantiated but do not represent the objects
    • They only have general details and actions of a type of object
      • Example: a Vehicle abstract class may only have number of wheels, or number of seats. Later, another class, like Car, can inherit the Vehicle class and add more details like colour, make, brand, etc.
    • abstract: Abstract classes are declared with abstract keyword
      • All abstract classes are intended to be inherited
      • Only public members of abstract classes are visible to derived objects
        • abstract class <class name> { .. }
    • Abstract Methods: methods declared with abstract keyword but contains no body
      • They are meant to be overridden in derived classes
        • abstract <return type>  <method name>();

 

Interfaces

  • Interface: a class with method declarations but no implementations
    • Interfaces cannot be inherited, they must be imported
    • Interfaces always has abstract methods
    • You can only implement an interface class, but it is not part of the hierarchy
      • <access level> interface <name> { .. methods .. }
    • Comparable Interface: one example of an interface in the java.lang package
      • CompareTo(Object obj) : returns 0 when obj is same as the object, a negative integer if obj is less than the object, and positive integer if obj is greater than the object.
      • A class must implement each method defined in the interface
    • Multiple Interfaces: A class can have multiple interfaces
      • When more than 1 interface is implemented, the interface names are separated by commas in the class declaration.

 

Grade 12 – Computer Science

 

Arrays – A Guide to Programming in Java Ch 10

 

Declaring Arrays

 

  • Arrays: are data structures that can store many of the same kinds of data together at once.
  • Arrays start at index zero and has the declared amount of elements.
  • Array Element Index: the place at which an array element is located
  • Declaring arrays
    • <type> [][] <name> = new <type> [<num1>][<num2>]
    • Square brackets are used to access certain places in arrays
  • Initial Array Values: for int arrays, all initial values are 0. For String arrays, all initial values are null
  • Declaring arrays by initializing elements
    • <type>[] <name> = {<element1>, .. <elementn>};

 

Using Arrays

  • Access elements using the index number in square brackets
    • <name> [<index>]
  • Change elements by making that index equal something
    • <name> [<index>] = <value or a variable>
  • Traversing: using a for loop to go through an entire array and search / print out elements
    • these for loops start at 0 and goes until it’s one less than the length of the array
    • Array Length: can be obtained by <array>.length;
  • For-each statement: this type of loop can do the traversing for you
    • for (<type> element : <array>) {

<statements>;

}

  • The for-each prevents the exception ArrayIndexOutOfBoundsException error
  • This cannot be used if you want to know the index at which a value is located

 

Array Parameters

  • Arrays passed to a method can be entire array or element of the array
    • public static void testMethod( int[] array, int aNum) …
    • Square brackets are used to signify that this is an array
  • Passed arrays are a mere reference to the original data type
  • Passing single elements in an array will not be referenced, the actual value will be passed

Arrays with Meaningful Indexes

  • Using arrays you can reference certain indexes as a value then add frequency.
    • For example, in a dice rolling app, the value at index [1] can hold the frequency each time 1 was rolled by the dice.
  • Offset array Indexes: when you are using indexes for huge numbers like frequency of years from 1990 to 2001, it doesn’t make sense to make an array 2001 in size but only use the last 100. So you can offset it by saying 1990 is index 0. To do this, when accessing the array, you simply subtract it by the amount you offset.

 

Characters and Arrays

  • Strings cannot be manipulated as a set of characters, but they can be converted into a char array where each letter is stored in it’s own index.
  • the charAt(int index) method can return the char value at the letter position index.
  • toCharArray() method converts each character in the string to char and places it in the char array.
  • Unicode: each letter and symbol is assigned a digital representation called Unicode.
    • 16 ones and zeros are used for each letter.
    • A letter in the char variable is stored as Unicode representation of the letter
    • Lower case letters have higher values in Unicode than upper case letters.
    • You can type cast char to any number and it will return the Unicode equivalent of that character.

 

Searching an Array

  • Linear Search: will look at one array element at a time until a specific value is found or after entire array is searched.
    • If the element is found, the search will stop at that spot

 

2D Arrays

  • 2D arrays: can store a table of information with 2 dimensions
  • Declare them using 2 square brackets
    • <type> [][] <name> = new <type> [<num>][<num>];
  • Access 2D arrays using their position in the square brackets
  • The coordinates follow X Y coordinates and index starts at zero
  • To find length, you do:
    • array.length;   to find the length for the horizontal row
    • array[0].length;   to find the length for the vertical column

 

ArrayList Class

  • ArrayList is a collection of related objects stored as a single unit.
    • Java has a collections framework and ArrayList is one example of such framework
    • ArrayList Class includes methods for adding, deleting, or finding elements
  • add(int index, element); : inserts element at index position and moves everything to the next position in the array
  • add(element); :inserts the element at the end of the array
  • get(int index); :returns the element at index position
  • indexOf(obj); :returns the index of the first element matching obj using the equals() method of the object’s class to determine equality between the elements
  • remove(int index); :removes the element at index position in the array and moves everything up one position
  • set(int index, element); :replaces the element at index with element.
  • size(); :returns the number of elements in the array
  • Dynamic Array: ArrayList is a dynamic array because elements can be added and grow or shrink as the applications needs it.
  • The equals() method is used in the indexOf() ArrayList method because objects are stored in ArrayList, not primitive types
  • Declaring ArrayList
    • ArrayList<String> name = new ArrayList<String>();
    • Type Parameter: the <String> part tells the compiler that ArrayList contains String objects.

 

Wrapper Classes

  • Since primitive data types cannot be stored in ArrayList, Integers or Doubles must be wrapped into objects before they can be compared.
  • Similarly, they must be converted back to primitive data types when retrieving arrays
  • To do that, we use Wrapper Classes in java.lang.Integer or java.lang.Double.

 

  • compareTo(Integer intObject); : returns 0 when the integer object value is the same as intObject. A negative int is returned when the Integer object is less than intObject and a positive int is returned when the Integer object is greater than intObject.
  • intValue(); :returns the int value of the Integer object.

 

  • To take advantage of these classes, the ArrayList type parameter must be Integer or Double.

 

AutoBoxing and AutoUnboxing

  • Using wrapper classes to wrap and unwrap elements can be cumbersome and make codes extremely long
  • Java includes autoboxing and autounboxing.
  • These will eliminate the need for extra code, once the ArrayList is set to the right type parameter, autoboxing and autounboxing will take care of the wrapping for you.

 

Grade 12 – Computer Science

 

Graphical User Interface – A Guide to Programming in Java Ch 11

 

Intro

  • GUI are programs written with a visual interface using components such as frames, panels, labels, buttons, combo boxes, and text field
  • Event Driven Application: clicked actions done on the GUI will create an event
  • Event Handler: is a method run when the event is done

 

Swing Package (javax.swing.*)

  • Swing package holds the APIs used for creating GUIs
  • Frame: is a window with a border, title, and buttons for minimizing, maximizing and closing the frame.
    • It is a top level container for the GUI, which holds and displays the components in a content frame
    • JFrame in the javax.swing.package package
    • setDefaultLookAndFeelDecorated(boolean): decorates the window with buttons
    • setDefaultCloseOperation(class_constant): tells the frame what to do when the user hits the close button, usually JFrame.EXIT_ON_CLOSE
    • getContentPane(): returns the pane object
    • setContentPane(JPanel object): connect a panel to the frame
    • Pack(): sizes the frames so all components are at or above their preferred sizes
    • setVisible(boolean): displays the frame when true
  • Panel: a frame uses a pane to hold GUI components. JPanel is one way of adding or removing components
    • Add(Component GUIcomponent): adds a the component onto the pane, which also returns the index of the component in the pane
    • Remove(int index): removes the component at index value
  • Label: class for creating labels that can display text values
    • JLabel(string): constructor
    • JLabel(string, align_constant): creates JLabel objet with text and aligment LEADING or TRAILING aligning left or right respectively
    • setText(String): change the text of the label
  • Swing applications run it’s own thread dispatched in the main() method
  • Thread: a process that runs sequentially from start to finish.
    • GUIs should be invoked from an event-dispatching thread to ensure that each event-handler finishes executing before the next one executes.
  • Buttons: a clickable element which executes a task
    • JButton(String): creates a button with string as name provided
    • setActionCommand(String cmd): sets the name of the action performed when the button is clicked to cmd
    • getActionCommand(): returns name of action that has been performed by the button
    • addActionListener(object): adds object that listens for the user to click this component

Handling Events

  • Listener: is an object that listens for action events
    • Listeners require the java.awt.event.* import
    • When an action occurs, it executes the event handler named actionPerformed()
    • actionPerformed(ActionEvent event): has an ActionEvent parameter passed by the GUI when an event occurs
    • Action command: a string describing an event
  • Using this for the listener object will refer to the GUI’s object itself
  • To implement the ActionListener, we add implements ActionListener to the class declaration and then defining actionPerformed() method.
  • A constructor for the class will define and construct the buttons
  • A listener ActionPerformed method is created to handle the button actions
  • The actionPerformed will look for the event using the event.getActionCommand(); method

 

Controlling Layout

  • Layout: refers to the arrangement of components in the GUI
  • Borders: are invisible, spaces that can be used to add padding around a component to give it distance from other components
  • Layout managers: determines the order of components on a content pane
    • FlowLayout: places them one next to another in a row, when a row gets too long, a new row is started (default)
    • BoxLayout: places components one after another in a column
    • GridLayout: places components into a grid of rows and columns
      • GridLayout(number of rows, number of columns, pixels between columns, pixels between rows)
      • GridLayout requires the java.awt.* statement
  • Alignment: refers to the placement of a component within a layout
    • setLayout(): used to specify a layout for the contentPane. BoxLayouts objects require arguments for arrangements. Vertical line layouts use PAGE_AXIS
    • setBorder(): specifies borders for the pane. BorderFactory object can specify different kinds of borders. createEmptyBorder() used for empty borders
    • setAlignment(): specifies the vertical alignment of the elements

 

Getting Input from user

  • Text Fields: allow users to enter information and then be prompted to submit the data
    • JTextField(int col): constructor for a text field
    • JTextField(String, int col): creates a text field with a default text in the field
    • getText(): returns the string containing in the text in JTextField
    • addActionListener(object): adds an object that listens for the user to press the enter key
  • All data retrieved from the text field are Strings, you need to convert them to double or integer if you need it
    • java.lang.Double
      • parseDouble(String): returns double value of String
      • toString(double num): returns string representation of num
    • java.lang.Integer
      • parseInteger(String text): returns int value of the string
      • toString(int num): returns string representation of num

 

Combo Boxes

  • Combo boxes offer users to select from a limited set of choices
  • JComboBox
    • JComboBox(Object[] items): constructor for combo box with an array of choices
    • setSelectedItem(int index): makes the item at index the selected item
    • getSelectedItem(): returns the String corresponding to the selected item
    • setEditable(boolean): allows text to be typed in the combo box
    • addActionListener(Object): adds object that listens for user to select an item from the component’s list
  • To handle events, you must have an event object casted to a JComboBox and then getSource(). Then you must retrieve the string in the combo box selected
    • JComboBox comboBox = (JComboBox)event.getSource();
    • String itemName = (String)comboBox.getSelectedItem();
    • These 2 lines are implemented in the actionPerformed method

 

Colours

  • Color class is located in the java.awt.* package that allows you to change the colours of GUI elements
    • setBackground(Color.constant): sets the background color of a component to constant from the Color class
    • setForeground(Color.constant): sets the foreground color

 

Images

  • Images can be added onto a JLabel or JButton element in the form of GIF or JPG
    • JLabel(ImageIcon pic): creates JLabel object with that picture
    • setIcon(ImageIcon pic): sets the JLabel with that picture
    • Similar for buttons, JButtons have JButton(String str, ImageIcon pic) to have picture and text

 

Using Nested Classes to Handle Events

  • Sometimes with many buttons, you might need multiple buttons to handle all the events
  • In such circumstances, a class can be created inside a class to handle those events
  • When declaring the class inside, be sure to implement ActionListener as well as refer to that class when you are making buttons/event GUI elements

 

 

Grade 12 – Computer Science

 

Files and Exceptions Handling – A Guide to Programming in Java Ch 12

 

What is a File?

  • Files: are data stored into a computer’s memory that remains persistent. These files will not disappear when the computer is powered off.

 

The File Class

  • The file class, part of java.io package creates object that represents a file
  • It can create a new file, test existence of a file, or delete a file
    • File(String f) – creates a new File object and refers to it as file f
    • createNewFile() – creates a new file with filename specified in constructor (IOException and return false if file cannot be created, true of created)
    • delete() – deletes that file, returns true of successful
    • exists() – returns true of a file exists
  • For paths in a filename, escape sequence (\\) should be used to show backslashes

 

Handling Exceptions

  • Exceptions are errors affecting program execution
  • If they are not handled, then the program will terminate
  • Although usually the program will end anyways, you can greet the user with a better error message.
  • try – catch – finally statement can be used to write an exception handler
    • try contains statements which might generate an exception
    • catch will execute statements if the exception in the parameter occurred
      • Separate catch clauses should be used for each type of exception
    • finally is optional and will execute regardless of what happens in the try-catch clauses
  • IOException throw: certain methods can throw exceptions when there is an error
    • createNewFile() throws an IOException exception if it cannot create a new file
  • An exception is an object of the Throwable class
    • These objects have getMessage() member that returns string containing information about the error
    • err stream is used to display error messages

 

The File Streams

  • File Stream keeps track of file position when the stream processes charactors
  • Sequential File Access is performed to read one character after another or 1 line after another
  • A stream has a sequence of characters:
    • Cr followed by Lf means its a line terminator
    • -1 is the end of file

 

FileReader and BufferedReader Classes

  • FileReader create the input file stream.
  • BufferedReader is used to read text from the stream
  • FileReader Class
    • FileReader(File fileName) – creates file stream for File object, throws FileNotFoundException if file does not exist
    • close() – closes the input file stream. Throws IOException if it cannot be closed
  • BufferedReader Class
    • BufferedReader(Reader stream) – creates a buffered-input stream from stream. Reader is a FileReader superclass.
    • read() – reads a single character from the input stream. This method throws an IOException exception if stream cannot be read
    • readLine() – reads a line of text from the input stream. This method throws IOException exception if it cannot be read.
    • close() – closes the input file stream. Throws IOException..

 

Processing Numeric Data

  • Files on a disk are a set of characters, even if they are numeric data.
  • Double Class (java.lang.Double)
    • parseDouble(String text) – returns the double value in the String text
  • Integer Class (java.lang.Integer)
    • parseInteger(String text) – returns the integer value in the String text

 

FileWriter and BufferedWriter Classes

  • FileWriter and BufferedWriter classes are used together to write to a file
  • FileWriter creates an out stream
  • BufferedWriter sends the text to the stream
  • FileWriter class
    • FileWriter(File fileName, boolean append) – creates output file stream for File object. If append is true, it will continue writing to the existing file. Otherwise, it will be overwritten. Constructor throws IOException. New file will be created if no File exists
    • close() – self explanatory
  • BufferedWriter class
    • BufferedWriter(Writer stream) – buffered writer stream from stream writer
    • newLine() – writes new line character to output stream. IOException if ..
    • write(String str) – writes str to the output stream, method throws IOException..
    • write(char c) – writes c to output stream, method throws IOException..
    • close() – self explanatory

 

Object Serialization

  • Object Serialization: writing objects to a file
  • The class information about an object is written out to a stream
    • If a class uses another class, this information is also written out
  • Object Deserialization: when objects are retrieved from an object
  • FileOutputStream and ObjectOutputStream are used to write objects to files
  • FileInputStream and ObjectInputStream are used to read objects from files
  • FileOutputStream
    • FileOutputStream(File fileName, boolean append) – creates an output file stream. Same rules apply to FileReader.
    • close() – self explanatory
  • OutputObjectStream
    • ObjectOutputStream(FileOutputStream stream) – creates object stream from stream
    • writeObject(Object obj) – writes information to the output stream
    • writeInt(int num) – writes num to the file stream
    • writeDouble(double num) – writes a double to the output stream
    • close()
  • FileInputStream
    • FIleInputStream(File fileName) – creates input stream for FIle object
    • close()
  • ObjectInputStream
    • ObjectInputStream(FileInputStream stream) – creates an object stream from stream. Throws IOException exception if stream cannot be read
    • readObject() reads an object from the input stream. Throws a ClassNotFoundException if the stream cannot be read or cannot be deserialized
    • readInt() reads an int from the input stream.
    • readDouble() read a double from the input stream
    • close()
  • Serializable Interface: classes that make objects waiting to be written to objects need
  • to implement the Serializable interface
    • The interface needs no implementation, just that it needs it to write it
  • Objects read from readObject() requires casting to the appropriate type

 

 

Grade 12 – Computer Science

 

Advanced Algorithms – A Guide to Programming in Java Ch 13

 

Selection Sort

  • Sorts by finding the lowest number and swapping it with first
  • Next, it will look at the list from the 2nd number onwards and look for the lowest number from there
  • It will find the smallest number from 2 till the end, and swap it with the 2nd number
  • Nested for-loops are capable of doing this method, without the use of recursions

 

Sorting Objects

  • Using the equals() or compareTo() implemented in objects, you may compare objects
  • Objects may also implement the Comparable Interface to use to compare
  • Interfaces cannot be used to instantiate a class but interfaces can be used as a data type.
  • Interface data type can refer to any class it implements
  • This polymorphic behavior can allow a generic sort of any list of objects which have the Comparable Interface

 

Insertion Sort

  • Starts sorting with the first 2 items in a list, shifts them to the correct place
  • The third item will be compared and shifted up to where it fits
  • Each element is compared with all the elements before it to see where it should fit

 

Recursion

  • Recursive Call: are methods that can call itself.
  • A recursive method calls itself but with different parameters each time
  • Recursion can be used to solve problems requiring smaller versions of the same problem, then combining the results
    • For example, if we wanted to use recursion to find the value of a number raised to a power, we could have a recursion call that reduces the number into x * xn-1 each time until it reaches 1 and adding all the results.
    • 23 is 2* 22 + 2* 21 + 1 which is 8
      • Each 2* 23 is a new call in the recursive method

 

Mergesort

  • Selection short is inefficient for large arrays
  • Merge sort takes a “divide-and-conquer” approach in sorting numbers.
  • It cuts the array in half, and cuts the halfs in half and so on to to sort smaller sections
  • Mergesort will then recombine all of the elements together into one large sorted array
  • Mergesort has a recursive method that keeps calling itself to sort the halves
  • A temporary array is needed to store the items moved from two sorted arrays into the items array

 

Binary Search

  • Binary search uses a sorted list to quickly look for the location of a value
  • It too also takes the divide and conquer approach
  • It cuts the array in half and determines, by comparing the target value with the middle, beginning, and end value to see which half the value is located in
  • It then takes the half and does the same thing to cut that in half
  • Eventually, it will find the number on one of the halves
  • This saves time because it only looks at half of the values at a time, not needing to go through the entire array

 

Depth-First Searching

  • Solves problems, not sort lists
  • A problem is solvable with DFS If it can be modeled by a tree diagram
  • It looks deeper and deeper into the problem, in smaller chunks, until it finds the solution (uses recursive methods)
  • Each time a recursive method is called, it does the same actions differently with slight modifications to get deeper into the problem.
  • Can be used for solving mazes, creating schedules, or possible plays in a game