1 of 125

​

ANALYSIS AND DESIGN OF ALGORITHMS

​

(BCS401)

​

1

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

1

2 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

2

3 of 125

​

​

DESIGN AND ANALYSIS OF ALGORITHMS(18CS42)

Module 1

Syllabus :

Introduction:

What is an Algorithm?its properties, Algorithm Specification, Analysis Framework, Performance Analysis: Space complexity, Time complexity.

Asymptotic Notations:

Big-Oh notation (O), Omega notation (Ω), Theta notation (Θ), and Little-oh notation (o), Mathematical analysis of Non-Recursive and recursive Algorithms with Examples..

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

3

4 of 125

Brute Force Design Technique:

Selection sort ,sequential search, string matching algorithm with complexity Analysis

​

Text Book -  Introduction to the Design and Analysis of Algorithms, Anany Levitin:, 2nd Edition, 2009. Pearson.

Chapter 2 and Chapter 3

​

4

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

4

5 of 125

Text Book -1

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

5

6 of 125

Text Book -2

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

6

7 of 125

Algorithm

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

7

8 of 125

How to prepare tea?

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

8

9 of 125

How to prepare Maggi noodles?

  1. Take one and a half cup of Water in a pan.
  2. Heat the pan on medium flame.
  3. When the Water comes to boil, add the Maggi to the pan.
  4. Cover it with a lid for a minute.
  5. After a minute, uncover the lid and add the tastemaker to the pan.
  6. Mix it well, Without breaking the Noodles.
  7. Just when all of your Water is boiled, switch off the flame.
  8. Enjoy the hot Maggi.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

9

10 of 125

Shortest Distance between two cities

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

10

11 of 125

Module 1 – Outline Introduction to Algorithms

  1. Introduction
  2. Performance Analysis
  3. Asymptotic Notations
  4. Brute Force Design Technique

​

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

11

12 of 125

What is an Algorithm?

  • An algorithm is a finite sequence of unambiguous instructions to solve a particular problem.

​

​

​

​

​

​

​

​

​

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

12

13 of 125

  • In addition, all algorithms must satisfy the following properties:

​

    • Definiteness: Each instruction is clear and unambiguous.
    • Finiteness: algorithm terminates after a finite number of � steps.
    • Correctness: Must work for valid inputs and are specified
    • Effectiveness: Every instruction must be very basic so that it clearly can be carried out , in principle, by a person using pencil and paper. In general steps are sufficiently simple and basic.
    • Input: Zero or more quantities are externally supplied.
    • Output: At least one quantity is produced.

​

​

13

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

13

14 of 125

Algorithm specification

  • An algorithm can be specified in
    1. Natural Language like English
    2. Pseudo code convention
    3. Graphical representation like flow chart
    4. Programming language like c++ , java, python etc
    5. Combination of above methods.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

14

15 of 125

1.Natural Language like English

For example: Euclid(m,n)

While(n!=0) do Step1: if n=0 return the value of m as the answer & stop; � otherwise proceed to step2

r<-m%n Step2:Divide m by n and assign the value of the � remainder to r

m<-n Step3:Assign the value of n to m &value of r to n goto step1

n<-r

Return m

15

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

15

16 of 125

2.Pseudo code convention

A pseudo code is a combination of a natural language and programming language. A pseudo code is usually more precise than a natural language.

​

​

16

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

16

17 of 125

Algorithm Specification for pseudo code

1.Comment is specified using //

2.Algorithm header is specified as algorithm Name with � parameter list().

3.Specify algorithms inputs and the required outputs.

4.Compound statements are specified with {} or begin…end

​

​

​

​

17

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

17

18 of 125

5.For if statement(branching statement)

if(condition)

statement1;

statement 2;

else

statements

endif

​

6.For looping statement

a)while(condition)do b)repeat c)for variable🡨value1 to value2 do

….. ----- -------

…… ------ --------

endwhile until(condition) endfor

​

​

18

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

18

19 of 125

19

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

19

