Tom Quayle

Algorithms: Searching

Slide Duration:

Section 1: AP Computer Science
About the AP Computer Science Exam

17m 11s

Intro
0:00
0:16
Java Editor
0:45
The AP Computer Science Exam
1:30
1:31
Final Score
1:49
College Credit
2:08
Format of AP Exam Questions
2:20
Two Sections
2:26
Section 1
2:31
Section 2
2:40
Scoring
3:23
Multiple Choice Questions
3:57
Example
4:04
5:06
Keep in Mind
6:21
6:58
Evaluate Each Roman Numeral Separately
7:08
Example Multiple Choice Question
7:34
Java Editor
8:35
Free Response Questions
12:25
Example
12:40
Java Editor
14:35
AP Java Subset
17:06
What It Is
17:37
Primitive Types
18:49
Arithmetic Operators
19:11
Assignment Operator
19:46
Combined Arithmetic / Assignment Operators
19:51
Increment / Decrement Operators
20:13
Relational Operators
20:36
Logical Operators
21:06
Numeric Casts
21:44
Numeric Wrapper Classes
22:39
Math Library Methods
23:08
String Operations
23:50
User Input
25:33
Output
27:17
Program Invocation
28:13
Arrays
29:06
Lists
29:52
Control Structures
30:47
Methods
31:27
Classes
32:10
Inheritance
33:09
Exceptions
34:22
Tips for Taking the Exam
34:55
Before the Exam
35:04
During the Exam
36:58
Summary
39:27
Types, Variables, & Arithmetic Operators

23m 20s

Intro
0:00
0:11
Primitive Data Types
0:37
Int
1:48
Double
2:42
Boolean
3:53
Variables
4:04
Declaring a Variable
4:16
Assigning a Value
6:01
Declaring and Assigning on the Same Line
6:36
Casting
7:00
Mixing Types
7:10
Automatic Casting
8:31
Find Variables - Constants
9:21
Final Variables
9:40
Constants Written in All Capitals
10:43
Arithmetic Operators
11:59
Five Arithmetic Operators
12:10
Result Depends on Type of Operands
13:49
Assignment Operators
14:59
Compound Assignment Operators
15:13
Examples
15:43
Increment / Decrement Operators
17:08
17:37
Subtracts 1 (--)
18:25
Summary
21:41
Equality, Relational, & Logical Operators

22m 34s

Intro
0:00
0:11
Equality and Relational Operators
1:09
Equal to
1:15
Not Equal to
2:25
Relational Operators
2:40
Logical Operators
3:44
Three Operators: And, Or, Not
3:53
AND Defined
4:18
OR Defined
4:50
NOT Defined
5:19
Example: And
5:43
Example: Or
6:23
Example: Not
6:41
Truth Tables
7:16
Truth Tables for AND
7:30
Truth Tables for OR
8:05
Truth Tables for NOT
8:47
Short-Circuit Evaluation
10:03
Example
10:32
This Behavior Can be Useful in Program Design
12:29
De Morgan's Laws
13:53
First Law
14:04
Second Law
14:29
Operator Precedence
15:28
List of Operators in Highest to Lowest Precedence
15:38
Evaluation on Operators
17:30
Summary
20:26
Input, Output, & Errors

24m 7s

Intro
0:00
0:11
Getting Input from the User
0:42
For AP Questions, Will Look Like One of the Following
0:54
One Method of Getting Input From the User
2:50
Scanner Class
3:20
Providing Output to the User
4:38
Only 2 Included in AP Subset
5:06
Example: Print Two Strings on the Same Line
5:45
Example: Print a String and an Integer
6:16
Example: Print a Blank Line
6:40
Java Code Example
7:04
Escape Sequences
11:10
Backslash Character Followed by One or More Additional Characters
11:23
Newline Character
11:49
Double Quote Character
12:39
Backslash Character
13:48
Java Code Examples: Printing Escape Sequences
14:43
Exception Handling
16:25
Describe As
16:33
Exceptions Within the AP Subset That Provides Structured Way to Handle Errors
17:18
Java Code Example
19:40
Summary
22:21
Conditional Statements

