Data Structure and Algorithms Syllabus - BCIS (PU)

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.

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

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