1 of 18

The best semi-conductor??

Silicon is the basis of modern computing in chips but it has some major flaws. Scientists at MIT, UHouston have conducted experiments to show Cubic Boron Arsenide overcomes both these issues.

The Beauty and Joy of Computing��Lecture #5�Algorithms�

​

https://www.sciencedaily.com/releases/2022/07/220721141459.htm

Put your notes here

UC Berkeley�Teaching Professor �Dan Garcia

CS10 NEWS

  • Check office hours every week (go to anyone’s office hours)

​

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (1)

Garcia

2 of 18

Algorithms: Definitions

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (2)

Garcia

3 of 18

Algorithm: Definition

  • “Algorithms are precise sequences of instructions for processes that can be executed by a computer and are�implemented using programming languages.”

​

  • The concept of algorithms, however, is far older than computers.

​

en.wikipedia.org/wiki/Algorithm

Euclid’s GCD Algorithm�(Wikipedia, Somepics)

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (3)

Garcia

4 of 18

Early Algorithms

  • Dances, ceremonies, recipes, and building instructions are all conceptually similar to algorithms.
  • Babylonians defined some fundamental mathematical procedures ~3,600 years ago.
  • Genes contain algorithms!

Woman Basket Weaving�(Wikipedia, Public Domain)

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (4)

Garcia

5 of 18

Algorithms You've Seen in BJC so far

​

  • Length of word
  • Whether a word appears in a list
  • Interact with the user (ask)
  • Sort a List (you’ll see in lab)

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (5)

Garcia

6 of 18

Algorithms You May Already Know

Luhn algorithm

Credit card number validation

Deflate�Lossless data compression

PageRank

Google’s way to measure web page “reputation”

EdgeRank

Facebook’s way to determine news feed sort

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (6)

Garcia

7 of 18

Building Blocks of Algorithms

Sequencing

Application of each step of an algorithm in order given

Selection�Use of Boolean condition to select which of two parts to do

​

Iteration

Repetition algorithm part # times or until condition met

Recursion

The overall algorithm calls itself to help solve the problem on smaller parts,combine result.

(we’ll see later)

🗹

Every algorithm can be constructed using only�Sequencing, Selection, & Iteration!

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (7)

Garcia

8 of 18

Which of the following is false?

  1. Algorithms can be worth billions of $
  2. You learned your first algorithm before you could speak
  3. Proving algorithms are correct is easy
  4. Algorithms can adapt, like a living thing

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (8)

Garcia

9 of 18

Algorithms: Properties, Expressing

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (9)

Garcia

10 of 18

Properties of Algorithms

  • Algorithms can be combined to make new algorithms.
  • Using existing correct algorithms as building blocks for constructing a new algorithm helps ensure the new algorithm is correct.
  • Knowledge of standard algorithms can help in constructing new algorithms
  • Different algorithms can be developed to solve the same problem.
  • Developing a new algorithm to solve a problem can yield insight into the problem

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (10)

Garcia

11 of 18

How to Express Algorithms…

A programmer’s spouse says: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.” The programmer comes home with 12 loaves of bread.

​

Algorithms need to be expressed in a context-free, unambiguous way for all participants!

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (11)

Garcia

12 of 18

Languages for Algorithms

  • Natural Language, Pseudo Code
    • For Humans to understand
  • Visual & Text-based Programming �Languages
    • Can be run on a computer
  • …or in any other information conveying way!

​

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (12)

Garcia

13 of 18

Algorithms vs. Functions & Procedures

  • Algorithms are conceptual definitions of how to accomplish a task and are language agnostic, usually written in pseudo-code.
  • Find max value in list
    • Set (a temporary variable) the max as the first element
    • Go through every element, compare to max, and if it’s bigger, replace the max
    • Return the max
  • A function or procedure is an implementation of an algorithm, in a particular language.

​

  • Find max value in list

​

Garcia

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (13)

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (13)

Garcia

14 of 18

Which Language to Choose?

  • Different languages are better suited for expressing different algorithms
  • Some programming languages are designed for specific domains and are better for expressing algorithms in those domains
  • The language used to express an algorithm can affect characteristics such as clarity or readability but not whether an algorithmic solution exists
  • Clarity and readability are important considerations when expressing an algorithm in a language.

​

​

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (14)

Garcia

15 of 18

Programming Languages

C/C++

Good for programming that is close to hardware

Java/C#�Portable code

Python/Perl/TclTK

Fast to write and portable

Scratch/Snap!

Good for teaching programming concepts

​

Nearly all programming languages are equivalent in terms of being able to express any algorithm!

🗹

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (15)

Garcia

16 of 18

Of 4 languages, what’s the most powerful?

  1. C/C++
  2. Java/C#
  3. Perl/Python/TclTk
  4. Scratch/Snap
  5. All equally powerful

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (16)

Garcia

17 of 18

Different Algorithms demo time!

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (17)

Garcia

18 of 18

Summary

  • The concept of an algorithm has been around forever, and is an integral topic in CS.
  • Algorithms are well-defined procedures that can take inputs and produce output. Programming languages help us express them.
  • We're constantly dealing with trade-offs when selecting / building algorithms.
  • Each language listed is equally powerful
    • We’ll see why next time!

Garcia

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (18)

UC Berkeley “The Beauty and Joy of Computing” : Algorithms (18)

Garcia