28m

Intro
0:00
0:09
Conditional Statements
0:55
Based on Value of a Boolean Expression
1:40
Switch Statement
2:42
The If Statement
2:59
Structure of If Statement
3:06
The If-Else Statement
4:46
The If-Else Statement
6:02
If expression - False
6:34
Nested If-Else Statements
7:13
'Nest'
7:28
Nested If-Else Statements
7:56
First Thing to Determine
9:28
Code
10:24
The Extended If Statement
13:14
Code
15:45
The Switch Statement
18:54
The Way It Works
19:37
Example: Switch Statement in a Java Program
22:44
Summary
27:03
Loops

32m 29s

Intro
0:00
0:07
Repeating an Action
0:53
Example
1:03
Repeating an Action
1:21
Use Brute Force Method
1:32
The While Loop
2:16
To Repeat An Action
2:55
Example: While Loop
4:57
The Do Loop
5:53
Example: Do Loop
8:00
Distinction of Do Loop & While Loop
9:04
The For Loop
10:30
The Way It Works
10:41
Example: The For Loop
12:43
The Enhanced for Loop
14:18
The Way It Works
14:42
Example:Enhanced for Loop
16:32
Nested While Loops
19:06
Example
19:33
Example: Nested While Loop (Code)
20:47
Nested For Loops
22:36
Example
22:51
Example: Nested For Loop (Code)
23:29
The Return Statement
24:30
Example
25:03
The Break Statement
26:21
The Continue Statement
28:01
Summary
30:56
Strings

42m 20s

Intro
0:00
0:25
Literal Strings
1:27
Class: Strings
1:38
String Is Immutable
2:11
Example
2:53
Literal Strings
3:27
String Variables
4:24
Example: String Variable
5:56
String Concatenation
7:03
Example
7:37
Example: String Concatenation
8:26
String Concatenation
10:00
Assignment Operator
10:11
Example
10:48
Example: String Concatenation
11:25
String Length
13:05
Example: String Length
14:16
String Comparison
16:04
Equals Method
16:37
Example: String Comparison
17:08
String Comparison
21:40
String.Equals: Case-Sensitive
21:49
Equals Ignore Case: Case-Insensitive
22:14
Example: Case-Sensitive and Case-Insensitive Comparison
22:46
String Comparison
25:38
Compare To (String.compareTo)
25:53
Example
27:27
Example: Sting Comparison Using the compareTo Method
28:15
Taking a Subset of a String
30:34
Substring Method
30:59
2 Versions
31:08
1st Version: Takes One Parameter
31:27
2nd Version: Takes Two Parameters
32:41
Example: Substring
34:02
Searching Within a String
36:04
indexOf Method
36:12
1st Version: Takes One Parameter
36:26
2nd Version: Takes Two Parameters
37:27
Searching Within a String
38:36
lastIndexOf Method
38:53
1st Version: Takes One Parameter
39:08
2nd Version: Takes Two Parameters
39:28
Summary
40:43
Arrays

47m 2s

Intro
0:00
0:14
Declaring and Creating an Array
0:49
Array Defined
0:55
1st Way to Declare and Create and Array
1:10
2nd Way to Declare and Create and Array
2:15
Referring to Elements in an Array
5:12
Integer Expression
5:39
Code Example: Declaring and Creating Arrays
7:26
Referring to Elements in an Array
9:12
Example
9:45
Code Example: Looping Through an Array of Ints
12:23
Referring to Elements in an Array
15:35
Enhanced for Loop
15:42
Code Example: Looping Through an Array of Strings With an Enhanced for Loop
17:19
Referring to Elements in an Array
19:25
ArrayIndexOutOfBoundsException
19:37
Code Example: Array Index Out of Bounds Exception
21:03
Resizing Arrays
23:05
Example
23:33
Code Example: Resizing Arrays
25:15
Copying Arrays
28:13
Passing an Array to a Method
30:09
Example
30:15
When Calling This Method: Pass in an Array
33:40
Code Example: Passing an Array to a Method
34:06
Returning an Array From a Method
36:02
Create a Method
36:12
Calling This Method
38:42
Code Example: Returning an Array to a Method
39:24
Two-Dimensional Arrays
42:23
Length Method
43:17
Number of Columns
43:42
Summary
45:00
Classes & Objects