20 of 125

Fundamentals of Algorithmic problem solving/

Algorithm design and analysis process

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

20

21 of 125

Step1.Understanding the Problem

Before designing the algorithm one must completely understand the Statement of the problem.so read the problem description carefully think about special cases. If the problem in the question is known one can use already existing algorithms otherwise design your own.It is Important to specify the exact range of inputs the algorithm must handle.

Step 2:Decide on

*Computational Devices: Once the problem is understood then we need to decide upon Computational Devices needed to implement the program.Von Neumann machine is a computer Architecture it uses RAM.Its central assumption is that instructions are executed one after the another.algorithms designed to be executed on such machines are called Sequential Algorithms. Some newer computers can execute operations concurrently i.e parallel.algorithms that take advantage of this capability are called parallel algorithms.

21

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

21

22 of 125

*Exact and Approximate Problem Solving:next to decide upon the whether to solve the problem Exactly or Approximately.

*Appropriate Data Structure

*Algorithm Design Technique:An algorithm design technique is a general approach to solving problems algorithmically that is applicable to variety of problems from different areas of computing.

22

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

22

23 of 125

Step 3:Design Algorithm

Once the technique is decided we should specify(design) the algorithm in natural Language, pseudocode ,flow chart using any of the specification.

Step 4:Prove the Correctness

once the algorithm has been specified one has to prove its correctness. that is algorithm yields a required result for every valid input in a finite amount of time.

Step 5:Analyzing an algorithm: There are two kinds of algorithm efficiency say time and space.how fast the algorithm runs and how much extra memory the algorithm needs.

Step 6:Coding an Algorithm :coding algorithm using any of the programming language.

23

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

23

24 of 125

​

Analysis Framework:

A general framework for analyzing the efficiency of algorithms. There are two kinds of efficiency Time,Space.

Space efficiency deals with the extra space the algorithm requires to run.

Time efficiency Indicates how fast an algorithm runs.

  • Measuring an Input’s Size: All algorithms run longer on larger inputs.For example ,it takes longer to sort larger arrays,Multiply larger matrices & so on.
  • Units for Measuring Running time:Identify the most important operation of the algorithm called Basic Operation,The operation which is contributing most to the total running time.

-Basic operation:is usually the most time-consuming operation in the algorithms innermost loop.

  • Order of Growth

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

24

25 of 125

Orders of Growth

  • The order in which time increases W.R.T input is called as order of the growth.It is the relationship between input size and the time consumed for running an algorithm as the input size increases,the time consumed increases in a particular order
  • Because for large values of n, it is the function's order of growth that counts.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

25

26 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

26

27 of 125

Analysis Framework

  • Worst-Case
  • Best-Case
  • Average-Case Efficiencies

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

27

28 of 125

Worst Case

  • Definition: The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n, for which the algorithm runs the longest among all possible inputs of that size.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

28

29 of 125

Best Case

  • Definition: The best-case efficiency of an algorithm is its efficiency for the best-case input of size n, for which the algorithm runs the fastest among all possible inputs of that size.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

29

30 of 125

Average Case

  • Definition: the average-case complexity of an algorithm is the amount of time used by the algorithm, averaged over all possible inputs.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

30

31 of 125

Asymptotic Notations

  • To compare orders of growth, computer scientists use three notations:
    • O(big oh),
    • Ω(big omega),
    • Θ (big theta) and

​

    • o(little oh)

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

31

32 of 125

Performance Analysis

  • Space complexity
    • Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size.
    • Space complexity includes both Auxiliary space and space used by input.
  • Time complexity

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

32

33 of 125

Time Complexity

  • Execution time or run-time of the program is refereed as its time complexity
  • This is the sum of the time taken to execute all instructions in the program.
  • But, We count only the number of steps in the program. Why?
  • How to count?

– Two ways

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

33

34 of 125

​

​

Trade-off

  • One has to make a compromise and to exchange computing time for memory consumption or vice versa, depending on application.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

34

35 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

35

