Data structures and algorithm

Mount Kenya University


P.O. Box 342-01000 Thika

Email:

Web: www.mku.ac.ke




DEPARTMENT OF INFORMATION
TECHNOLOGY

COURSE CODE: BIT22203
COURSE TITLE: DATA STRUCTURES AND
ALGORITHMS

,Contents
CHAPTER ONE ............................................................................................................................................... 5
DATA STRUCTURES ................................................................................................................................... 5
What is Linked List? .............................................................................................................................. 25
1.4.1 Pros and Cons of Linked Lists...................................................................................................... 26
1.4.2 What is the good and bad thing about linked list? ....................................................................... 27
1.4.3 Types of linked lists ....................................................................................................................... 27
Linearly linked lists........................................................................................................................... 27
Circularly linked lists ....................................................................................................................... 27
Singly Linked Lists ........................................................................................................................... 27
Doubly linked lists............................................................................................................................. 27
Multiply-linked Lists ........................................................................................................................ 27
Binary Trees ........................................................................................................................................ 34
1.5.4 Traversal methods ....................................................................................................................... 37
CHAPTER TWO ............................................................................................................................................ 41
INFIX AND POSTFIX EXPRESSION (REVERSE POLISH NOTATION) ............................................................ 41
CHAPTER THREE .......................................................................................................................................... 47
CHAPTER FOUR ........................................................................................................................................... 54
SEARCH AND SORT ALGORITHMS ........................................................................................................... 54
SAMPLE EXAMS QUESTIONS ....................................................................................................................... 68

, COURSE OUTLINE

BIT22203 DATA STRUCTURES AND ALGORITHMS




Purpose of the course : To present fundamental methodology and concepts of writing and applying
algorithms to various data structures.

WEEK ONE & TWO

1. Data Structures and their applications
 One-dimensional array data structures
 Two-dimensional data structures
 Stack data structure
 Queue data structure
 Linked list data structure
 Tree data structure
 Graph data structure

WEEK THREE & FOUR
2. Operations on data structures
 Operations on Stack data structure
 Operations on Queue data structures
 Operations on Linked list data structure
 Operations on tree data structures

WEEK FIVE, SIX & SEVEN
3. Algorithms
 Algorithms for manipulating array data structures
 Algorithms for manipulating stack data structures
 Algorithms for manipulating queue data structures
 Algorithms for manipulating linked list
 Algorithm for manipulating trees
 Algorithms for manipulating postfix and infix expressions

WEEK EIGHT
4. Recursive functions
 Factorial functions
 Power functions
 Fibonacci functions

WEEK NINE
5. Postfix and infix expressions

WEEK TEN
6 .Traversal of the tree
 Pre-order traversal
 In-order traversal
 Post-order traversal

, WEEK ELEVEN
7. Search
 Linear search
 Binary search

WEEK TWELVE, THIRTEEN & FOURTEEN
8. Sorting
 Bubble sort algorithm
 Selection sort algorithm
 Insertion sort algorithm
 Quick sort algorithm

Assessments

 Continuous Assessment Tests (CATs) (30%)
 End of semester examination (70%)
Total = 100%




Required text books

Salamis S, Data structures, Algorithms and application in Java, McGraw Hill

Banachowski I et al, Analysis of algorithms and Data structures, Addison wiley

Text books for further reading

MKlaus W., Algorithms, data structures, programmes, New Delhi, MCGraw Hill




Compiled by : Joshua Agola