47m 33s

Intro
0:00
0:46
Classes and Objects
2:03
Class
2:17
Object
2:34
Constructors
3:43
Constructors
5:34
Methods
7:11
Example: getName Method
7:44
Methods
8:45
Example
9:08
Example in Java Program
10:19
Data Fields
12:48
Way to Find Data Fields
13:10
Data Fields
13:50
Example: Instantiate Two Objects with Different Instance Data
14:43
Return Type
16:21
A Primitive Type
16:37
An Object of a Class Type
16:49
Return Type
17:25
Access Control
18:19
Public, Protected and Private
19:31
Assumptions Made in AP Java Subset
20:00
Access Control
20:58
Definition of Public
21:08
Definition of Protected
21:18
Definition of Private
21:28
Guidelines on What to Make Public/ Private
21:36
Accessors and Modifiers
24:47
Accessor
25:35
Modifier or Mutator
26:24
Static vs. Instance
27:15
Static Member
27:26
Example: Static vs. Instance
27:59
Code Example
30:19
Passing Data to Method
34:00
Code Example
36:17
Getting Data Back From Methods
37:28
To Make Use of a Return Value
37:53
Code Example
38:51
39:39
Signature Includes
40:19
Signature Does Not Include
40:45
43:52
44:19
Summary
45:00
Inheritance & Polymorphism

31m 30s

Intro
0:00
0:42
Inheritance
1:14
Subclass
1:56
Superclass
2:07
Inheritance
3:08
Example
3:36
Inheritance
4:44
Subclass Does Not Inherit…
6:05
Inheritance
7:06
To Override a Method
7:17
Inheritance
8:59
Example
10:24
Class Hierarchies
11:31
Multiple Level Hierarchies for Subclass
12:41
Abstract Classes
14:35
Example
15:59
Polymorphism
20:19
Example
20:34
Interfaces
22:33
Interfaces Example
25:13
Defines 3 Methods
25:27
Summary
29:26
Lists

33m 15s

Intro
0:00
0:16
Lists
0:52
Wrapper Classes
1:10
The List Interface
2:37
Cannot Instantiate a List
3:26
The ArrayList Class
5:01
The Way It Works
7:45
The ArrayList Class
8:34
Primary Methods Needed To Use for ArraryList
8:53
Code Examples
16:26
21:01
21:59
Code Example
24:05
25:25
Internal Storage Implementation of ArrayList
25:35
26:01
Pros/Cons of Each
26:23
Summary
32:10
Numeric Wrapper Classes & Mathematical Functions

23m 14s

Intro
0:00
0:11
Numeric Wrapper Classes
0:42
To Get Around Storing Limitation
1:19
Setting and Getting Values
2:30
Double Class
3:57
Comparing Values
5:07
Equals Method
5:22
Comparing Values
7:16
CompareTo Method: Integer Class
7:29
CompareTo Method: Double Class
9:24
Minimum and Maximum Values
10:28
Integer Class: Publib Static Final
10:56
Double Class
12:19
Automatic Conversion
12:53
Autoboxing
13:12
Example
13:36
Get Method
14:52
The Math Class
15:59
Math.E
16:18
Math.PI
16:25
Example
16:34
The Math Class
17:07
Working With Random Numbers
18:42
Example
19:47
Summary
22:14
Algorithms: Iteration

25m 43s

Intro
0:00
0:13
Iteration
0:36
Iteration Defined
0:39
For Loop / While Loop
0:50
Example
1:11
Iteration
3:11
Two-Dimensional Range
3:19
Using Two Nested While Loops
5:00
Finding Minimum and Maximum Values
5:54
Finding Minimum and Maximum Values Examples
7:50
Finding Minimum and Maximum Values Example
12:52
Inserting in Order
15:19
Inserting in Order Code
17:42
Loop Invariants
21:53
Example
23:17
Summary
24:37
Algorithms: Recursion

