Data Structures and Algorithms ( BICT III sem)

Course Title: Data Structures and Algorithms

Course No. : ICT. Ed. 435                              Nature of course: Theoretical + Practical

Level: B. Ed                                                    Credit Hour: 3 hours (2T+1P)

Semester: Third                                               Teaching Hour: 80 hours (32+48)

                                                                                               

 

1.      Course Description

The purpose of this course is to provide the students with solid foundations in the basic concepts of data structures and algorithms. The main objective of the course is to teach the students how to select and design data structures and algorithms that are appropriate for problems that they might occur. This course is also about showing the correctness of algorithms and studying their computational complexities. This course offers the students a mixture of theoretical knowledge and practical experience. Programming language C will be used for practical work.

2.      General Objectives

The general objectives of this course are as follows:

• To introduce data abstraction and data representation in memory
• To describe, design and use elementary data structures such as stack, queue, linked list, tree and graph
• To decompose complex programming problems into manageable sub-problems
• To introduce algorithms and their complexity

3.   Specific Objectives and Contents

Specific Objectives	Contents
·         Define Data structure and ADT ·         Implement dynamic memory management functions in C ·         Define algorithms, asymptotic notations and mathematical functions	Unit 1: Introduction to Data Structures & Algorithms(6)                                                                    1.1         Data types, Data structure and Abstract date type 1.2         Dynamic memory allocation in C 1.3         Introduction to Algorithms 1.4         Asymptotic notations and common functions Lab: Write  a program to implement dynamic memory management functions(malloc(),calloc(),realloc() and free())
·         Define and implement stack and stack operations ·         Convert expressions in to different forms: infix, prefix and postfix ·         Describe the applications of the stack	Unit 2: Stacks                                                           (8) 2           2.1         Definition 2.2         Stack as an ADT 2.3         Stack operation 2.4         Stack application: Conversion from infix to postfix/prefix expression, Evaluation of postfix/ prefix expressions Lab: Write a program to implement stack operations
·         Define queue and its operations ·         Implement different types of queue ·         Describe the applications of the queue	Unit 3: Queues                                                         (10) 3           3.1         Definition 3.2         Queue as an ADT 3.3         Primitive operations in queue: Enqueue and Dequeue 3.4         Linear Queue, Circular Queue, Priority Queue. Lab: Write a program to implement linear and circular queue operations
·         Define linked list its type and applications ·         Implement linked list operations ·         Implement stack and queue as circular list ·         Describe the applications of the linked list	Unit 4:Lists                                                    (12) 4           4.1         List and ADT 4.2         Array Implementation of Lists 4.3         Linked List 4.4         Types of Linked List: Singly Linked List, Doubly Linked List, Circular Linked List. 4.5         Basic operations in Linked List: creation, node insertion and deletion from beginning, end and specified position 4.6         Stack and Queue as a Linked List Lab-1: Write a program to implement singly and doubly linked list operations Lab-2: Write a program to implement stack and queue as linked list
·         Define recursion. ·         Differentiate between recursion and iteration ·         Implement recursion to solve TOH and Fibonacci series ·         Identify the applications and efficiency of recursion	Unit 5: Recursion                                                       (6) 5           5.1         Principle of recursion 5.2         Comparison between recursion and iteration 5.3         Factorial, Fibonacci sequence,  GCD,  Tower of Hanoi(TOH) 5.4         Applications and Efficiency of recursion Lab-1: Write a program to solve the problem of TOH Lab-2: Write a program to print Fibonacci series Lab-3:Write a program to calculate factorial Lab-4: Write a program to calculate gcd of two numbers
·         Define tree and tree operations ·         Create and manipulate Binary tree, BST, AVL tree and B-Tree ·         Implement Huffman algorithm ·         Identify application areas of tree ·         Describe the applications of the tree	Unit 6: Trees                                                                (10) 6           6.1         Concept and definitions 6.2         Basic operations in binary tree 6.3         Tree height, level and depth 6.4         Binary Search Tree 6.5         Insertion, Deletion, Traversals (pre-order, post-order and in-order ), Search in BST 6.6         AVL tree and Balancing algorithm 6.7         Applications of tree Lab: Write a program to insert, delete, search and display(pre-order, in-order, post-order) items in BST
·         Define sorting and its type ·         Illustrate and implement exchange sort, selection and tree sorting, insertion sort, merge and radix sort. ·         Identify and compare the efficiency of mentioned sorting algorithms	Unit 7: Sorting                                 (12) 7           7.1         Introduction and Types of sorting: Internal and External sort 7.2         Comparison Sorting Algorithms: Bubble, Selection and Insertion Sort 7.3         Divide and Conquer Sorting: Merge, Quick and Heap Sort 7.4         Efficiency of Sorting Algorithms Lab: Write a program to implement:            a) Bubble sort b) Selection sort c) Insertion sort d) Quick sort e) Merge sort f) Heap sort
·         Identify different searching algorithms and implement them. ·         Identify the efficiency of mentioned searching algorithms	Unit 8: Searching                                                     (8) 8           8.1         Introduction to searching 8.2         Search Algorithms: Sequential search, Binary search 8.3         Efficiency of  search algorithms 8.4         Hashing : Hash function and hash tables, Collision resolution technique Lab: Write a program to implement: a)      Sequential search b)      Binary search
·         Define graph, graph terminologies, and graph as a ADT ·         Illustrate transitive closure, Warshall's algorithm and shortest path algorithm ·         Find the shortest path using Dijkstra's Algorithm ·         Explain and implement graph traversal algorithms ·         Define MST and implement prim's, kruskal's and round-robin algorithm ·         Describe the applications of the graph	Unit 9: Graphs                                                        (8) 9           9.1         Definition and Representation 9.2         Graph Traversal: BFS and DFS 9.3         Minimum Spanning Trees: Kruskal and Prims Algorithm 9.4         Shortest Path Algorithms: Dijksrtra Algorithm Lab: Write a program to implement graph traversal algorithms(BFS and DFS)