36 of 125

Recursive Algorithm

  • An algorithm is said to be recursive if the same algorithm is invoked in the body (direct recursive).
  • Algorithm A is said to be indirect recursive if it calls another algorithm which in turn calls A.
  • Example 1: Factorial computation n! = n * (n-1)!
  • Example 2: Binomial coefficient computation

​

​

  • Example 3: Tower of Hanoi problem
  • Example 4: Permutation Generator

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

36

37 of 125

Method-1

  • Introduce a count variable
  • Increment count for every operation

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

37

38 of 125

Method-2

  • Count the steps per execution for every line of code
  • Note the frequency of execution of every line and find the total steps.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

38

39 of 125

Method-2

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

39

40 of 125

Summary of analysis framework

  • Both time and space efficiencies are measured as functions of the algorithm's input size.
    • Time efficiency - basic operation
    • Space efficiency - extra memory units
  • The efficiencies of some algorithms may differ significantly for inputs of the same size.
    • For such algorithms, we need to distinguish between the worst-case, average-case, and best-case efficiencies.

​

  • The primary interest lies in the order of growth of the algorithm's running time (or extra memory units consumed) as its input size goes to infinity.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

40

41 of 125

.

Big-Oh notation

A function t(n) is said to be in O(g(n)),

denoted t(n)∈ O(g(n)),

if t (n) is bounded above by some constant multiple of g(n) for all large n,

i.e., if there exist some positive constant c and some nonnegative integer n0 such that

t(n) ≤ c g(n) for all n ≥ n0.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

41

42 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

42

43 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

43

44 of 125

Problems on Big O

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

44

45 of 125

Omega notation

A function t(n) is said to be in Ω(g(n)), denoted t(n)∈ Ω(g(n)),

if t(n) is bounded below by some positive constant multiple of g(n) for all large n,

i.e., if there exist some positive constant c and some nonnegative integer n0 such that

t(n) ≥ c g(n) for all n ≥ n0.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

45

46 of 125

Big Omega t(n)= Ω(g(n))

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

46

47 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

47

48 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

48

49 of 125

Theta Notation

A function t(n) is said to be in Θ(g(n)), denoted t(n) ∈

Θ(g(n)),

if t (n) is bounded both above and below by some positive constant multiples of g(n) for all large n,

i.e., if there exist some positive constants c1 and c2 and some nonnegative integer n0 such that

c2 g(n) ≤ t(n) ≤ c1g(n) for all n ≥ n0.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

49

50 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

50

51 of 125

Graphical representation

  • Which one best to represent order of growth

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

51

52 of 125

Strategies for Ω and Θ

  • Proving that a f(n) = Ω(g(n)) often requires more thought.
    • Quite often, we have to pick c < 1.
    • A good strategy is to pick a value of c which you think will work, and determine which value of n0 is needed.
    • Being able to do a little algebra helps.
    • We can sometimes simplify by ignoring terms of f(n) with the positive coefficients.
  • The following theorem shows us that proving f(n) = Θ(g(n)) is nothing new:
    • Theorem: f(n) = Θ(g(n)) if and only iff(n) = O(g(n)) and f(n) = Ω(g(n)).
    • Thus, we just apply the previous two strategies.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

52

53 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

53

54 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

54

55 of 125

Problem-3

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

55

56 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

56

57 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

57

58 of 125

Little Oh

  • The function f(n) = o(g(n)) [ i.e f of n is a little oh of g of n ] if and only if

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

58

59 of 125

  • For comparing the order of growth limit is used

Little Oh

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

59

60 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

60

61 of 125

Theorem: If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)), then t1(n) + t2(n) ∈

O(max{g1(n), g2(n)}).

(The analogous assertions are true for the Ω and Ө notations as well.)

​

Proof:

The proof extends to orders of growth the following simple fact about four arbitrary real numbers a1, b1, a2, b2:

if a1 ≤ b1 and a2 ≤ b2, then a1 + a2 ≤ 2 max{b1, b2}.

