Test-3 Internals Theory Syllabus

UNIT - 5

DECREASE-AND-CONQUER APPROACHES, SPACE-TIME

TRADEOFFS:

Decrease-and-Conquer Approaches:

Introduction,

Insertion Sort,

Depth First Search and Breadth First Search,

Topological Sorting

Space-Time Tradeoffs: 

Introduction

Enhancement in String Matching(Horspools String matching).

UNIT – 6

LIMITATIONS OF ALGORITHMIC POWER AND COPING WITH

THEM:

Decision Trees, P, NP, and NP-Complete Problems

UNIT - 7

COPING WITH LIMITATIONS OF ALGORITHMIC POWER:

Backtracking: n - Queens problem

Subset –Sum Problem.

Approximation algorithms for Traveling Salesman Problem(TSP):

i.      Nearest-Neighbor algorithm

ii.    Twice-around-the –tree algorithm