Class[1][23ed may] [algorithms]

ALGORITHMS, COMPUTER GRAPHICS, AND MATHEMATICS FOR GAME DEVELOPERS & COMPUTER SCIENTISTS Class[1]: Introduction to Algorithms, Big-O Notation Presented by Dr. Saajid Abuluaih - May 2021 -

Algorithms, Computer Graphics, and Mathematics for Game Developers and Computer Scientists © 2021 arche1.co.jp | jaist.ac.jp All rights reserved. 2 Agenda One-Bite Wisdom On Algorithms Simple Algorithms 𝑖 Big O Notation The Class Structure On Pseudocode Introduction to the Course 𝑔 𝑛 “The future is not just unwritten - it is unsearched” -Bruce Sterling

Algorithms, Computer Graphics, and Mathematics for Game Developers and Computer Scientists © 2021 arche1.co.jp | jaist.ac.jp All rights reserved. 3 BEFORE WE START, I GOT ONE DISCLAIMER TO ANNOUNCE This course is not designed for totally beginners … You need to have some basic knowledge on what Computer Science is all about HOWEVER, If you feel like you can’t understand something that you think it is important Please let me know

5 • Let’s Make a Deal was a very famous game show back in the 70’s & 80’s • Monty Hall is the host of the show • There are three doors, one of them has a nice prize, and the other two have gags (Usually a farm animal) • You chose a door and then the host will open “Empty” another • The host then will aske you whether to stick with or switch the door you picked MONTY HALL PROBLEM, THE THREE DOORS GAME References: Monty Hall Problem - Wikipedia Monty Hall Problem - Numberphile - YouTube Monty Hall show - Let’s make a deal Is there a good strategy to use in this case?

6 • Mathematicians say: in order to increase your chances to win the nice prize, you must switch MONTY HALL PROBLEM, THE THREE DOORS GAME References: Monty Hall Problem - Wikipedia Monty Hall Problem - Numberphile - YouTube Monty Hall show - Let’s make a deal This strategy doesn’t guarantee that you will. But it will increase your chances 13 1/3 2/3 1/3 2/3

7 Mathematicians say: in order to increase your chances of winning the nice prize, you must switch. MONTY HALL PROBLEM, THE THREE DOORS GAME References: Monty Hall Problem - Wikipedia Monty Hall Problem - Numberphile - YouTube To explain it even better, consider the following scenario. You have six doors. You chose one. The host open 4 empty doors. Will you prefer then to stick with your early door selection or will you switch. 1/6 5/6

Algorithms, Computer Graphics, and Mathematics for Game Developers and Computer Scientists © 2021 arche1.co.jp | jaist.ac.jp All rights reserved. WHAT THAT HAS TO DO WITH OUR CLASS FOR TODAY? NOTHING it has nothing to do with today’s class

This is a course in algorithms and 3D computer graphics that enables enrolled students to learn the theory of computer graphics along with algorithms implementation for solving real-life problems, specifically that relates to mathematics and physics of motion in 3D spaces. Ultimately, the course intends to deliver knowledge that is sufficient to construct an interactive 3D application for simulating the movement of a controllable entity. The main topics this course intends to cove is: 10 INTRODUCTION, WHAT THIS COURSE IS ALL ABOUT - Algorithms: - Big-O notation - Definition, characteristics, usage, design, optimization - Programing useful algorithms for popular problems - Computer Graphic with Three.js: - Scene creation: - Light, camera - Renderer, animation loop - 3D Object creation: - Geometry - Material - Mesh - Mathematica and Physics - Locations in 2D & 3D spaces - Raycasting in 3D environments - Vectors: - Vector normal form - Dot product - Cross Product - Intersections - Matrices and Transformations - Newtons Laws of Motions Bonus: - Programing languages: C#, JavaScript, TS

The structure of delivering classes: • One-bite wisdom 15 minutes (Knowledge Sharing Session) • Algorithms (15 minutes) • Lecture (45min ~ an hour) • Quiz • Homework • Groups’ discussion 30 minutes (we need four groups for) 12 THE CLASS STRUCTURE, WHAT THIS COURSE IS ALL ABOUT

Definition: An algorithm is an unambiguous finite sequence of well-defined step-by-step computer-implementable instructions, that takes data as an input instance (of a given problem) and produces an output that can be called a solution to the problem. But what is a problem: A problem is a set of instances that all share the same characteristic What is not an Algorithm: We don’t call the implementation of an algorithm an algorithm. We call it “code”. What makes an algorithm better than the other: Long story short, “the performance” … the smaller number of steps needed to produce the solution the better the algorithm is. However! Although, any type of instructions that handle inputs are considered “algorithms”; algorithmic thinking always involve loops and conditions. 14 ON ALGORITHMS, WHAT IS ALGORITHM? References: Algorithm What exactly is an algorithm? Algorithms explained | BBC (Ideas)

A flowchart is the graphical or pictorial representation of an algorithm with the help of different symbols, shapes, and arrows to demonstrate a process or a program. 15 ON ALGORITHMS, DESIGNING AN ALGORITHM References: Explain Algorithm and Flowchart with Examples Example 1: Print 1 to 20: Algorithm: • Step 1: Initialize X as 0, • Step 2: Increment X by 1, • Step 3: Print X, • Step 4: If X is less than 20 then go back to step 2.