Since t1(n) ∈ O(g1(n)), there exist some positive constant c1 and some nonnegative integer n1 such that

t1(n) ≤ c1g1(n) for all n ≥ n1.

​

Similarly, since t2(n) ∈ O(g2(n)), t2(n) ≤ c2g2(n) for all n ≥ n2.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

61

62 of 125

Theorem: If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)), then t1(n) + t2(n) ∈

O(max{g1(n), g2(n)}).

(The analogous assertions are true for the Ω and Ө notations as well.)

​

Proof: (continued):

Let us denote c3 = max{c1, c2} and consider n ≥ max{n1, n2} so that we can use both inequalities.

Adding them yields the following: t1(n) + t2(n) ≤ c1g1(n) + c2g2(n)

≤ c3 g1(n) + c3g2(n) = c3[g1(n) + g2(n)]

≤ c32 max{g1(n), g2(n)}.

Hence, t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}), with the constants c and n0 required by the O definition being 2c3 = 2 max{c1, c2} and max{n1, n2}, respectively.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

62

63 of 125

Basic Efficiency classes

Class

Name Comments

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

63

64 of 125

Class

Name

Comments

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

64

65 of 125

Quiz: Which kind of growth best characterizes each of these functions?

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

65

66 of 125

Mathematical Analysis of Non-recursive Algorithms

  1. Decide on a parameters indicating an input’s size.
  2. Identify the algorithm’s basic operation.
  3. Check whether the number of times the basic operation is executed depends only on the size of an input.

If it also depends on some additional property, the worst- case, average-case, and, if necessary, best-case efficiencies have to be investigated separately.

  1. Set up a sum expressing the number of times the algorithm’s basic operation is executed.
  2. Using standard formulas and rules of sum manipulation, either find a closed form formula for the count or, at the very least, establish its order of growth.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

66

67 of 125

67

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

67

68 of 125

68

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

68

69 of 125

69

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

69

70 of 125

Best, Worst, Average case exist?

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

70

71 of 125

Best, Worst, Average case exist?

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

71

72 of 125

Best, Worst, Average case exist?

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

72

73 of 125

Analysis

Best, Worst, Average case exist?

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

73

74 of 125

The basic operation is count=count + 1 repeats times

number of

Best, Worst, Average case exist?

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

74

75 of 125

Analysis of Recursive Algorithms

  1. Decide on a parameter indicating an input’s size.
  2. Identify the algorithm’s basic operation.
  3. Check whether the number of times the basic operation is executed can vary on different inputs of the same size;

if it can, the worst-case, average-case, and best-case efficiencies must be investigated separately.

  1. Set up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation is executed.

​

5.Solve the recurrence or, at least, ascertain the order of growth of its solution.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

75

76 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

76

77 of 125

  • We can use backward substitutions method to solve this

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

77

78 of 125

Tower of Hanoi puzzle.

  • In this puzzle, There are n disks of different sizes that can slide onto any of three pegs.
  • Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top.
  • The goal is to move all the disks to the third peg, using the second one as an auxiliary, if necessary.
  • We can move only one disk at a time, and it is forbidden to place a larger disk on top of a smaller one.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

78

79 of 125

Tower of Hanoi puzzle.

  • The problem has an elegant recursive solution
  • To move n>1 disks from peg 1 to peg 3 (with peg 2 as auxiliary),
    • we first move recursively n-1 disks from peg 1 to peg 2 (with peg 3 as auxiliary),
    • then move the largest disk directly from peg 1 to peg 3, and,
    • finally, move recursively n-1 disks from peg 2 to peg 3 (using peg 1 as auxiliary).
  • If n = 1, we move the single disk directly from the source peg to the destination peg.

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

79

80 of 125

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

80

81 of 125

Algorithm

TowerOfHanoi(n, source, dest, aux)

If n == 1, then

move disk from source to dest else

TowerOfHanoi (n - 1, source, aux, dest) move disk from source to dest TowerOfHanoi (n - 1, aux, dest, source)

