Lec 10

M269
Algorithms, Data
Structures and
Computability

BY:
DR. AHMED GAWISH
A.GAWISH@ARABOU.EDU.KW
 Agenda
1] Continue The Graphs Algorithms: Floyd-Warshall Algo.
2] Paradigms of Algorithms:
• Brute Force
• Greedy Algorithm
• Divide and Conquer
• Dynamic Programming
• Optimization Programming
3] Types of Problems:
• P, NP, NP-Hard Problems
4] Database – SQL
Floyd-Warshall
(Dynamic Programming)
• Floyd - Warshall is an algorithm that finds the shortest path
between every pair of vertices in a graph (all pairs, shortest paths).
• It supports negative edge-weights, but not negative-weight cycles.
• Runs in O(n3) time
• Increases number of hops allowed by 1 with each iteration

What is the difference between Floyd-Warshall and Dijkstra’s??

Dijkstra’s: Shortest path from one node to all nodes
Floyed-Warshall: Shortest path between all pairs of vertices,
negative edges allowed
 Floyd-Warshall Algorithm
•IfV is the number of vertices, Dijkstra’s runs in
(V2)
• We could just call Dijkstra |V| times, passing a different
source vertex each time.
• (V  V ) = (V )
2 3

• (Which is the same runtime as the Floyd-Warshall

Algorithm)

• BUT, Dijkstra’s doesn’t work with negative-weight

edges.
 Floyd-Warshall Algorithm
• A weighted, directed graph is a collection vertices connected
by weighted edges (where the weight is some real number).
• Adjacency Matrix:
• Let D be an edge-weighted graph in adjacency-matrix form
• D(i,j) is the weight of edge (i, j), or ¥ if there is no such edge.
• Update matrix D, with the shortest path through
immediate vertices.

Tampa Orlando Jaxville

1.5
Tampa Orlando
Tampa 0 1.7 3.5 1.7

Orlando 1.5 3.5

0 ∞ 4 2.5

Jax 4 2.5 0 Jacksonville

Floyd Warshall Algorithm
- Example

Original weights.

Consider Vertex 1:
D(3,2) = D(3,1) + D(1,2)

Consider Vertex 2:
D(1,3) = D(1,2) + D(2,3)

Consider Vertex 3:
Nothing changes.
 Algorithm Pseudo Code
Floyd Warshall Algorithm –
Example
A fast method

How to do these calculations in

a very fast way:
https://www.youtube.com/watch
?v=i9SZKy2yTZw&t=26s
Exercise:
 Dynamic Programming
• Dynamic Programming is an algorithm design technique for
optimization problems: often minimizing or maximizing.
“Programming” here means “planning”
• Like divide and conquer, DP solves problems by combining
solutions to subproblems.
• Unlike divide and conquer, subproblems are not
independent.
• Subproblems may share subsubproblems,
• However, solution to one subproblem may not affect the solutions
to other subproblems of the same problem. (More on this later.)
• DP reduces computation by
• Solving subproblems in a bottom-up fashion.
• Storing solution to a subproblem the first time it is solved.
• Looking up the solution when subproblem is encountered again.
• Key: determine structure of optimal solutions
Steps in Dynamic Programming

1. Characterize structure of an optimal solution.

2. Define value of optimal solution recursively.
3. Compute optimal solution values either top-down with
caching or bottom-up in a table.
4. Construct an optimal solution from computed values.
 Example: Fibonacci numbers
• Recall definition of Fibonacci numbers:

F(n) = F(n-1) + F(n-2)

F(0) = 0
F(1) = 1

• Computing the nth Fibonacci number recursively (top-down):

F(n) Please see the following

video, it will help you to
F(n-1) + F(n-2) understand the idea:
https://www.youtube.com/wat
F(n-2) + F(n-3) F(n-3) + F(n-4) ch?v=mmjDZGSr7EA

...
0 1 1 . . . F(n-2) F(n-1) F(n)
Efficiency:
- time n What if we solve it
- space n
recursively?
2n
 Paradigms of Algorithms
