Data Structure and Algorithms Syllabus - BCIS (PU)
View and download full syllabus of Data Structure and Algorithms
Course Description
Course Objectives
This course aim to provide fundamentals knowledge on data structure designing and implementing for storing information, and various algorithms used in computer sciences with an aim to give a feel for algorithms and data structure. They will be able to use and design linked data structures, appreciate how the inheritance mechanism of object-oriented languages enable the, to write generalized code expressing an algorithm or data structure in a way that may be used in a variety of real-world situation.
Course Description
This course focuses on an arrangement of data in a computer’s memory or even disk storage. It incorporate example of several common data structure including arrays, Linked lists, queues, stacks, binary trees, and hash tables. The course also includes algorithms, on the other hand, that are used to manipulate the data contained in these data structure as in searching and sorting. Many algorithms apply directly to a specific data structures. When working with certain data structure student need to know how to insert new data, search for a specified item, and deleting a specific item. Commonly used algorithms include in the course are useful for:
- Searching for a particular data item (or record)
- Simple sorting and advance sorting
- Iterating through all the item in a data structure
Course Outcomes
On successful completion of this module, a student will
- Have a good working knowledge of the development framework and be able to use its various feature, including UI, resource, storage, security, multimedia, location, etc;
- End it appreciating that understanding the algorithm and data structure used for some problem is much importance than knowing the exact code for it in some programming language; and
- Be able to understand the developed application and use this knowledge in developing system.
Unit Contents
Course Contents
Unit 1: Introduction 3 hours
What is the subject about? Mathematics review, Brief introduction to Recursion
Unit 2: Algorithm Analysis 3 hours
Mathematical background, Model, What to analyze? Running time calculations
Unit 3: Lists, Stacks, and Queues 5 hours
Abstract data types (ADTs), The list ADT, The stack ADT, The queue ADT
Unit 4: Trees 6 hours
Reliminaries, Binary trees, The search tree ADT – Binary search trees, AVL trees, Splay trees, Tree traversals (revisited), B-trees
Unit 5: Hashing 6 hours
General idea, Hash function, Open hashing (separate chaining), Closed hashing (open addressing), Rehashing, Extendable hashing
Unit 6: Priority Queues 6 hours
Model, Simple implementation, Binary heap, Applications of priority queues, D-heaps, Leftist heaps, Skew heaps, Binomial queues
Unit 7: Sorting 7 hours
Preliminaries, Insertation sort, A lower bound for simple sorting algorithms, Shell-sort, Heap-sort, Merge- sort, Quick-sort, Sorting large objects, A general lower bound for sorting, Bucket sort, External sorting
Unit 8: Graph Algorithm 6 hours
Definitions, Topological sort, Shortest-path algorithm, Network flow problems, Minimum spanning tree Applications of depth-first search, Introduction to NP-completensess
Unit 9 : Algorithm Design Techniques 6 hours
Greedy algorithm, Divide and conquer, Dynamic programming, Randomized algorithms, Backtracking algorithms
Laboratory
There shall be 10 lab exercises based on C or JAVA
- Implementation of stack
- Implementation of linear and circular queue
- Solution of TOH and Finbonacci recursion
- Implementation of Link list: Singly, and doubly linked
- Implementation of Tree: AVL tree, Balancing of AVL
- Implementation of merge sort
- Implementation of search: sequential, Tree and Binary
- Implementation of Graphs: Graph traversals
- Implementation of hashing
- Implementation of heap
Text and Reference Books
Basic Text
- Langsam, Y., Augustin, M.J. and Tanenbaum, A. M.: Data Structure Using C and C++, Prentice Hall of India
- Rowe, G. W.: Introduction to Data Structure and Algorithms with C and C++, Prentice Hall of India
- Mark, Allen, Weiss: Data Structure and Algorithm Analysis in C++
Recommended:
- Any C++ book
- Short Name DSA
- Course code CMP 367
- Semester Sixth Semester
- Full Marks 100
- Pass Marks 45
- Credit 3 hrs
- Elective/Compulsary Compulsary