End if

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

81

82 of 125

Recurrence relation for total number of moves

The number of moves M(n) depends only on n. The recurrence equation is

We have the following recurrence relation for the number of moves M(n):

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

82

83 of 125

  • We solve this recurrence by the same method of backward substitutions:
  • The pattern of the first three sums on the left suggests that the next one will be

24 M(n − 4) + 23 + 22 + 2 + 1, and

generally, after i substitutions, we get

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

83

84 of 125

  • Since the initial condition is specified for n = 1, which is achieved for i = n - 1,

we get the following formula for the solution to recurrence

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

84

85 of 125

Example 3

  • Basic operation is Addition
  • The recurrence relation can be written as

​

  • Assuming n = 2k

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

85

86 of 125

Recurrence relation for basic operation

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

86

87 of 125

Brute Force Design Technique

A brute force approach is an approach that finds all the possible solutions to find a satisfactory solution to a given problem. The brute force algorithm tries out all the possibilities till a satisfactory solution is not found.

Topics : 1.Selection Sort

2.Sequential Search

3.String Matching Algorithm With complexity Analysis

Text Book1-3.1,3.2

87

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

87

88 of 125

Selection Sort

How Selection Sort works

  • In the selection sort, first of all, we scan the entire given list to find its smallest element and exchange it with the first element ,putting the smallest element in its final position in the sorted list.
  • Then we scan the list, starting with the second element , to find the smallest among the last n-1 elements and exchange it with the second element, putting the second smallest element in its final position in the sorted list. Procedure is as follows
  • set the initial element as a minimum.
  • Now we will compare the minimum with the second element. If the second element turns out to be smaller than the minimum, we will swap them, followed by assigning to a minimum to the third element.

​

88

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

88

89 of 125

3. Else if the second element is greater than the minimum, which is our � first element, then we will do nothing and move on to the third element � and then compare it with the minimum.� We will repeat this process until we reach the last element.

  1. After the completion of each iteration, we will notice that our minimum has reached the start of the unsorted list.
  2. For each iteration, we will start the indexing from the first element of the unsorted list. We will repeat the Steps from 1 to 4 until the list gets sorted or all the elements get correctly positioned.�Consider the following example of an unsorted array that we will sort with the help of the Selection Sort algorithm.

​

89

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

89

90 of 125

A [] = (7, 4, 3, 6, 5).

​

1st Iteration:

  • Set minimum = 7
  • Compare a0 and a1

​

90

4/16/2024

  • Compare a2 and a3

As, a2 < a3, set minimum= 3.

  • Compare a2 and a4

As, a2 < a4, set minimum =3.

Since 3 is the smallest element, so we will swap a0 and a2.

  • Compare a1 and a2

As, a1 > a2, set minimum = 3.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

90

91 of 125

2nd Iteration:

Set minimum = 4

  • Compare a1 and a2

​

91

4/16/2024

As, a1 < a2, set minimum = 4.

  • Compare a1 and a3

As, A[1] < A[3], set minimum = 4.

  • Compare a1 and a4

Again, a1 < a4, set minimum = 4.

Since the minimum is already placed in the correct position, so there will be no swapping.

3rd Iteration:

Set minimum = 7

  • Compare a2 and a3

As, a2 > a3, set minimum = 6.

  • Compare a3 and a4

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

91

92 of 125

As, a3 > a4, set minimum = 5.

92

4/16/2024

Since 5 is the smallest element among the leftover unsorted elements, so we will swap 7 and 5.

4th Iteration:

Set minimum = 6

  • Compare a3 and a4

As a3 < a4, set minimum = 6.

Since the minimum is already placed in the correct position, so there will be no swapping.

Sorted Array is

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

92

93 of 125

Algorithm :

SelectionSort(A[0…n-1])

//sorts a given array by selection sort

//Input:An unsorted array A[0…n-1]

//Output:Sorted array A[0…n-1] in ascending order

for i 🡨 0 to n-2 do (One loop to select an element of Array one by one)

