Oladapo Kayode Abiodun

Course Title: Algorithm And Complexity Analysis

Course Code: CMP 411

Introduction

This is a three-credit unit course offered by the 400-level students of the degree programme in Cybersecurity, Information Technology, Software Engineering and Computer Science. An algorithm is a step-by-step process of solving a problem while the complexity of an algorithm is the cost, measure in running time, storage or whatever relevant units of using the algorithm in solving one of those problems. The overall aim of CMP 411 is about the methods for solving problems on computers and the costs (running time, storage) of using those methods. In this course content you will find useful details about this course, its aims and objectives, what the course is all about, course materials to be used, available services in support of this course, and details on assignments and examinations. I strongly recommend you check regularly for updates. I wish you all the best in your learning and the successful completion of this course.

Course Aim

This course aims to introduce the students to how to design and test algorithms and also help them identify various types of algorithm design paradigms.

Course Outline

• Bits, Bytes, Word
• Linear and Non-Linear Structures
• Arrays, Tree Structure
• Sets and Relations
• Basic algorithmic analysis
• Asymptotic analysis of Upper and average complexity bounds;
• standard Complexity Classes Time and space trade-offs in algorithms analysis recursive algorithms.
• Algorithmic Strategies
• Fundamental computing algorithms
• Numerical algorithms
• sequential and binary search algorithms
• sorting algorithms
• Binary Search tress
• Hash tables
• graphs & its representation.

Course Objectives

After completing the course successfully, the student should be able to:

1. Explain the basic concepts of bits, bytes and word
2. Understand linear and non-linear structures
3. Describe arrays and tree structure
4. Discuss sets and relations
5. Describe the basic algorithmic analysis
6. Explain the asymptotic analysis of upper and average complexity bounds
7. Distinction in standard complexity classes time and space trade-offs in algorithm analysis
8. Explain algorithmic strategies
9. Describe the fundamental computing algorithms
10. Describe the numerical, sequential and binary search algorithms
11. Explain hash tables
12. Understand the graph and its representation
13. Discuss the application of this course in real-life
14. Conduct and carry out a research paper concerning the course.

Assessment

• Class Attendance, Participation and Discussion: 5 marks
• Course Research Paper: 20 marks
• Mid-Semester: 5 marks
• Final: 70 marks

Information about the instructor

• Instructor: Kayode Oladapo
• Education: Ph. D. in Computer Science
• Email: oladapoka@mcu.edu.ng

Main Course

• Week 1: Introductory Class
• Week 2: Bits, Bytes, Word, Linear and Non-Linear Structures
• Week 3 - 4: Arrays, Tree Structure, Sets and Relations
• Week 5: Basic algorithmic analysis, Asymptotic analysis of Upper and average complexity bounds
• Week 6 - 7: Standard Complexity Classes, Time and space trade-offs in algorithms analysis, recursive algorithms, and Algorithmic Strategies
• Week 8: Course Research Paper / Mid Semester Test
• Week 9- 10: Fundamental computing algorithms, Numerical algorithms
• Week 11 – 12: Sequential and binary search algorithms, sorting algorithms
• Week 13 – 14: Binary Search trees, Hash tables
• Week 15 - 16: Graphs & its representation.
• Week 17: Revision
• Week 18 - 19: Examination

Week 1: Introductory Class

• Meeting each of the students Discuss
• What is an Algorithm?
• Characteristics of an Algorithm
• Advantages of Algorithms
• Disadvantages of Algorithms
• Pseudocode
• Advantages of Pseudocode
• Disadvantages of Pseudocode
• Differences between Algorithm and Pseudocode
• Need of Algorithms

Simple Introductory Task

• Create an algorithm that multiplies two numbers and displays the output.

Week 2: Bits, Bytes, Word, Linear and Non-Linear Structures

• Bits, Bytes, Word
• Linear and Non-Linear Lecture Slide
• Exercise: You have just been nominated as a Programmer of a Software firm responsible for developing software for tertiary institutions. How would your knowledge of this course facilitate your task?
• Research Paper Task Distribution Research Paper Task.pdf

Week 3 - 4: Arrays, Tree Structure, Sets and Relations

• Arrays, Tree Structure, Sets and Relations Lecture Slide
• Arrays
  • Classification of Arrays
  • Application of Arrays

Week 5: Basic algorithmic analysis, Asymptotic analysis of Upper and average complexity bounds

• Analysis of Algorithm
  • Space Complexity
  • Time Complexity
    • Types of Time Complexity Analysis
• Complexity of Algorithm
• Week 5 Lecture Slides
• Python Task - Submission Date: 9th December
  • Discussion Group Task.pdf
• Dataset for Task
  • punch-data.txt
  • titanic.csv
  • ex1-data.txt
  • wind-data.csv

Week 6: Standard Complexity Classes, Time and space trade-offs in algorithms analysis, recursive algorithms, and Algorithmic Strategies

• Standard Complexity Classes
• Time and space trade-offs in algorithms analysis
• Recursive algorithms, and
• Algorithmic Strategies
• Week 6 Lecture Slides