Урок без названия

Tutorial – 2

Solving problems on O, o, Ω, Θ notations

Programming simple graph types

Mr. Khumoyun Aminaddinov

Computing Fibonacci
numbers

● What is Big-O ?
● What is small o ?
● What is omega ?
● What is theta ?

O(n)

Let’s recap:
● Asymptotics

https://www.geeksforgeeks.org/diff
erence-between-big-oh-big-omega-
and-big-theta/

Let’s recap:
● Asymptotics
● Comparison

Let’s recap:
● What is graph ?
● Why we need them ?

Task 1

Depth First Search or DFS for a Graph.
Depth First Traversal (or DFS) for a graph is similar to
Depth First Traversal of a tree. The only catch here is,
that, unlike trees, graphs may contain cycles (a node
may be visited twice). To avoid processing a node more
than once, use a boolean visited array. A graph can have
more than one DFS traversal.

Task 2

Shortest path in a Binary Maze
Given an MxN matrix where each element can either be
0 or 1. We need to find the shortest path between a
given source cell to a destination cell. The path can only
be created out of a cell if its value is 1.

Task 3

Print all paths from a given source to a
destination

Given a directed graph, a source vertex ‘s’ and a
destination vertex ‘d’, print all paths from given ‘s’ to ‘d’.
Consider the following directed graph. Let the s be 2
and d be 3. There are 3 different paths from 2 to 3.

Task 4

Find the number of islands
using DFS

Given a binary 2D matrix, find the number of islands. A
group of connected 1s forms an island. For example,
the below matrix contains 4 islands.

Task 5

How to find Shortest Paths from
Source to all Vertices using
Dijkstra’s Algorithm

Given a graph and a source vertex in the graph, find the
shortest paths from the source to all vertices in the
given graph.