min🡨 i

for j 🡨 i+1 to n-1 do (Another loop to compare that element with every other Array element)

if A[j] < A[min]

min 🡨 j

Swap A[i] and A[min]

​

93

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

93

94 of 125

Complexity Analysis of Selection Sort

Step 1:Input size is given by the no.of elements in an array say n

Step2 :Basic operation is the key comparison A[j]<A[min]

Step3 :the no of times B.O is executed depends on input size n

C(n)=Ʃ Ʃ 1= Ʃ[(n-1)-(i+1)+1]= Ʃ (n-1-i)

= (by replacing i=0 ,1..n-2)

​

=

(n2 ) however no of key comparisons are only (n)

94

4/16/2024

n-2

i=0

n-1

j=i+1

n-2

i=0

n-2

i=0

ɵ

ɵ

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

94

95 of 125

Sequential Search

  • Two popular search methods are Linear Search and Binary Search. So, here we will discuss Linear Search Algorithm.
  • Linear Search is defined as a sequential search algorithm.
  •  That starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set.

The steps used in the implementation of Linear Search are listed as follows -

Step 1: First, read the search element (Target element) in the array.

​

95

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

95

96 of 125

  • Step 2: Set an integer i = 0 and repeat steps 3 to 4 till i reaches the end of the array.
  • Step 3: Match the key with A[i].
  • Step 4: If the key matches, return the index. Otherwise, increment i by 1.

Algorithm

SequentialSearch(A[0..n-1],K)

//Input:An array A[0..n-1] and a search key K

//Output:The index of the first element of A that matches K or -1 if there are no matching elements

i<- 0

While i<n and A[i]≠K do

i<-i+1

if i<n return i

else return -1

​

​

96

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

96

97 of 125

  • Illustration of Linear Search:

Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 20

Step 1: Set i = 0 and check key with arr[0].

​

97

4/16/2024

Step 2: key and arr[0] are not the same. So make i = 1 and match key with arr[1].

Compare key with index 1

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

97

98 of 125

Step 3: arr[1] and key are different. Increment i and compare key with arr[2].

​

98

4/16/2024

Compare key with index 2

Step 4: arr[2] is not the same with key. Increment i and compare key with arr[3].

Compare key with index 3

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

98

99 of 125

Step 5: key and arr[3] are different. Make i = 4 and compare key with arr[4].

99

4/16/2024

Compare key with index 4

Step 6: key and arr[4] are not same. Make i = 5 and match key with arr[5].

Compare key with index 5

We can see here that key is present at index 5.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

99

100 of 125

Time Complexity

Step 1:Input size is given by the no.of elements in an array say n

Step2 :Basic operation is the key comparison A[j]<A[min]

Step3 :the no of times B.O is executed depends not only on input size n it also depends on the position of key element present in the given array.so all the 3 cases we should find

  • Best Case Complexity - In Linear search, best case occurs when the element we are finding is at the first position of the array. The best-case time complexity of linear search is O(1).
  • Average Case Complexity - All possible case time/No.of cases

​

​

100

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

100

101 of 125

1+2+3+4+5……..n/n

=(n(n+1)/2)/n

=(n+1)/2

O(n)

When search is successful ,the average no.of key comparisons is (n+1)/2.If the search is unsuccessful the average no.of key comparisons is n because the algorithm will inspect all n elements.

Worst Case Complexity - In Linear search, the worst case occurs when the element we are looking is present at the end of the array. The worst-case in linear search could be when the target element is not present in the given array, and we have to traverse the entire array. The worst-case time complexity of linear search is O(n).

​

101

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

101

102 of 125

102

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

102

103 of 125

103

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

103

104 of 125

104

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

104

105 of 125

105

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

105

106 of 125

  • After the completion of each iteration, we will notice that our minimum has reached the start of the unsorted list.
  • For each iteration, we will start the indexing from the first element of the unsorted list. We will repeat the Steps from 1 to 4 until the list gets sorted or all the elements get correctly positioned.�Consider the following example of an unsorted array that we will sort with the help of the Selection Sort algorithm.