27m 30s

Intro
0:00
0:09
Recursion
0:44
Calculating Factorials
2:49
n! and How It's Defined
3:01
Recursive Implementation of the Factorial Function in Java
3:34
Calculating Factorials
4:34
Calculate 4!
4:35
Factorial Function in Java
7:22
Calculating Fibonacci Numbers
9:19
Fibonacci Numbers Defined
9:30
Recursive Implementation
10:33
Implementation in Java
10:44
Calculating Fibonacci Numbers
11:28
Calculate Fibonacci(4)
11:29
Fibonacci in Java
14:59
Other Recursive Functions
17:35
Other Recursive Functions
21:32
Calculate Mystery(4)
21:33
Mystery in Java
22:29
Important Considerations
23:49
Recursive Methods
25:15
Summary
26:41
Algorithms: Sorting

29m 42s

Intro
0:00
0:08
Sorting
0:55
Definition of Sorting
1:05
Cant Sort Any of the Following
1:14
Selection Sort
3:49
Definition of Selection Sort
3:58
'Search-and-Swap' Algorithm
5:05
Selection Sort Example
7:46
Insertion Sort
10:57
Insertion Sort Example
13:02
Merge Sort
15:14
Recursive Sorting Algorithm
16:15
Merge Sort Example
18:03
Quick Sort
20:34
Recursive Sorting Algorithm
21:36
Quick Sort Example
23:35
Summary
27:19
Algorithms: Searching

32m 37s

Intro
0:00
0:08
Searching
0:40
Sequential Search
2:22
Performed on Any Array
2:29
Sequential Search Algorithm Using a For Loop
4:24
Java Example
6:28
Binary Search
8:51
Binary Search Algorithm Using a While Loop
12:03
Java Example
16:59
Binary Search
20:38
Recursive Method
20:53
Java Example: Using Binary Search
25:34
Search Considerations
28:16
Binary Search
29:14
Summary
31:14
Program Design & Development

29m 29s

Intro
0:00
0:41
Object-Oriented Programming
1:20
Definition
1:35
Encapsulation
2:26
Polymorphism
4:43
Top-Down Design and Development
5:56
Top-Down Design
6:10
Top-Down Development
6:51
Reusable Code
8:47
Definition
8:58
Example to Reusable Code
10:33
Team Development
11:36
Team Development
15:03
15:23
Data Structure
19:28
Definition
19:35
Examples
19:44
User Interface
20:53
Definition
21:00
Specifications
24:19
Definition
24:29
2 Important Purposes for Specifications
25:25
Summary
27:27
Standard Classes & Interfaces

32m 53s

Intro
0:00
0:13
Object
1:46
Methods
1:57
Equals Method
2:06
toString Method
2:16
What Else To Know
2:28
Integer
3:19
Constructor
3:32
Methods
3:51
Constants
4:28
What Else To Know
5:05
Double
6:14
Constructor
6:35
Methods
6:50
What Else To Know
7:06
String
8:16
Methods
8:40
What Else To Know
12:10
Math
15:24
Methods
15:36
What Else To Know
18:13
List
20:02
Methods
20:30
ArrayList
22:45
What Else To Know
23:27
Test-Taking Tips
26:05
Summary
29:47
Section 2: AP Test Preparation
Multiple Choice Question Tips & Practice

55m 47s

Intro
0:00
0:23
AP Computer Science Exam Structure
1:32
Two Sections
1:40
Contribution to Score
3:35
Multiple Choice Strategies and Tips
4:50
Example Question 1
9:07
Example Question 2
13:34
Example Question 3
16:12
Example Question 4
21:44
Example Question 5
26:41
Example Question 6
34:12
Example Question 7
39:41
Example Question 8
42:09
Example Question 9
46:31
Example Question 10
50:35
Summary
54:49
Free Response Question Tips & Practice

40m 55s

