MIDLANDS STATE UNIVERSITY
FACULTY OF BUSINESS SCIENCES
DEPARTMENT OF INFORMATION AND MARKETING SCIENCES
MODULE NAME AND CODE: DATA STRUCTURES AND ALGORITHMS - DSI136
MODULE OBJECTIVE: This module covers the analysis and design of fundamental data
structures and engages learners to use data structures as tools to algorithmically design efficient
computer programs that will cope with the complexity of actual applications. Python is used for
demonstration of concepts.
LEARNING OUTCOMES
Read and write algorithms in pseudocode
Implement and use abstract data structures
Use known algorithms to solve programming problems
Appreciate the impact on memory usage and computation speed to make informed
decisions about the most appropriate data structures and algorithms to use when
designing software
Demonstrate an understanding of trade-offs when making design decision about data
structures and algorithms
TOPICS AND SUB-TOPICS
1. Introduction
Overview of data structures
Characteristics of data structures
Data structures, abstract data types, design patterns, manipulation, and operations
Types of data structures – linear and nonlinear
Overview of algorithms
Characteristics of algorithms
Algorithm design and analysis process
Asymptotic notations and Analysis of algorithms
Time and Space complexity
Writing an algorithm, Pseudocode, and designing a flowchart
Basic terminology
2. Arrays and Linked Lists
Arrays: Dynamic memory allocation, one-dimensional arrays, multidimensional
arrays, operations on arrays, storage – Row major order, Column major order.
Linked lists: types of linked lists – singly, doubly, and circularly linked lists,
operations on linked lists.
3. Stacks, Queues, and Tries
Stacks: Implementation of stacks– array and linked list, operations on stacks,
Applications of Stacks, Notations – infix, prefix and postfix, Conversion and
evaluation of arithmetic expressions using Stacks.
Queues: Implementation of queues– array and linked list, operations on queues,
Types of queues – queue, double-ended queue, and priority queue.
Tries: Implementation and operations
4. Trees and Graphs
Trees: Binary tree, Binary search tree, threaded binary tree, Height balanced trees,
Tries, Heaps, Hash tables
Graph traversals: Breadth-First Search, Depth First Search,
Shortest path: Depth-first search in directed and undirected graphs.
Union-find data structure and applications
Directed acyclic graphs
Topological sort
5. Searching Techniques
Linear search
Binary search
Interpolation search
Hash Tables and Functions
Hash Tables and Hash Functions
6. Sorting techniques:
Sorting algorithms
Bubble sort,
Selection sort,
Insertion sort,
Quick sort,
Merge sort,
Radix sort
Shell sort
7. Recursion Basics
Properties
Implementation
Analysis of recursion
ASSESSMENT CRITERIA
Assessment: CA: (At Least 2 Assignments + 1 Test): 40% of FEM + Written Exam: 60% of
FEM
RECOMMENDED STUDY MATERIAL
LIST OF REFERENCE BOOKS:
1. Y Daniel Liang, “Introduction to Programming using Python”, Pearson.
2. Benjamin Baka, David Julian, “Python Data Structures and Algorithms”, Packt
Publishers,2017.
3. Rance D. Necaise, “Data Structures and Algorithms using Python”, Wiley Student
Edition.
4. Martin Jones, “Python for Complete Beginners”, 2015.
5. Zed A. Shaw, “Learn Python the Hard Way: a very simple introduction to the
terrifyingly beautiful world of computers and code”, 3e, Addison-Wesley, 2014.
6. Hemant Jain, “Problem Solving in Data Structures and Algorithms using Python:
programming interview guide”, 2016.
WEB REFERENCES:
1. https://docs.python.org/3/tutorial/datastructures.html
2. http://interactivepython.org/runestone/static/pythonds/index.html
3. http://www.tutorialspoint.com/data_structures_algorithms
4. http://www.geeksforgeeks.org/data-structures/
5. http://www.studytonight.com/data-structures/
6. http://www.coursera.org/specializations/data-structures-algorithms