4.  Instructional Techniques

The instructional techniques for this course are divided into two groups.  First group consists of general instructional techniques applicable to most of the units. The second group consists of specific instructional techniques applicable to particular units.

4.1 General Techniques

Reading materials will be provided to students in each unit. Lecture, Discussion, use of multi-media projector, brain storming, and problem solving methods are used in all units.

4.2 Specific Instructional Techniques

Demonstration is an essential instructional technique for all units in this course during teaching learning process. Specifically, demonstration with practical works will be specific instructional technique in this course. The details of suggested instructional techniques are presented below:

Units	Activities
Unit 1: Introduction to Data Structures & Algorithms	·     Define and Describe the different types of data structures ·     State different operations occurring in data structures ·     Write a program to implement dynamic memory management functions ·     Explain asymptotic notations and complexity on time and space of algorithm ·     Monitor of students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 2: Stacks	·     Illustrate the algorithms of stack operations ·     Lab works in pair to implement stack operations ·     Convert expression in other from one form to another making group and individually ·     Monitoring of students' work by reaching each pair and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 3: Queues	·     Demonstrate queue and queue operations with algorithms ·     Lab work in pairs to implement queue operations ·     Group discussion in advantages and limitations of queues ·     Monitoring of students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 4: List	·     Demonstrate operations of linked list with algorithms ·     Lab work in pairs to implement linked list operations ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 6: Trees	·     Demonstrate operations and types of tree ·     Lab work in pairs to implement BST ·     Trace a working principle of AVL and B-Tree ·     Assign students to create AVL and B-Tree in group ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 7: Sorting	·     Trace the working principle of different sorting algorithms ·     Lab work in pair to implement sorting algorithms ·     Analyze efficiency of sorting algorithms ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 8: Searching and Hashing	·     Demonstrate the working principle of different searching algorithms ·     Lab work in pair to implement searching algorithms ·     Analyze efficiency of searching algorithms ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 9: Graphs	·     Explain the graph and graph terminology ·     Solve the practical problems of shortest path and spanning tree using different algorithms ·     Assign student to solve graph problems ·     Lab work in pair to implement graph traversing algorithms ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback

5.      Evaluation :

Internal Assessment	External Practical Exam/Viva	Semester Examination	Total Marks
40 Points	20 Points	40 Points	100 Points

Note: Students must pass separately in internal assessment, external practical exam and semester examination.

5.1   Internal Evaluation (40 Points):

Internal evaluation will be conducted by subject teacher based on following criteria:

1)      Class Attendance                                                                              5 points

2)      Learning activities and class performance                                                5 points

3)      First assignment ( written assignment)                                         10 points

4)      Second assignment (Case Study/project work with presentation )          10 points

5)      Terminal Examination                                                                               10 Points

Total                                                                                              40  points

5.2        Semester Examination (40 Points) 

Examination Division, Dean office will conduct final examination at the end of semester. 1)      Objective question (Multiple choice 10 questions x 1mark)  10 Points 2)      Subjective answer questions  (6 questions x 5 marks)             30 Points

Total                                                                                                   40  points

5.3  External Practical Exam/Viva (20 Points):

Examination Division, Dean Office will conduct final practical examination at the end of semester.

Recommended Books and References

Recommended Books

1           G. S. Baluja, “Data structure Through C, A Practical Approach", Fourth Ed. Dhanpat Rai & Co., 2009-10.

2           Y Langsam , MJ , Augenstein and A.M , Tanenbaum  Data Structures using C and C++ , Prentice Hall India.

References

3           G.W Rowe, Introduction to Data Structure and Algroithms with C and C++ , prentice Hall  India.

4           T.H Corman, C.E Leiserson, R.L Rivest, C Stein, Introduction to Algorithms, 3^rd Ed, The MIT Press Cambridge, Massachusetts London, England,2010

5           R.L Kruse, B.P. Leung, C.L. Tondo, data structure and program Design in C Prentice-Hall India.

6           G. Brassard and P. Bratley fundamentals of Algroithms, Prentice-Hall India.