# Difference between revisions of "CS 101/Additional Materials/Chapter 7"

Mike Huynh (Talk | contribs) m |
Karl Wurst (Talk | contribs) (Added chapter sections to begin cleanup) |
||

Line 1: | Line 1: | ||

+ | == Section 7.1 How to Solve Problems == | ||

+ | |||

+ | === Ask Questions === | ||

+ | |||

+ | === Look for Familiar Things === | ||

+ | |||

+ | === Divide and Conquer === | ||

+ | |||

+ | === Algorithms === | ||

+ | |||

+ | === Computer Problem-Solving Process === | ||

+ | |||

+ | === Summary of Methodology === | ||

+ | |||

+ | ==== 1. Analyze the Problem ==== | ||

+ | |||

+ | ==== 2. List the Main Tasks ==== | ||

+ | |||

+ | ==== 3. Write the Remaining Modules ==== | ||

+ | |||

+ | ==== 4. Re-sequence and Revise as Necessary ==== | ||

+ | |||

+ | === Testing the Algorithm === | ||

+ | |||

+ | == Section 7.2 Algorithms with Simple Variables == | ||

+ | |||

+ | === An Algorithm with Selection === | ||

+ | |||

+ | === Algorithms with Repetition === | ||

+ | |||

+ | === Count-Controlled Loops ==== | ||

+ | |||

+ | ==== Event-Controlled Loops ==== | ||

+ | |||

+ | ==== Square Root ==== | ||

+ | |||

+ | == Section 7.2 Composite Variables == | ||

+ | |||

+ | === Arrays === | ||

+ | |||

+ | === Records === | ||

+ | |||

+ | == Section 7.4 Searching Algorithms == | ||

+ | |||

+ | === Sequential Search === | ||

+ | |||

+ | === Sequential Search with a Sorted Array === | ||

+ | |||

+ | === Binary Search === | ||

+ | |||

+ | == Section 7.5 Sorting == | ||

+ | |||

+ | === Selection Sort === | ||

+ | |||

+ | === Bubble Sort === | ||

+ | |||

+ | === Insertion Sort === | ||

+ | |||

+ | == Section 7.6 Recursive Algorithms == | ||

+ | |||

+ | === Subprogram Statements === | ||

+ | |||

+ | === Recursive Factorial === | ||

+ | |||

+ | === Recursive Binary Search === | ||

+ | |||

+ | === Quicksort === | ||

+ | |||

+ | == Section 7.7 Important Threads == | ||

+ | |||

+ | === Information Hiding === | ||

+ | |||

+ | === Abstraction === | ||

+ | |||

+ | === Naming Things === | ||

+ | |||

+ | === Testing === | ||

+ | |||

+ | |||

===Linear (Sequential) Search=== | ===Linear (Sequential) Search=== | ||