Intro
0:00
0:27
AP Computer Science Exam Structure
1:15
Two Sections
1:20
Contribution to Score
2:09
Free Response Strategies and Tips
3:23
Free Response Strategies and Tips Continued
6:17
Free Response Strategies and Tips Continued
10:22
Free Response Strategies and Tips Continued
13:00
Free Response Strategies and Tips Continued
15:42
Example Free Response Question
17:41
Example Free Response Question Narrative Continued
18:30
Example for Problem
19:29
Example Set-Up for Problem
19:56
Example Set-Up for Problem Continued
21:48
Code
24:14
Code Continued: First Method
25:36
Second Method
26:28
27:04
Definition of Part A: What They Want You to Write
27:33
Definition of Part B: What They Want You to Write
28:50
Requirements for Part A
31:06
Part A: One Possible Solution
31:49
Requirements for Part B
34:06
Part B: One Possible Solution
34:48
Summary
39:52
The GridWorld Study

54m 18s

Intro
0:00
0:19
Overview of GridWorld
0:51
Definition of GridWorld
1:00
Important part of AP Exam
3:14
Need to Understand It
5:16
Overview of GridWorld: Testable APIs
8:00
API Defined
8:06
Testable APIs
8:52
Testable Code
9:22
4 Classes
9:57
Location Class
10:21
Location Class: 8 Public Constants That Help with Direction
11:36
Row Numbering
12:32
Column Numbering
13:13
Location Class: 7 Public Constants That Represent Turns
13:31
Location Class: Methods Useful in Navigating Through the Grid
15:25
15:34
getDirectionToward
16:21
Location Class: 3 Other Useful Methods
16:58
Equals Method
17:05
CompareTo Method
17:35
ToString Method
18:16
Grid Interface
18:41
Represents
18:50
Grid Interface: Useful Methods
20:34
getNumRows Method
20:42
getNumCols Method
20:52
isValid Method
21:00
Grid Interface: Useful Methods
22:16
Put Method
22:23
Remove Method
22:13
Get Method
23:26
Grid Interface: Useful Methods
23:44
GetOccupiedLocations Method
23:55
24:21
25:02
25:24
Grid Interface: Useful Methods
25:37
GetNeighbors Method
25:44
Actor Class
26:27
Constuctor: Actor
27:02
GetColor Method
27:31
SetColor Method
27:38
GetDirectionToward Method
27:46
SetDirection Method
28:09
GetGrid Method
28:27
GetLocation Method
28:40
PutSelfInGrid and RemoveSelfFromGrid Method
28:51
MoveTo Method
30:03
Act Method
30:17
ToString Method
31:24
Rock Class
31:46
3 Methods
31:58
Flower Class
32:35
3 Methods
32:51
Bug Class
33:53
Includes These Methods
34:34
How the Move Method Works
36:38
CanMove Method
38:53
BoxBug Class
40:49
Behavior
41:00
2 Private Variables
41:20
Constructor for BoxBug
41:55
BoxBug Class Methods
42:16
Critter Class
43:41
How It Works
44:03
Next Step
45:38
3rd Step
47:01
Last Step in Act Method
48:33
ChameleonCritter Class
49:00
Redefines Some Characteristics of Critter Class
49:26
Another Difference
51:02
Summary
52:25

41m

Intro
0:00
0:16
Multiple Choice Strategies and Tips
0:45
Structure
0:49
Points Worth
1:47
Some Strategies and Tips
3:29
6:10
Some Strategies and Tips Specifically on GridWorld Questions
6:29
Some Strategies and Tips Specifically on GridWorld Questions
9:37
GridWorld Testable APIs and Code
13:17
Testable APIs
13:25
Testable Code
13:47
Example Question 1
14:32
Example Question 2
17:11
Example Question 3
22:53
Example Question 4
26:17
Example Question 5
34:11
Summary
39:47

39m 31s