• Brute force: In computer science, brute-force search or exhaustive search, also
known as generate and test, is a very general problem-solving technique that
consists of systematically enumerating all possible candidates for the solution and
checking whether each candidate satisfies the problem's statement. e.g. Selection
and insertion sort algorithms…naïve pattern matching algorithm.
• Greedy Algorithms: The solution is constructed through a sequence of steps. At
each step the next optimal step is selected locally, without considering whether this
step leads to the final global optimal solution or not. e.g. Kruskal, Dijkstra algorithm.
• Divide-and-Conquer: Divide the problem instance to several smaller sub-instances
then solve each one independently. Finally, the solutions of these sub-instances are
combined to form final solution. e.g. Merge and quick sort algorithm.
• Dynamic Programming: Solve problem of divide-conquer where identical sub-
instances are computed repeatedly. Smallest sub-instances are solved first and
results are placed in table to be used to construct larger sub-instances solution. e.g.
Floyd-Warshall algorithm.
• Optimization Programming: Optimization is the selection of a best element from set
of available alternatives. In general, optimization includes finding "best available"
values of some objective function given a defined domain (or input), including a
variety of different types of objective functions and different types of domains. e.g.
genetic algorithm, ant colony algorithm.
The types of problems: • https://www.youtube.com/watch?v=YX40h
P, NP, NP-Complete, NP-Hard problem bAHx3s
• https://www.youtube.com/watch?v=Ig0ESj
• P problems are questions that have a yes/no 4NmAk
answer and can be easily solved by a computer. For
example, determining whether a number is prime is a relatively easy problem to solve.
• NP problems are questions that have yes/no answers that are easy to verify, but are hard to solve.
And by hard, I mean it would take years, decades or centuries for your computer to come up with an
answer. For example, the travelling salesman problem is trying to figure out the shortest trip through a
bunch of cities, visiting each city only once. Let's say you ask me the question, can I visit these 500
cities in my state and spend less than 3000 miles on the road? If I magically show you an itinerary that
takes you to all those 500 cities, you can easily verify whether that itinerary is less than 3000 miles.
BUT, trying to come up with that itinerary in the first place is really hard for computers.
• NP-complete problems are special kinds of NP problems. You can take any kind of NP problem and
twist and contort it until it looks like an NP-complete problem. For example, the knapsack problem is
NP. It can ask what's the best way to stuff a knapsack if you had lots of different sized pieces of
different precious metals lying on the ground , and that you can't carry all of them in the bag.
Surprisingly, there are some tricks you can do to convert this problem into a travelling salesman
problem. In fact, any NP problem can be made into a travelling salesman problem, which makes
travelling salesman NP-complete.
• NP-Hard problems are worst than NP problems. Even if someone suggested you a solution to a NP-
Hard problem, it'd still take forever to verify if they were right. For example, in travelling salesman,
trying to figure out the absolute shortest path through 500 cities in your state would take forever to
solve. Even if someone walked up to you and gave you an itinerary and claimed it was the absolute
shortest path, it'd still take you forever to figure out whether he was a liar or not.
SQL Introduction
Standard language for querying and manipulating data

Structured Query Language

Data Definition Language (DDL)
Create/alter/delete tables and their attributes
Data Manipulation Language (DML)
Query one or more tables

14
 Database Management System
SELECT * FROM
city WHERE name
LIKE Ban%

Database
Client Manager

User Interface & Control access to the Database: a structured, self-

communication database. describing collection of data.
protocol • authentication
• enforce permissions
• data integrity
• access services
 Client - Server Databases
• Database Server is a separate process on a host.
• Clients can be on any machine.
• Many programs may be clients using a standard API.
"mysql" utility
Server
mysqld

Java App
+JDBC client
server controls
access to database
Excel client

Client side Server side

 Data Types in SQL
• Characters:
• CHAR(20) -- fixed length
• VARCHAR(40) -- variable length
• Numbers:
• BIGINT, INT, SMALLINT, TINYINT
• REAL, FLOAT -- differ in precision
• MONEY
• Times and dates:
• DATE
• DATETIME -- SQL Server
17

• Others... All are simple

 Table name Attribute names

Product
Tables in SQL
PName Price Category Manufacturer

Gizmo $19.99 Gadgets GizmoWorks

Powergizmo $29.99 Gadgets GizmoWorks

SingleTouch $149.99 Photography Canon

MultiTouch $203.99 Household Hitachi

18

Tuples or rows
 Tables Explained

• A tuple = a record
• Restriction: all attributes are of atomic type
• A table = a set of tuples
• Like a list…
• …but it is unordered: no first(), no next(), no last().

19
 Tables Explained

• The schema of a table is the table name and its attributes:

Product(PName, Price, Category, Manfacturer)

• A key is an attribute whose values are unique;

we underline a key
Product(PName, Price, Category, Manfacturer)

20
 SQL Query
Basic form: (plus many more bells and whistles)

SELECT
SELECT attributes
attributes
FROM
FROM relations
relations(possibly
(possiblymultiple)
multiple)
WHERE
WHERE conditions
conditions(selections)
(selections)

21
 Simple SQL Query
Product PName Price Category Manufacturer
Gizmo $19.99 Gadgets GizmoWorks
Powergizmo $29.99 Gadgets GizmoWorks
SingleTouch $149.99 Photography Canon
MultiTouch $203.99 Household Hitachi

SELECT
SELECT **
FROM
FROM Product
Product
WHERE category=‘Gadgets’
WHERE category=‘Gadgets’

PName Price Category Manufacturer

“selection” Gizmo $19.99 Gadgets GizmoWorks
Powergizmo $29.99 Gadgets GizmoWorks 22
 Simple SQL Query
Product PName Price Category Manufacturer
Gizmo $19.99 Gadgets GizmoWorks
Powergizmo $29.99 Gadgets GizmoWorks
SingleTouch $149.99 Photography Canon
MultiTouch $203.99 Household Hitachi

