Unit 1

Basic concepts of data structures and abstract data types; Basic analysis of algorithms: notions of time and space complexities, asymptotic analysis and notations, efficiency of algorithms. Review of recursion techniques. [2 weeks]

Unit 2

Stacks, LIFO; Linked Lists, Queues, and basic operations associated with these structures, algorithms, and applications. [3 weeks]

Unit 3

Sorting and searching algorithms: Bubble sort, insertion sort; Divide and conquer strategy; merge sort, quick sort. Linear search, binary search, breadth first and depth first search algorithms, pattern matching algorithms. Other problem-solving strategies: Greedy Method – Fractional knapsack problem, scheduling problem. [3 weeks]

Unit 4

Tree: definition and properties, basic tree traversals, Binary Tree, data structure for representing trees, Binary Search Tree, array-based implementation. [2 weeks]

Unit 5

Graphs: data structure for graphs, graph traversals, directed acyclic graphs, weighted graphs, shortest paths, minimum spanning trees. [3 weeks]

A term project may be given during the last third of the semester on an implementation of some data structure and a simple application carried out in groups of two to four students.

1. develop knowledge of basic data structures for storage and retrieval of ordered or unordered data.
2. develop a knowledge of applications of data structures including the ability to implement algorithms for the creation, insertion, deletion, searching, and sorting of each data structure.
3. Analyse and compare algorithms for efficiency using asymptotic notations.
4. Program examples requiring the implementation of the above data structures.

Evaluation Pattern: As in the rules for Assessment Procedure (R.14)

Textbook:
Goodrich M T, Tamassia R and Michael H. Goldwasser, “Data Structures and Algorithms in Python”, Wiley publication, 2016.

References:
Clifford A. Shaffer, “Data Structures and Algorithm Analysis”, Third Edition, Dover Publications, 2012.
Tremblay J P and Sorenson P G, “An Introduction to Data Structures with Applications”, Second Edition, Tata McGraw-Hill, 2002.
Skills and Employability: Entire course contents with tutorials and assignments help build foundations and develops computational thinking, programming skills – design and implementation of software for scientific, engineering and industrial computing applications in universities, industries and research labs/organizations.