ASSOSA UNIVERSITY
COLLEGE OF COMPUTING AND INFORMATICS
Department: Computer Science
Course Tile: Data structures and Algorithms
Instructor Name: Melkamu A.
Email:malmawu@gmail.com
Course Description:
This course focuses on the study of data structures, algorithms and program efficiency. Topics
include: analysis of time and space requirements of algorithms; program efficiency improving
techniques, abstract data types such as linked lists, stacks, queues, trees (traversal,
implementations); simple searching algorithms (linear search, binary search, … ), simple
sorting algorithms (bubble sort, insertion sort, selection sort, … ), advanced sorting algorithms
(merge sort, quick sort, heap sort … ).
Course Goals or Learning Outcome:
The course aims:
• To introduce the most common data structures like stack, queue, linked list
• To give alternate methods of data organization and representation
• To enable students use the concepts related to Data Structures and Algorithms to solve
real world problems
• To practice Recursion, Sorting, and searching on the different data structures
• To implement the data structures with a chosen programming language
Prerequisites:
Fundamentals of Programming II
Chapter 1 - Introduction to Data Chapter 2 - Simple Sorting and Searching
Structures, Algorithm and Algorithm Algorithms
Analysis
✓ Searching
✓ Introduction • Linear/Sequential Searching
✓ Abstract Data Type and Abstraction • Binary Searching
✓ Properties of Algorithm ✓ Sorting
✓ Analysis of Algorithm • Selection Sort
• Bubble Sort
• Insertion Sort
• Pointer Sort
Chapter 3 - Linked Lists
✓ Review on Pointer, Dynamic Memory Chapter 7- Advanced Sorting and
allocation and De-allocation Searching
✓ Single Linked Lists
✓ Double Linked Lists ✓ Sorting
✓ Implementation of Linked Lists • Heap Sort
Chapter 4: Stacks • Quick Sort
• Merge Sort
✓ Properties of Stack • Shell Sort
✓ Array Implementation of Stack
✓ Linked List Implementation of Stack ✓ Advanced Searching
✓ Application of Stack ✓ Hashing
o Evaluation of Algebraic Expression
o Infix and Post fix (RPN) conversion Chapter 8- Graphs
o Function calls
✓ Introduction
Chapter 5: Queue ✓ Describing graphs
✓ Directed Graphs
✓ Properties of Queue
✓ traversing a graph
✓ Array Implementation of Queue
✓ Linked List Implementation of
Queue
✓ Double Ended Queue (Deque)
✓ Priority Queue
✓ Application of Queues
Chapter 6- Tree Structures
✓ Binary Trees and Binary Search
Trees
✓ Basic Tree Operations
✓ Traversing in a Binary Tree
✓ General Trees and Their
Implementations.
Teaching materials Reference books:
Robert Lafore, “Data Structures and Algorithms in JAVA, 2nd Ed.”, Sam’s Publishing
Jean Paul Tremblay, Paul G. Soreson, “An Introduction to Data Structures with Applications”,
Mc. Graw Hill Computer Science Series
E. Horowitz, S.Sahni and Dinesh Mehta. Fundamentals of data structures in C++, W.H Freeman
and Company (1995)
Sanjay Pahuja, A practical approach to data structures and algorithms, new age international
publishers, 2008