Intro
0:00
0:14
Free Response Strategies and Tips
0:49
Format
0:56
Points
1:18
Quick Reference Guide
1:49
Not Required to Do in Order
2:48
Multiple Parts
3:33
All Answers Must Be Written in Java
5:00
Partially Correct Solutions Can Be Awarded Partial Credit
7:49
Write Neatly
10:40
Don't Waste Time
12:52
GridWorld Testable APIs and Code
14:55
Testable APIs
15:05
Testable Code
15:53
GridWorld Testable APIs and Code
16:37
GridWorld Free Response Question
16:41
Example
17:34
Example Free Response Question
18:23
Question
18:54
Visual Diagram of the Game Board
20:00
Visual Chart
21:08
Narration Continues
21:56
The Piece Class
22:59
Narration Continues
23:59
What You Will Need to Do
24:28
The Rest of the Definition for DropGame
25:08
Part A: Requirements
25:55
Part B: Requirements
28:44
Part A: Question (Again)
31:54
Part A: One Possible Solution
32:19
Part B: Question (Again)
35:30
Part B: One Possible Solution
35:47
Summary
38:34
Final Tips for Taking the Exam

27m 38s

Intro
0:00
0:10
AP Computer Science Exam Structure
0:46
Two Sections
0:49
Scoring
1:24
Multiple Choice Strategies and Tips
2:15
Answer Questions for Descriptive Paragraph First
2:38
3:42
Free Response Strategies and Tips
4:00
4:57
5:54
Partially Correct Solutions
8:32
Write Neatly
10:33
Draw a Single Line Through Mess-Ups
13:09
14:49
15:20
15:39
Remember, You Can Watch This Lesson More Than Once
15:54
What to Bring to Your Exam
16:19
What Not to Bring to Your Exam
18:47
22:00
24:23
Summary
26:44
Glossary of Terms to Know

36m 31s

Intro
0:00
0:16
Abstract Class
1:28
Array
2:29
Casting
3:43
Class
4:39
Conditional Statement
5:35
Constructor
6:28
Escape Sequence
7:18
Exception
8:24
Final Variable
8:59
Inheritance
10:19
Instance
11:36
Interface
12:33
Iteration
13:08
List
14:05
Logical Operator
15:11
Loop
16:20
Loop Invariant
17:06
Method
17:30
Numeric Wrapper Class
18:55
20:38
Polymorphism
21:10
Primitive Data Type
23:22
Public and Private
24:06
Random
25:03
Recursion
27:07
Return Type
28:08
Searching
28:59
Signature
30:14
Sorting
30:51
Static
32:40
String
33:37
Subclass and Superclass
34:30
Glossary
35:37
Bookmark & Share Embed

## Copy & Paste this embed code into your website’s HTML

Please ensure that your website editor is in text mode when you paste the code.
(In Wordpress, the mode button is on the top right corner.)
×
• - Allow users to view the embedded video in full-size.
Since this lesson is not free, only the preview will appear on your website.

• ## Related Services

 1 answerLast reply by: Professor QuayleWed May 6, 2015 10:37 PMPost by Milan Ray on May 6, 2015isn't the recursive binary search really just more code? Becuase it just states another way to do the loop, just without a while.. 0 answersPost by meteib alsubaie on December 4, 2013nice

### Algorithms: Searching

• Searching is looking for a particular value in a collection
• If the collection is not sorted, every value must potentially be searched
• If the collection is sorted, it is possible to search much more efficiently
• Sequential Search examines every value; must be used if collection is not sorted
• Binary Search is much faster than Sequential Search for large collections of data but can only be used if the data is sorted
• Binary Search can be implemented either iteratively or recursively

### Algorithms: Searching

Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.

• Intro 0:00
• Searching 0:40
• Sequential Search 2:22
• Performed on Any Array
• Sequential Search Algorithm Using a For Loop 4:24
• Java Example
• Binary Search 8:51
• Binary Search Algorithm Using a While Loop 12:03
• Java Example
• Binary Search 20:38
• Recursive Method
• Java Example: Using Binary Search
• Search Considerations 28:16
• Binary Search
• Summary 31:14

OR

### Start Learning Now

Our free lessons will get you started (Adobe Flash® required).