INTRODUCTION TO ALGORITHMS BCS755B

INTRODUCTION: What is an Algorithm?, Fundamentals of Algorithmic Problem Solving, Important problem Types, Fundamental Data Structures, Analysis Framework, Asymptotic Notations and Basic Efficiency Classes, ,Analysis Framework, Asymptotic Notations and Basic Efficiency Classes,

Chapter 1 (Sections 1.1 to 1.4), Chapter 2 (2.1, 2.2)

FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM EFFICIENCY: Mathematical Analysis of Non-recursive Algorithms, Mathematical Analysis of Recursive Algorithms.

BRUTE FORCE APPROACHES: Selection Sort and Bubble Sort, Sequential Search and Brute Force String Matching.

Chapter 2(Sections 2.3,2.4), Chapter 3(Section 3.1,3.2)

Exhaustive Search (Travelling Salesman problem and Knapsack Problem).

Depth First search and Breadth First search.

DECREASE-AND-CONQUER: Insertion Sort, Topological Sorting.

DIVIDE AND CONQUER: Merge Sort, Binary Tree Traversals.

Chapter 3(3.4,3.5), Chapter 4 (Sections 4.1,4.2), Chapter 5 (Section 5.1,5.3)

TRANSFORM-AND-CONQUER: Balanced Search Trees (AVL Trees), Heaps and Heapsort.

SPACE-TIME TRADEOFFS: Sorting by Counting: Comparison counting sort, Input Enhancement in String Matching: Horspool’s Algorithm, Hashing.

Chapter 6 (Sections 6.3,6.4), Chapter 7 (Sections 7.1,7.2, 7.3)

DYNAMIC PROGRAMMING: Three basic examples, The Knapsack Problem and Memory Functions.

THE GREEDY METHOD: Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman Trees and Codes.

Chapter 8 (Sections 8.1,8.2), Chapter 9 (Sections 9.2,9.3,9.4)