{{#ev:youtube|CX2CYIJLwfg}} | {{#ev:youtube|CX2CYIJLwfg}} |

## Latest revision as of 16:39, 25 March 2016

## Contents

- 1 Section 7.1 How to Solve Problems
- 2 Section 7.2 Algorithms with Simple Variables
- 3 Section 7.2 Composite Variables
- 4 Section 7.4 Searching Algorithms
- 5 Section 7.5 Sorting
- 6 Section 7.6 Recursive Algorithms
- 7 Section 7.7 Important Threads
- 8 Binary Search of an Array

## Section 7.1 How to Solve Problems

### Ask Questions

### Look for Familiar Things

### Divide and Conquer

### Algorithms

### Computer Problem-Solving Process

### Summary of Methodology

#### 1. Analyze the Problem

#### 2. List the Main Tasks

#### 3. Write the Remaining Modules

#### 4. Re-sequence and Revise as Necessary

### Testing the Algorithm

## Section 7.2 Algorithms with Simple Variables

### An Algorithm with Selection

### Algorithms with Repetition

### Count-Controlled Loops =

#### Event-Controlled Loops

#### Square Root

## Section 7.2 Composite Variables

### Arrays

### Records

## Section 7.4 Searching Algorithms

### Sequential Search

### Sequential Search with a Sorted Array

### Binary Search

## Section 7.5 Sorting

### Selection Sort

### Bubble Sort

### Insertion Sort

## Section 7.6 Recursive Algorithms

### Subprogram Statements

### Recursive Factorial

### Recursive Binary Search

### Quicksort

## Section 7.7 Important Threads

### Information Hiding

### Abstraction

### Naming Things

### Testing

### Linear (Sequential) Search

{{#ev:youtube|CX2CYIJLwfg}}

selection searching https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&cad=rja&uact=8&ved=0ahUKEwikuN7eibDLAhUC5GMKHX4uChwQFgg6MAU&url=http%3A%2F%2Fzimmer.csufresno.edu%2F~sasanr%2FTeaching-Material%2FSAD%2FProcess-Specification%2FSelection-control-structure.doc&usg=AFQjCNFzgkQSqo79T8nFJGkTQ8jydRdP2A&sig2=ZnVqsb6ew77RVgRbJ2DTwA 07MAR2016 this is downloadable PDF doc that helped me understand the selection control process. It is take from another CS book, may be useful to have a slightly different way of explaining the same items. Scott Shea

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheSequentialSearch.html This is an interactive website about Sequential Search. The website made more sense than the book because of the diagrams and questions they offered. It provides clear understanding and examples. -Justin Cabacungan (Date Added: March 10, 2016)

### Binary Search

https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search I found this link to be really helpful because it provided a lot of information in an easy to understand way. I find that Khan Academy is a really helpful site to find information on. Added: 12 MAR 2016 By: Kylie Sauter

{{#ev:youtube|D5SrAga1pno}}

The Binary Search Algorithm: http://www.csit.parkland.edu/~mbrandyberry/CS1Java/Lessons/Lesson27/BinarySearch.htm Added 3/10/2016. Last Updated 2010. Explains how to do binary search in a way that is very easy to understand. Provides a few graphics that also help to exemplify the process. - Samantha Stuart

I found this helpful for the binary and linear search https://www.youtube.com/watch?v=wNVCJj642n4 -Liz Cochrane

Binary Search! https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/ 3/12/16. This link explains a lot about the concept of binary searching and how it works. Mike Wilbur.

How Binary Search Works

https://www.youtube.com/watch?v=JQhciTuD3E8 uploaded on 2/16/12

I found this video helpful with understanding how binary search works, one of the most efficient searching techniques. The video is complete with examples and an explanation on its scalability.

- Andrew Lund (3/12/16)

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/ This definition and example helped me when it came to learning about binary search. I am a hands on learner so actually seeing an example of a way something is supposed to be done really helps out. (March 12, 2016) -Danielle Gary

Selection Sort http://www.algolist.net/Algorithms/Sorting/Selection_sort Added on March 8th, 2016. Last updated in 2009. This website gives an overview of how selection sort takes place. It also adds a paragraph or two explaining the method as well ask the Java and C++ instructions. Urooj Haider

https://www.youtube.com/watch?v=GUDLRan2DWM This video describes Selection sort algorithm. It was uploaded by mycodeschool on on Jun 7, 2013. Sworup Ojha 3/10/16

https://en.wikipedia.org/wiki/Selection_sort This wikipedia page has a animation of how a selection sort works, which helped me with Java. It also has a java code to see how to create one yourself. Mike Huynh 3/12/16

### Bubble Sort

http://www.sorting-algorithms.com Published 2016 This is a great tutorial on different sorting algorithms complete with descriptions, tutorials and animations. Added 3/12/2016 Sean Thomson

Published
{{#ev:youtube|8Kp-8OGwphY}}

**Chapter 7 Resource -**
________________________________________________________________________________________________________________
http://www.javawithus.com/tutorial/searching-and-sorting-arrays

This site helped me learn about searching and sorting arrays. It did this by going into more simple explanations than the book of each of the search and sorting.

Jaclyn Mason _____________________________________________________________________________________________________________________

Algorithm Lesson 1-5:Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, Linear and Binary Searching

Lesson 1: https://www.youtube.com/watch?v=P00xJgWzz2c - Posted on Jan 1st, 2009 Lesson 2: https://www.youtube.com/watch?v=c4BRHC7kTaQ - Posted on Apr 14th, 2009 Lesson 3: https://www.youtube.com/watch?v=GCae1WNvnZM - Posted on July 26th, 2009 Lesson 4: https://www.youtube.com/watch?v=y_G9BkAm6B8 - Posted on Sept 10th, 2009 Lesson 5: https://www.youtube.com/watch?v=wNVCJj642n4 - Posted on Dec 28th, 2009

Date of access: March 21st, 2015

Each of these videos give a clearly understandable yet brief explanation on each concept that they covers, from Bubble Sort to Linear Searching in arrays. Each topic that these videos base their premise on are major all major points in Chapter 7.

Logan Martinez

Chapter 7 Resource- I found this video very helpful in explaining the search algorithms used on arrays.

Posted on Dec 28th, 2009

https://www.youtube.com/watch?v=wNVCJj642n4

Ian Kelly

http://www.cs.utexas.edu/users/porter/cs304p/Practice/loops.html
This website was helpful in explaining controlled loops. It also shows an example of an event controlled loop and count controlled loop. There is no specific posted date. - Jessica Krafft

{{#ev:youtube|rhYouy229DA}}

- Date added
- 3/20/2015

- Date Created
- June 17, 2012
- I found this video helpful in explaining count control and event control loops.

- Sudarshan T

Chapter 7 Resource.
How Binary Search Works: https://www.youtube.com/watch?v=JQhciTuD3E8
Date Created: 26 February 2012.
Date Added: 20 March 2015.
This video goes in depth explaining how Binary Search Works. It also informs the audience which method works best/takes the most time.
Olivia Giedymin

Selection Sort vs. Bubble Sort {{#ev:youtube|iwi74tXBIt4}} {{#ev:youtube|_nQvymN-gUI}} Both are published on September 29, 2014 Access date: March 14, 2015 Date added: March 21, 2015 I find these clips explain the different between the two type of sort very easy to understand. Leon Ngo

Chapter 7 Resource
Introduction to Subprograms
{{#ev:youtube|x6opPdnNAbA}}
Date Published: February 26, 2103
Date added: March 21, 2015
This video demonstrates how subprograms work and function along with its name codes and expressions

Bubble Sort https://www.youtube.com/watch?v=BMZ6MF_l3vw This is a short and simple explanation of how bubble sort works and what exactly it is. Date Added 3-23-15 Date Published 12-5-09 Joseph Dupont

- Recursion

{{#ev:youtube|Mv9NEXX1VHc}}

This video explains the concept of recursion. I found it helpful.

- Date Added
- 3/28/2015
- Date Published
- May 16, 2014

Sudarshan T

.....................................................................................

Recursive Formulae

http://mathbitsnotebook.com/Algebra1/Functions/FNSequenceFunctionsRecursive.html

Simple, pictorial, illustrations of Recursive Functions.

Submitted by: J. Young,1:11 pm, 3/11/16

.....................................................................................

**Search and Sort Algorithms**

http://www.sorting-algorithms.com/

Copyright 2015

This website showed an animated chart of the search and sort function of various algorithms. It also explained in summary what was occurring and indicated numerous other resources in searching and sorting of algorithms

Submitted By Bob Lafrance

**Intro to Algorithms**
https://www.khanacademy.org/computing/computer-science/algorithms Date Added: 10/22/15. This website goes over the basics of algorithms in computer science. It has exercises that covers binary search, insertion sort, selection sort, recursion, quick sort, and other topics. Each section has an explanation about the process and how it works, and exercises on how to program it. ~Caitlyn Lambert-Hutchinson

http://www.bing.com/videos/search?q=bubble+sort&&view=detail&mid=1FB1D7EDD4C85E0F1C521FB1D7EDD4C85E0F1C52&FORM=VRDGAR This video breaks down how bubble sort algorithms work which I found very helpful to see visually. Rebecca Campbell 3/10/2016

### Algorithms

https://www.khanacademy.org/computing/computer-science/algorithms date added: 10/23/2015 This website has great descriptions and information on algorithms. It has a break down of the different topics including sorting, searching, and recursive algorithms. It then divides these topics into sub topics, they also feature examples. Zachary Brogna a set of instructions for solving a problem or a subproblem in a finite amount of time using a finite amount of data. Liz Cochrane

https://www.youtube.com/watch?v=6nDMgr0-Yyo Date added 3/6/16. Algorithms Lesson 8: Selection Sort video from YouTube posted on youtube on August 18th 2011. Inro to algorithms I found this topic beyond confusing. Good video with examples. The maker of this video also has a helpful website xoax.net. Rebecca Peacott

https://www.ted.com/talks/kevin_slavin_how_algorithms_shape_our_world?language=en Cool TED talk about how algorithms are everywhere - added by Zachary Halzel on 3/7/2016

### Algorithms

{{#ev:youtube|_oaWilIk5Vw}} Added on 10/24/2015 video uploaded on 3/9/2014. The beginning of the video provides great examples and visual aids. It is a lesson plan educators could use in order to explain to students and exercises that would help practice. Antoinette Cabral

## Binary Search of an Array

Published: 2015

Added: 10-24-15

This site uses interactive diagrams that help me understand binary search better than the book did. It also made writing the pseudocode much easier. With the book, I did not understand what the expressions meant in pseudocode or how they were obtained. This website explained how each line of the pseudocode is created. ~Rebecca Sherr

Problem Solving and Algorithms https://www.youtube.com/watch?v=63BBWWsqsT0 Apr. 4 2013 Oct. 24 2015 This youtube video focuses on solving real world problems that a programer runs in to when developing a program. With this instruction you get more in-depth look at how to solve these issues from chapter 7 but also show us how to incorporate better solving skills to these problem. This video can greatly increase your ability to under stand all of the harder issues explained in the chapter by step by step process. Zachary Nader.

Algorithms walk through: https://www.khanacademy.org/computing/computer-science/algorithms I found this helpul in better understanding the process and working of algorithms.

-Joseph Clark

https://www.youtube.com/watch?v=D5SrAga1pno To begin, this youtube video provides a very basic and clear understanding of how binary searches work. Not only this, but the video also explains binary search trees, which are in the next chapter after. This was doubly useful in my understanding of how a binary search worked. The video was uploaded on 9/27/12. Zackery Squires 3/9/2016