Iterations VS Recursion The basic idea of using recursion and iteration is to repeat a sequence of instructions. Recursion is a function call in which the function being called is the same as the one initiating the call, whereas iteration occurs when a loop is continuously executed until a given condition is met. 16 On Algorithms, Algorithms implementation function Function1 (num) { if (Base) { return num; } return num + Function1(num - 1); } function Function1(num) { var value = 1; for (var i= num; i>=0; i--) { value += i; } return total; } References: Programming Loops vs Recursion - Computerphile

Factorial of a positive integer 𝑛𝑢𝑚 is product of all 𝑣𝑎𝑙𝑢𝑒𝑠 from 𝑛𝑢𝑚 to 1. For example, the factorial of 𝑛𝑢𝑚 = 5 is 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1 = 120. 18 A SIMPLE ALGORITHM, CALCULATING THE FACTORIAL VALUE OF A POSITIVE INTEGER function factorial(num) { if (num === 1) { return 1; } return num * factorial(num - 1); } function factorial(num) { var total = 1; for (var i= num; i>=1; i--) { total = total * i; } return total; }

• Write the implementation of the following flowchart using your favorite coding language. [Homework] • What does the algorithm in the flowchart do? • What is the output of the algorithm if N was 15? 20 Quiz [1] What is the output of the following algorithm? Start Total = 0 i = 0 Read N Is count < N Print N Total = Total + N i = i + 1 End

It is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In another way, it shows how the code slows as the data grows (Big- O notation used to measure space as well). 22 BIG-O NOTATION What is Big-O? References: Big O: How Code Slows as Data Grows Big O notation Algorithms Notes for Professionals

We can not use the time to measure the performance of an algorithm. So, what to doe? • Rather than counting seconds, we count the number of steps (operations) that we need to execute every time to generate the outcome. • Think of this simple algorithm that does nothing other than printout “hello world” how many steps we need to execute? 23 BIG-O NOTATION TIMING OUR ALGORITHMS References: Big O: How Code Slows as Data Grows Algorithms Notes for Professionals • It is going to be 𝑂 1 . • Big-O Notation is a way to formalize a fuzzy counting

What is the time complexity for the following algorithms: 24 BIG-O NOTATION LET’S EXAMINE the number of steps needed in algorithm THIS FUNCTION [P1] References: Big O: How Code Slows as Data Grows Algorithms Notes for Professionals How about his one: It is liner, 𝑂(𝑁) It is liner, 𝑂(1)

What is the time complexity for the following function: 25 BIG-O NOTATION LET’S EXAMINE the number of steps needed in algorithm THIS FUNCTION [P2] References: Big O: How Code Slows as Data Grows Algorithms Notes for Professionals What do you think this is? Quadratic 𝑂(𝑁2 ) It is 𝑂(log(𝑁))

We can not use the time to measure the performance of an algorithm. So what to doe? • 𝑂(1): Constant time • 𝑂(log(𝑁)): Logarithmic running time • 𝑂(𝑁): Linear running time • 𝑂(𝑁2 ): Quadratic. Polynomials running time. • 𝑂(2𝑁 ): Exponential running time • 𝑂(! 𝑁): Factorial running time 26 BIG-O NOTATION BIG-O COMPLEXITY MOST COMMON PATTERNS References: Big O: How Code Slows as Data Grows Algorithms Notes for Professionals

• How the code slows as the data grows (Big-O notation used to ) • What does the algorithm do? • What is the output of the • algorithm if N was 15? 27 Big-O Notation What is the output of the following algorithm? References: Algorithms Notes for Professionals Big O Cheatsheet

• What is the Big-O notation for the following algorithm? • Is there anyway to enhance it? 29 Quiz [1] What is the time complexity of the following? Start Total = 0 i = 0 Read N Is count < N Print N Total = Total + N i = i + 1 End

31 Definition: Pseudocode is an artificial and informal language that helps programmers develop algorithms. It is a "text- based" step-by-step design tool. Basic common pseudocode: - Assignment a ← expression - Arithmetic operators and numeric procedures a + b, a – b, a * b, a / b - Relational and Boolean operators a = b, a ≠ b, a > b, a < b, a ≥ b, a ≤ b - Condition Evaluates to true if condition is true; otherwise evaluates to false. Evaluates to true if both condition1 and condition2 are true or condition3 is true; - Iterations Repeat n Times { < Your logic here > } Repeat Until (condition) { < Your logic here > } - Procedures Procedure name (parameter1, parameter2, ...) { < Your logic here > Return (expression) } On Algorithms, Pseudocode References: PSEUDOCODE GUIDE

Find any simple problem, and design two different algorithms that lead to the same result: • Use the flowcharts you learnt about today to present your algorithms • What is the time complexity (Big-O notation) of the algorithms that you are going to design • Write the pseudocode of your algorithms Read Chapter 3 of [Algorithms: Notes for Professional] and: • Summarize Big-Theta notation • Summarize Big-Omega Notation 33 DEADLINE 27/5 3/6, HOMEWORK

Class[1][23ed may] [algorithms]

More Related Content

What's hot

Similar to Class[1][23ed may] [algorithms]

Recently uploaded

Class[1][23ed may] [algorithms]