COURSE OUTLINE
DATA STRUCTURES AND ALGORITHM
Level: Degree Mode: Day Class Duration: 45 Hours
Lecturer: Stephen Waweru Phone: 0720264448 Email:steve1972bb@[Link]
COURSE DESCRIPTION
This course provides a formal and practical introduction to the algorithms and data structures that
underlie all areas of computation. It aims to provide students with a toolbox of standard algorithms and
data structures, as well as the skills to analyze both the theoretical complexity of algorithms and their
practical behavior. Both written and programming exercises will be used, with examples from all areas
of Informatics. The course introduces design and analysis of algorithms. Design techniques: divide-and-
conquer, greedy method, dynamic programming; selection of prototypical algorithms; choice of data
structures and representations; complexity measures: time, space, upper, lower bounds, asymptotic
complexity; NP-completeness. Algorithms and their performance. Data abstraction, queues, linked lists,
stacks, trees, graphs, and associated algorithms. Sorting and searching.
LEARNING OUTCOMES:
On completion of this course, the student will be able to:
1. Explain both formally and informally the difference between "best", "expected", and "worst" case
behavior of an algorithm, and use asymptotic notation to analyze the time and space complexity of
algorithms. Use recurrence relations to determine the time complexity of recursively defined
algorithms.
2. Describe the properties, typical implementations, and example application use cases of abstract data
types (e.g., stacks, queues, sets, dictionaries, priority queues) and discuss the costs and benefits of
dynamic and static data structure implementations; use the above knowledge to justify the selection
of appropriate data types in a range of settings.
3. Work with a range of data structures to implement basic algorithms given pseudo code or a task
specification; perform empirical studies to compare the performance of different implementations of
the same algorithm or data type on various input (or different algorithms for the same problem) and
explain what can be learned from empirical analysis that cannot be learned from asymptotic analysis
(and vice versa).
4. Describe various algorithmic strategies (e.g., brute-force, greedy, divide-and-conquer, recursive
backtracking, dynamic programming) and give examples of each from a range of application areas
including language processing and information retrieval. Hand-simulate a range of algorithms,
including algorithms for searching, sorting, hashing, solving graph problems, and examples of
dynamic programming. Give example applications that would use each algorithm and choose
appropriate algorithms to use for example problems.
5. Define informally the classes P and NP and give examples of problems in NP. Explain the halting
problem and its significance.
Teaching Methods and Methodologies
Lectures, practical and tutorial sessions in Computer Laboratory, individual and group
assignments, exercises and project work
Instructional Materials/Equipment
Overhead projector and computer, handouts, white boards, textbooks, Network and
internetworking devices
DATA STRUCTURES AND ALGORITHM
Topics Sub-topics Total
Hours
1 Introduction to Data Definition and importance of data structures 6
Structures and Algorithms: and algorithms.
Basic concepts of algorithm analysis: time
complexity (Big O notation), space
complexity.
Introduction to abstract data types (ADTs).
2 Elementary Data Structures Arrays: Static and dynamic arrays, multi- 9
dimensional arrays.
Linked Lists: Singly, doubly, and circular
linked lists; operations (insertion, deletion,
traversal).
Stacks: LIFO principle, array and linked list
implementations, applications (expression
evaluation, recursion).
Queues: FIFO principle, array and linked list
implementations, applications (scheduling,
breadth-first search).
3 Trees Introduction to Trees: Terminology, types of 6
trees.
Binary Trees: Traversal methods (in-order,
pre-order, post-order).
Binary Search Trees (BSTs): Operations
(insertion, deletion, searching), balancing
concepts (e.g., AVL trees, Red-Black trees).
Heaps: Min-heap, max-heap, heapify
operation, applications (priority queues,
heapsort).
CAT 1 [10 marks]
Project [ 10 marks]
4 Graphs Introduction to Graphs: Terminology, 6
representations (adjacency matrix, adjacency
list).
Graph Traversal Algorithms: Breadth-First
Search (BFS), Depth-First Search (DFS).
Shortest Path Algorithms: Dijkstra's
algorithm, Bellman-Ford algorithm.
Minimum Spanning Tree Algorithms: Prim's
algorithm, Kruskal's algorithm.
5 Sorting and Searching Sorting: Bubble sort, selection sort, insertion 6
Algorithms sort, merge sort, quicksort, heapsort.
Searching: Linear search, binary search.
6 Hashing Hash functions, collision resolution 6
techniques (chaining, open addressing).
Hash tables and their applications.
7 Recursion: Recursive definitions and processes. 6
Designing and analysing recursive
algorithms
CAT 2 [10 marks]
TOTAL HOURS 45
Instructional Materials
LCD projectors, computers, white boards, appropriate software (compilers, text processors, spreadsheet
applications, and network simulation software), networking equipment (Switches, routers, and cables for
setting up networking), Laboratory Equipment (electronic circuits, and testing tools)
Course Evaluation
CAT1 CAT2 Assignments TOTAL COURSE WORK EXAM 60% Total Marks
MARKS
10% 10% 10% 30% 70% 100%
Course Textbooks
1. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
Clifford Stein (CLRS): A rigorous and comprehensive reference, often considered a more advanced
text.
2. Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss: A widely recommended
text that balances theory with practical implementation.
3. The Algorithm Design Manual by Steven S. Skiena: Focuses on practical application and problem-
solving.
4. Data Structures and Algorithms Made Easy by Narasimha Karumanchi: A popular book for those
looking to practice with puzzles and problems.
5. Data Structures & Algorithms by Goodrich, Tamassia, and Mount: Another strong option that is
often recommended as a primary or supplementary text