​

106

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

106

107 of 125

  • After the completion of each iteration, we will notice that our minimum has reached the start of the unsorted list.
  • For each iteration, we will start the indexing from the first element of the unsorted list. We will repeat the Steps from 1 to 4 until the list gets sorted or all the elements get correctly positioned.�Consider the following example of an unsorted array that we will sort with the help of the Selection Sort algorithm.

​

107

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

107

108 of 125

  • After the completion of each iteration, we will notice that our minimum has reached the start of the unsorted list.
  • For each iteration, we will start the indexing from the first element of the unsorted list. We will repeat the Steps from 1 to 4 until the list gets sorted or all the elements get correctly positioned.�Consider the following example of an unsorted array that we will sort with the help of the Selection Sort algorithm.

​

108

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

108

109 of 125

Important Problem Types

  • Sorting
    • rearrange the items of a given list in non-decreasing order
    • there is no algorithm that would be the best solution in all situations

Two properties

    • Algorithm is stable if it preserves the relative order of any two equal elements in its input
    • in-place - no extra memory
  • Searching
    • Linear search
    • Binary search

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

109

110 of 125

Important Problem Types

  • String Processing
  • Graph Problems
    • Oldest problems
  • Combinatorial Problems
    • grows extremely fast with a problem’s size
    • there are no known algorithms for solving such problems exactly in an acceptable amount of time

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

110

111 of 125

Fundamental Data structures

  • Linear data structures
    • Array
    • Linked list
      • Singly linked list
      • Doubly linked list
    • List
      • Stack
      • Queue, Priority queue

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

111

112 of 125

Fundamental Data structures

  • Graphs
    • Undirected
    • Directed (Digraph)
  • Weighted graph
  • cycle

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

112

113 of 125

Fundamental Data structures

  • Graph Representations
    • Adjacency matrix
    • Adjacency list

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

113

114 of 125

Fundamental Data structures

  • Graph Representations
    • Weighted graph
    • cycle

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

114

115 of 125

Fundamental Data structures

  • Trees, Forests
    • Rooted tree
    • Depth of vertex v
    • Height of the tree

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

115

116 of 125

116

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

116

117 of 125

Fundamental Data structures

117

4/16/2024

  • Trees, Forests
    • Ordered tree
      • Binary tree
      • Binary search tree

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

117

118 of 125

Fundamental Data structures

118

4/16/2024

  • Sets
    • Set operations
      • Check membership, Union, Intersecection
    • Implementations
      • Bit vector, List

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

118

119 of 125

Fundamental Data structures

119

4/16/2024

  • Dictionaries
    • Searching
    • Adding
    • Deleting

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

119

120 of 125

Extra Byte-1.1: Min Distance

120

4/16/2024

Consider the following algorithm for finding the distance between the two closest elements in an array of numbers. Make as many improvements as you can in this algorithmic solution to the problem. If you need to, you may change the algorithm altogether; if not, improve the implementation given.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

120

121 of 125

Extra Byte-1.2: Secret

121

4/16/2024

Consider the following algorithm.

  1. What does this algorithm compute?
  2. What is its basic operation?
  3. How many times is the basic operation executed?
  4. What is the efficiency class of this algorithm?
  5. Suggest an improvement/better algorithm, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

121

122 of 125

Extra Byte-1.3: Enigma

122

4/16/2024

Consider the following algorithm.

  1. What does this algorithm compute?
  2. What is its basic operation?
  3. How many times is the basic operation executed?
  4. What is the efficiency class of this algorithm?
  5. Suggest an improvement/better algorithm, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

122

123 of 125

Assignment-1 Due: Within 5 days

123

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

123

124 of 125

Class test-1 Max Marks: 20 Duration:45 Mins

124

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

124

125 of 125

End of Module-1

125

4/16/2024

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

/skit.org.in

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

4/16/2024

125