DS (BSC-IT 2nd)

Section I

Analysis of Algorithms : Why Analyze Algorithms?; What is Analysis?; What Analysis

doesn’t

do?; What to count and consider?; Cases to Consider during Analysis; Rates of Growth;

Analysis

of Sequential Search Algorithm (Worst Case Analysis, Average Case Analysis).

Arrays : What are Arrays?; Array Operations; Merging of Two Arrays; TwoDimensional

Arrays

(Row Major and Column Major Arrangement, Common Matrix Operations, More Matrix

Operations); Array of Pointers; Multidimensional Arrays; Arrays and Polynomials;

Multiplication of

Polynomials.

Strings : What are Strings?; Representation of Strings; Operations on Strings; Pointers

and

Strings; A Two-Dimensional Array of Strings; Array of Pointers to Strings; Limitation of

Array of

Pointers to Strings; Pattern Matching (Brute Force Algorithm); Few More String

Functions.

Section II

Linked Lists : What is a Linked List?; Operations on Linked Lists; Ascending Order

Linked Lists;

Reversing the Links; Merging of Linked Lists; Sorting a Linked List; Circular Linked

List (Function

delcirq(), Function cirq_display()); A few more Operations; Recursive Operation on

Linked Lists;

Doubly Linked Lists (Function d_append(), Function d_addatbeg(), function

d_addafter(), function

d_delete()); Linked Lists and Polynomials (Function poly_multiply(), Function padd()).

Sparse Matrices : Representation of Sparse Matrix as an Array; Common Matrix

Operations;

Transpose of a Sparse Matrix; Addition of Two Sparse Matrices; Multiplication of Two

Sparse

Matrices; Linked Representation of a Sparse Matrix; Other forms of a Sparse Matrix.

Stacks : Operations on Stack; Stack as an Array; Stack as a Linked List; Applications of

Stacks;

 PTU/BOS/BSIT/111/09-05-2006/batch-2005

18

Infix to Prefix Conversion; Infix to Post-fix conversion; Postfix to prefix conversion;

postfix to infix

conversion; Evaluation of Postfix expression.

Queues : Representation of Queue as an Array; Representation of a Queue as a Linked

List;

Circular Queues; Dequeue; Priority Queue; Array Implementation of a Priority Queue.

Section III

Trees : Binary Trees; Traversal of a Binary Tree; Representation of a Binary Trees in

Memory

(Linked Representation of Binary Trees, Array Representation of Binary Trees, Binary

Search

Trees); Operations on a Binary Search Tree (Searching of a Node in a BST, Insertion of a

Node

in a BST, Deletion from a Binary Tree, Applications of Binary Trees (Representing

Expressions In

Binary Trees).

Searching and Sorting : Searching (Linear Search, Binary Search, Comparison of

Linear

Search and Binary Search); Sorting (Internal Sorting, External Sorting); Internal Sorting

(Bubble

Sort, Selection Sort, Quick Sort, Insertion Sort); External Sorting.