[go: up one dir, main page]
Scribd
Upload
255 views9 pages

6.2 Sum of Subset, Hamiltonian Cycle

This document discusses algorithms and backtracking approaches for solving sum-of-subsets and Hamiltonian cycle problems. It provides examples and explanations of how to use backtracking to find a subset of numbers that sums to a given total (subset sum problem) and how to find a Hamiltonian cycle by starting at a vertex and iteratively selecting adjacent vertices until returning to the starting point. References for further reading on these algorithmic problems and backtracking are also included.

Uploaded by

Suraj kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
255 views9 pages

6.2 Sum of Subset, Hamiltonian Cycle

This document discusses algorithms and backtracking approaches for solving sum-of-subsets and Hamiltonian cycle problems. It provides examples and explanations of how to use backtracking to find a subset of numbers that sums to a given total (subset sum problem) and how to find a Hamiltonian cycle by starting at a vertex and iteratively selecting adjacent vertices until returning to the starting point. References for further reading on these algorithmic problems and backtracking are also included.

Uploaded by

Suraj kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 9

Department of Computer Science and Engineering (CSE)

UNIVERSITY INSTITUTE OF
ENGINEERING
COMPUTER SCIENCE
ENGINEERING
Bachelor of Engineering
Design and Analysis of
Algorithms(CSH-311/ITH-311)

Topic: Sum-of-subsets, Hamiltonian cycles DISCOVER . LEARN . EMPOWER

University Institute of Engineering (UIE)


Department of Computer Science and Engineering (CSE)

Learning Objectives & Outcomes


Objective:
• To understand the concept Sum-of-subsets, Hamiltonian
cycles

Outcome:
• Student will understand
 Sum-of-subsets
 Hamiltonian cycles

University Institute of Engineering (UIE)


Department of Computer Science and Engineering (CSE)

Subset-Sum Problem

• The Subset-Sum Problem is to find a subset's' of the given


set S = (S1 S2 S3...Sn) where the elements of the set S are n
positive integers in such a manner that s'∈S and sum of
the elements of subset's' is equal to some positive integer
'X.'
• The Subset-Sum Problem can be solved by using the
backtracking approach. In this implicit tree is a binary
tree. The root of the tree is selected in such a way that
represents that no decision is yet taken on any input. We
assume that the elements of the given set are arranged in
increasing order:
S1 ≤ S2 ≤ S3... ≤ Sn

University Institute of Engineering (UIE)


Department of Computer Science and Engineering (CSE)

Subset-Sum Problem (Contd.)


• The left child of the root node indicated that we have to
include 'S1' from the set 'S' and the right child of the root
indicates that we have to execute 'S1'. Each node stores
the total of the partial solution elements. If at any stage
the sum equals to 'X' then the search is successful and
terminates.
• The dead end in the tree appears only when either of the
two inequalities exists:
• The sum of s' is too large i.e. s'+ Si + 1 > X
• The sum of s' is too small i.e.

University Institute of Engineering (UIE)


Department of Computer Science and Engineering (CSE)

Example
• Given a set S = (3, 4, 5, 6) and X =9. Obtain the subset sum using
Backtracking approach.
Solution:
• Initially S = (3, 4, 5, 6) and X =9.
• S'= (∅)
The implicit binary tree for the subset sum problem is shown as fig:

University Institute of Engineering (UIE)


Department of Computer Science and Engineering (CSE)

Hamiltonian Circuit Problems

• Given a graph G = (V, E) we have to find the Hamiltonian Circuit


using Backtracking approach. We start our search from any
arbitrary vertex say 'a.' This vertex 'a' becomes the root of our
implicit tree. The first element of our partial solution is the
first intermediate vertex of the Hamiltonian Cycle that is to be
constructed.
• The next adjacent vertex is selected by alphabetical order. If at
any stage any arbitrary vertex makes a cycle with any vertex
other than vertex 'a' then we say that dead end is reached. In
this case, we backtrack one step, and again the search begins
by selecting another vertex and backtrack the element from
the partial; solution must be removed. The search using
backtracking is successful if a Hamiltonian Cycle is obtained.

University Institute of Engineering (UIE)


Department of Computer Science and Engineering (CSE)

REFERENCES
Text books:
•Cormen, Leiserson, Rivest, Stein, “Introduction to Algorithms”, Prentice Hall of
India, 3rd edition 2012. problem, Graph coloring.

Websites:
•https://www.javatpoint.com/subset-sum-problems
•https://www.javatpoint.com/hamiltonian-circuit-problems

University Institute of Engineering (UIE)


Department of Computer Science and Engineering (CSE)

Summary

Backtracking:

• Sum-of-subsets
• Hamiltonian cycles

University Institute of Engineering (UIE)


THANK YOU

University Institute of Engineering (UIE)

You might also like