BCA Syllabus – Fundamentals of Data Structures & Computer Algorithms

3.1 Fundamentals of Data Structures & Computer Algorithms

Second Year          Part III Group A              Third Semester                Subject Code:   

Unit -1

Divide and Conquer : The general method – Binary Search – finding the maximum and minimum – Mergesort – Quicksort – Selection – Strassen’s matrix – Multiplication. Greedy Method: The general method – Optimal storage on tapes – Knapsack Problem – Job sequencing with deadlines – Optimal merge patterns – minimum spanning tree – Single source shortest paths.

Unit – 2

Dynamic Programming : The general method – Multistage graphs – all pairs shortest paths – Optimal binary search trees – 0/1 Knapsack Reliability design the traveling salesman problem –Flow  shop scheduling.

Unit - 3

Introduction: Running time calculations – A Simple Example – General Rule – Solutions for the Maximum subsequence Sum problem – Logarithms in the Running time – Checking your Analysis – A grain of salt.

Unit - 4

LISTS, STACKS, and QUEUES: The List ADT: Simple Array Implementation of Lists Programming Details – Common Errors – Doubly Linked Lists – Circularly Linked Lists – Examples – Cursor Implementation of Linked Lists. The Stack ADT: Stack Model – Implementation of Stacks – Applications. The Queue ADT: Queue Model – Array Implementations of Queues – Applications of Queues.

Unit - 5

Trees :  Basic Terminology  - Binary Trees – Representations – Binary Tree Traversal – More on Binary Trees – Threaded Binary trees – Binary Tree Representation of Trees – Application of Trees – Counting Binary Trees.

TEXT BOOKS:

1)      Fundamentals of data structure – Ellis Horowitz, Sartaj Sahni, Galgottia

      Publications 1998

2)      Fundamentals of Computer algorithms - Ellis Horowitz, Sartaj Sahni,

      Galgottia Publications Pvt. Ltd. New Delhi.

3)      Data Structures and Algorithm Analysis in C - MARK ALLEN WEISS –

      Second edition – Addison Wesley Publishing Company 1997

      Chapters - 2.4, 3