ALGORITHM DESIGN &
ANALYSIS
B ATCH - 14 :
G.P hanindra - 231FA 19027
K .Chaitanya - 231FA 19046
S k.A adil - 231FA 19069
P.S neha - 231FA 19083
G UIDE : Dr. Siv adi Balak r is hna
QUESTI ON
A uni ve rs i ty needs to s c h e d u l e f i n a l e x a ms f o r mu l t i p l e c o u r s e s wh i l e
e ns urin g no s t udent has t wo e x a ms a t t h e s a me t i me a n d r o o ms a r e n o t
o v erbook ed .
a . Det ermi ne wh ethe r th e e x a m s c h e d u l i n g p r o b l e m f a l l s i n t o P, NP, o r NP -
c omp let e c la ss and jus t if y y o u r a n s we r.
b . How c an a ba ck t rac k in g a p p r o a c h h e l p i n s o l v i n g t h i s p r o b l e m? Wo u l d
i t b e effi c ient ?
c . I f a g re edy al gorit hm is u s e d i n s t e a d o f b a c k t r a c k i n g , wh a t wo u l d b e i t s
a dv ant ages and limit ati on s ?
I N TRODUCTI ON
P ( P o l y n o m i a l Ti m e ) :
• P stands for "polynomial time" and refers to the class of decision
problems that can be solved by a deterministic algorithm in
polynomial time.
NP (Nondeterministic Polynomial Time):
• NP problems are decision problems (problems with a yes/no answer)
whose solutions can be verified in polynomial time (meaning the time
it takes to check the solution grows polynomially with the size of the
input).
NP-Complete:
• An NP-complete problem is a problem that is both in NP and has the
property that any other problem in NP can be reduced to it in
polynomial time.
a ) C l a s s i fi c a t i o n o f t h e E x a m S c h e d u l i n g P r o b l e m
• C l a s s : N P- c o m p l e t e
• J u s t i fi c a t i o n :
⚬ The exam scheduling problem can be framed as a graph coloring
problem, where courses are represented as vertices and edges
represent conflicts (i.e., students enrolled in both courses).
⚬ Determining if a valid schedule exists (i.e., coloring the graph with
a limited number of colors corresponding to available time slots) is
NP-complete.
⚬ It is in NP because, given a proposed schedule, we can verify in
polynomial time whether it meets the constraints (no overlapping
exams for students and room availability).
b. Backtracking Approach
⚬ How it Helps:
￭ Backtracking systematically explores all possible schedules by assigning time slots to
exams and checking for conflicts.
￭ If a conflict arises, it backtracks to the previous step and tries a different assignment.
￭ This method ensures that all possible configurations are considered, leading to a valid
schedule if one exists.
• Efficiency:
⚬ Backtracking can be inefficient for large instances due to its exponential time complexity in
the worst case.
⚬ However, it can be optimized with techniques like constraint propagation and pruning to
reduce the search space.
c. Greedy Algorithm: Advantages and Limitations
Advantages:
• Simplicity: Greedy algorithms are generally easier to implement and understand.
• Speed: They can provide quick solutions, often in polynomial time, making them suitable for
large datasets.
• Good for Certain Cases: They may yield optimal or near-optimal solutions for specific instances
or constraints.
Limitations:
• Suboptimal Solutions: Greedy algorithms do not guarantee an optimal solution for all cases,
especially in complex scheduling scenarios.
• Lack of Flexibility: Once a decision is made, it cannot be changed, which may lead to conflicts
later in the schedule.
• No Backtracking: They do not explore alternative configurations, which can result in missed
valid schedules.
U SI NG BACKT RACK I NG AL G OR I T H M
OU TPUT
U SI NG GREEDY ALGORITHM
OU TPUT
THANK
YOU