SELECT
SELECT PName,
PName,Price,
Price,Manufacturer
Manufacturer
FROM
FROM Product
Product
WHERE
WHERE Price
Price>>100
100

PName Price Manufacturer

“selection” and
“projection” SingleTouch $149.99 Canon
MultiTouch $203.99 Hitachi 23
 Selections
What goes in the WHERE clause:
• x = y, x < y, x <= y, etc
• For number, they have the usual meanings
• For CHAR and VARCHAR: lexicographic
ordering
• Expected conversion between CHAR and VARCHAR

• For dates and times, what you expect...

• Pattern matching on strings... 24
 The LIKE operator
• s LIKE p: pattern matching on strings
• p may contain two special symbols:
• % = any sequence of characters
• _ = any single character

Product(PName, Price, Category, Manufacturer)

Find all products whose name mentions ‘gizmo’:
SELECT
SELECT **
FROM
FROM Products
Products 25
WHERE
WHERE PName
PNameLIKE
LIKE‘%gizmo%’
‘%gizmo%’
 Eliminating Duplicates
Category
SELECT
SELECT DISTINCT
DISTINCTcategory
category Gadgets
FROM
FROM Product
Product Photography
Household

Compare to:

Category
Gadgets
SELECT
SELECT category
category Gadgets
FROM
FROM Product
Product Photography
Household
26
 Ordering the Results
SELECT
SELECT pname,
pname,price,
price,manufacturer
manufacturer
FROM
FROM Product
Product
WHERE
WHERE category=‘gizmo’
category=‘gizmo’AND
ANDprice
price>>50
50
ORDER
ORDERBY
BY price,
price,pname
pname

Ordering is ascending, unless you specify the DESC keyword.

Ties are broken by the second attribute on the ORDER BY list, etc.

27
 Ordering the Results
SELECT
SELECT category
category
FROM
FROM Product
Product
ORDER
ORDERBY
BY pname
pname

PName Price Category Manufacturer

?
Gizmo $19.99 Gadgets GizmoWorks
Powergizmo $29.99 Gadgets GizmoWorks
SingleTouch $149.99 Photography Canon
MultiTouch $203.99 Household Hitachi

28
 Joins in SQL
PName Price Category Manufacturer
Gizmo $19.99 Gadgets GizmoWorks
Product Powergizmo $29.99 Gadgets GizmoWorks
SingleTouch $149.99 Photography Canon
MultiTouch $203.99 Household Hitachi

• Connect two or more tables:

Company Cname StockPrice Country

GizmoWorks 25 USA
What is
the connection Canon 65 Japan 29
between
them ? Hitachi 15 Japan
 Joins
Product (pname, price, category, manufacturer)
Company (cname, stockPrice, country)

Find all products under $200 manufactured in Japan;

return their names and prices.

Join
between Product
SELECT pname, and Company
SELECT pname,price
price
FROM
FROM Product,
Product,Company
Company
WHERE
WHERE manufacturer=cname
manufacturer=cnameAND
ANDcountry=‘Japan’
country=‘Japan’
AND
ANDprice
price<=<=200
200

30
 Joins in SQL
Product
Company
PName Price Category Manufacturer
Cname StockPrice Country
Gizmo $19.99 Gadgets GizmoWorks
GizmoWorks 25 USA
Powergizmo $29.99 Gadgets GizmoWorks
Canon 65 Japan
SingleTouch $149.99 Photography Canon
Hitachi 15 Japan
MultiTouch $203.99 Household Hitachi

SELECT
SELECT pname,
pname,price
price
FROM
FROM Product,
Product,Company
Company PName Price
WHERE
WHERE manufacturer=cname AND
manufacturer=cname ANDcountry=‘Japan’
country=‘Japan’ SingleTouch $149.99
AND price <= 200
AND price <= 200

31
 Joins
Product (pname, price, category, manufacturer)
Company (cname, stockPrice, country)

Find all countries that manufacture some product in the ‘Gadgets’ category.

SELECT
SELECT country
country
FROM
FROM Product,
Product,Company
Company
WHERE
WHERE manufacturer=cname
manufacturer=cnameAND
ANDcategory=‘Gadgets’
category=‘Gadgets’

32
Product
Joins in SQL
Company
Name Price Category Manufacturer
Cname StockPrice Country
Gizmo $19.99 Gadgets GizmoWorks
GizmoWorks 25 USA
Powergizmo $29.99 Gadgets GizmoWorks
Canon 65 Japan
SingleTouch $149.99 Photography Canon
Hitachi 15 Japan
MultiTouch $203.99 Household Hitachi

SELECT
SELECT country
country Country
FROM
FROM Product,
Product,Company
Company ??
WHERE
WHERE manufacturer=cname
manufacturer=cnameAND
ANDcategory=‘Gadgets’
category=‘Gadgets’ ??

33
Thank You