KARATINA UNIVERSITY
COMPUTER SCIENCE AND INFORMATICS DEPARTMENT
Course Code: COM 211
Course Title: Data Structures and Algorithms
Lecturer: Peter N. Njuguna
Contact: pnjuguna@[Link]
CONTACT HOURS: 4HRS
1.0 COURSE PURPOSE
The aim of this course is to provide an introduction to fundamental computer program algorithms and data
structures, with an emphasis on foundational material and to provide general set of abstract conceptual tools
for solving problems.
2.0 COURSE LEARNING OUTCOMES
At the end of this course the learner should be able to:
a) Describe algorithms in both functional and procedural styles and apply good principles of
algorithm design,
b) Analyze algorithms and estimate their worst-case and average-case behaviour,
c) Understand the importance of the data structures used in a particular implementation of an
algorithm, and how the data structure that is used can affect the running time,
d) Describe how several fundamental algorithms work, particularly those concerned with sorting,
searching and graph manipulation,
e) Design new algorithms or modify existing ones for new applications and reason about the
efficiency of the result.
3.0 COURSE CONTENT
Fundamental data structures: Stacks; queues; linked lists; hash tables; trees; graphs. Object-oriented design:
encapsulation and information hiding, classes, separation of behavior, class hierarchies, inheritance,
polymorphism. Computing algorithms: O (N log N) sorting algorithms, hash tables, including collision-
avoidance strategies, binary search trees, representations of graphs, depth- and breadth-first traversals.
Recursion: recursive mathematical functions, simple recursive procedures, divide-and-conquer strategies,
recursive backtracking. Introduction to algorithmic analysis.
Page 1 of 3
4.0 TEACHING METHODOLOGY
Lectures, class discussions, group assignments and presentations. Active participation required.
5.0 INSTRUCTIONAL MATERIALS
Instructor designed handouts, Power point Slides, Summary Notes
6.0 COURSE ASSESSMENT
The course will be assessed as follows:
Continuous Assessment Tests 20%
Practical Based Assessment 10%
Final Examination 70%
TOTAL 100%
7.0 COURSE CORE TEXTBOOK
i. Weiss M. A. (1999) Data structures and algorithm analysis in C++, 2nd Ed. Reading MA : Bruno R.
Preiss, (2001): Data Structures and Algorithms with Object-Oriented Design Patterns in C++.
ii. N. Wirth (2004) Algorithms and Data Structures
iii. Alfred V. Aho, and John E. Hopcroft, (2001): Data Structures and Algorithms
Addison Wesley [ISBN 978-0321441461]
7.0 RECOMMENDED BOOKS FOR FURTHER READING
i. Levitin A. V. (2007) Introduction to the design and analysis of algorithms. 2nd Ed, Reading M.A : Addison
Wesley [ISBN 978-0321358288]
Course Outline
WEEK TOPIC SUB TOPIC
1 Introduction to - Course description
Algorithms and Data - Introduction to Algorithm.
Structures - Introduction to Data Structures
- Basic Data types
- Strucured Data Type
2 Introduction to - Data Abstraction
Abstract Data Type - Functional Abstraction
(ADT) - Data Hiding Concepts in ADT & OOAD
- Encapsulation, Polymorphism
-
3 Recursive - Introduction to Iteration Algorithm Controls and Recursive
Algorithms - Multiplying numbers
- Find Factorial value
- Fibonacci numbers
4 Simple Sort - Introduction to Simple Sort Algorithms
Algorithms - Bubble Sort Algorithm
- Selection Sort Algorithm
- Insertion Sort Algorithm
Page 2 of 3
5 Advanced Sort - Merge Sort Algorithm
Algorithms - Quick Sort Algorithm
6 Search Algorithms - Sequential Search
- Binary Search
- Sit in CAT 1
7 Introduction to - Best Case
Algorithm Analysis - Average Case
- Worst Case
- Asymptotic Notation
- Big O, Big Theta, Big Omega Notations
8 Linear Data - Array
Structures - Linked List
- Queue
- Stack
9 - Queue
- Stack
10 Non Linear Data - Introduction to Tree
Structures - Tree Traversal
11 - Introduction to Binary Search Tree
- Binary Search Tree Algorithms
- CAT 2
12 - Introduction to Graph
- Graph Traversal
13 - Other Graph Algorithms
- Assignment Presentation
14 - Revision
15 - EXAM
16 - EXAM
H.O.D:_____________________________ Sign:_____________ Date:____________________
Classrep Name:_____________________ Sign:_____________ Date:____________________
Lecturer Name:_____________________Sign:_____________ Date:____________________
Page 3 of 3