To operate the Blended Learning Center(BLC) at optimal level, maintenance will be performed every day at 8:30 AM and at 5:00 PM regularly which can take up to 30 minutes. Please consider scheduling your activity in the BLC platform accordingly.
Topic outline
- Welcome Note
Welcome Note
Assalamu 'Alaikum.
I am Md. Mushfiqur Azam, welcoming you to Algorithms Course.
I hope we will learn together to enrich ourselves and together we can make this journey memorable.
May the Almighty grant you peace and happiness always.
Course Objective
This course introduces students to the analysis and design of computer algorithms. Upon completion of this course, students will be able to do the following:
• Analyse the asymptotic performance of algorithms.
• Demonstrate familiarity with major algorithms and data structures.
• Apply important algorithmic design paradigms and methods of analysis.
• Synthesize efficient algorithms in common engineering design situations.
|
Course Outcomes
(CO’s)
CO1
|
Analyze and calculate time complexity and space complexity of various algorithms or any written code using mathematical formula and comparison of algorithms.
|
CO2
|
Generate and
interpret the output of iterative and recursive codes with the analysis of the problem definition.
|
CO3
|
Identify which algorithm listed under which algorithmic paradigm. Compare among various algorithms/implemented codes and choose the efficient one.
|
CO4
|
Break down and describe the simulation of various algorithms for different input values.
|
CO5
|
Design and apply appropriate algorithms to solve
real-life problems.
|
Grading Scheme
Theory Class
|
Lab Class
|
Attendance: 7% Class Tests/Quizzes: 15% Assignment: 5% Presentation (using video/ppt): 8% Midterm Exam: 25% Final Exam: 40% |
Lab Attendance: 10% Lab Performance Test: 25% Assignment + Viva: 10% Project: 25% Lab Final: 30%
|
Text Book:
a. Introduction to Algorithms , (3rd Edition, MIT Press, 2009) ISBN: 9780262033848. Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Reference Books :
a. Algorithms (4th Edition)
Author: Robert Sedgewick and Kevin Wayne
b. Algorithm Design
Author: Jon Kleinberg, Eva Tardos
c. Data Structures And Algorithms Made Easy In JAVA
Author: Narasimha Karumanchi
*** Useful Web Links:
Class Lectures:
- Week-01 Preparing Background
Week-01 Preparing Background
Topics of discussion
- Introduction and importance of Algorithm and its application
- Function and Recursion,
- Euclid’s Greatest Common Divisor(GCD) Algorithm
Expected Learning Outcome
- Gain knowledge about the importance of algorithm
- Perform exercise on function and recursion function
Week-01 Plan
Week plan
|
Topics
|
Materials
|
Week-01: Lecture-01
|
Introduction to Algorithms
|
|
Week-01: Lecture-02
|
Computational complexity and Asymptotic Notation of Algorithms
|
PowerPoint Slide
|
Week-01: Lab - 01
|
Problems with C Basics, Loops, Array, F
unction, Recursion
|
|
Lab -01
Some Other Resources
Discussion on the topics covered in Week-01 Forum
Restricted Not available unless: You belong to any group
Dear Student, You can Discuss on Week-01 contents that we covered in this week. If you have any problem and confusion or suggestion, feel free to share.
|
- Week-02: Notation and Complexity Analysis
Week-02: Notation and Complexity Analysis
Topics of discussion
- Introduction with the Asymptotic Notation
- Discussion on the Complexity of Algorithms
- Importance of Complexity for designing an Algorithm
Expected Learning Outcome
- Gain knowledge about the importance of algorithm
- Find out the Asymptotic Notation from an Algorithm
- Find out the complexity from any code or algorithm
Week-02 Plan
Week plan
|
Topics
|
Materials
|
Week-02: Lecture-03
|
Asymptotic Notation and Complexity Analysis
|
|
Week-02: Lecture-04
|
Searching Algorithms: Linear Search and Binary Search
|
|
Week-02: Lab - 02
|
Problems with Array, Function, Binary Search
|
|
- Week-03 Searching and Sorting Algorithm Based on Brute Force Approach
Week-03 Searching and Sorting Algorithm Based on Brute Force Approach
Topics of discussion
- Introduction to brute force techniques.
- Introduction to the searching Algorithm.
- Introduction to the sorting Algorithm
- Quiz #01
Expected Learning Outcome
- Knowledge about the Linear Search algorithm and its complexity
- Knowledge about the Insertion sort algorithm and its complexity
- Knowledge about the Bubble sort algorithm and its complexity
- Knowledge about the Selection sort algorithm and its complexity
- Exercise the Sorting and searching Algorithm with some additional problems.
Week-03 Plan
Week plan
|
Topics
|
Materials
|
Week-03: Lecture-05
|
Introduction to Sorting Algorithms:
1. Selection Sort and
2. Insertion Sort
|
|
Week-03: Lecture-06
|
Divide and Conquer Approach:
Merge Sort
|
|
Week-03: Lab - 03
|
Sorting Algorithms:
Selection Sort and Insertion Sort
|
|
- Week-04 Searching and Sorting Algorithm Based on Divide and Conquer Approach
Week-04 Searching and Sorting Algorithm Based on Divide and Conquer Approach
Topics of discussion
- Introduction to Divide and Conquer Approach.
- Introduction to the searching Algorithm based on Divide and Conquer Approach.
- Introduction to the Sorting Algorithm based on Divide and Conquer Approach.
Expected Learning Outcome
- Knowledge about the Binary Search algorithm and its complexity
- Knowledge about the Merge sort algorithm and its complexity
- Knowledge about the Quick sort algorithm and its complexity
- Exercise the Sorting and searching Algorithm with some additional problems.
Week-04 Plan
Week plan
|
Topics
|
Materials
|
|
|
|
Week-04: | Lecture-07 |
Discussion on Divide and Conquer Approach:Merge Sort
|
|
|
|
|
|
- Week-05 Introduction to Greedy Approach
Week-05 Introduction to Greedy Approach
Topics of discussion
- Introduction to Greedy Approach
- Discussion on Coin Change Problem
- Discussion on Bin packing Problem
- Discussion on Knapsack Problem
- Discussion on Hoffman coding
- Assignment-01
Expected Learning Outcome
- Solve the Coin Change Problem based on Greedy Method
- Solve the Knapsack Problem based on Greedy Method
- Solve the Hoffman coding based on Greedy Method
- Solve the Bin packing Problem based on Greedy Method
- Exercise the Sorting Algorithm with some additional problems in the Lab.
Week-05 Plan
Week plan
|
Topics
|
Materials
|
Week-05: Lecture-09
|
Greedy Method:
|
|
Week-05: Lecture-10
Date:
|
Greedy Partial Knapsack Greedy Huffman Coding
|
Lecture Slide
|
Week-05: Lab - 05
|
Implementation of
|
Lab Task - 4
|
- Week-06: Introduction to Dynamic Programming
Week-06: Introduction to Dynamic Programming
Topics of discussion
- Introduction to Dynamic Programming (DP)
- Discussion on Fibonacci Numbers Problem
- Discussion on Coin Change Problem (DP)
- Discussion on Knapsack Problem (0/1)
Expected Learning Outcome
- Solve the Coin Change Problem based on DP
- Solve the Knapsack Problem based on DP
- Solve the Fibonacci Numbers Problem based on DP
- Exercise the Bin-packing Algorithm with some additional problems in the Lab.
Week-06 Plan
Week plan
|
Topics
|
Materials
|
Week-06: Lecture-11
|
1. Fibonacci Numbers Problem
2. DP: Coin Change
|
|
Week-06: Lecture-12
|
DP: 0/1 Knapsack
|
Slide on 0/1 Knapsack
|
Week-06: Lab - 0
6
|
Fibonacci Series Coin Change
|
|
- Week-07 Mid-Term Examination
Week-07 Mid-Term Examination
- Week-08: Introduction to Dynamic Programming (Continue)
Week-08: Introduction to Dynamic Programming (Continue)
l
Topics of discussion
- Introduction to Dynamic Programming (DP)
- Discussion on longest Common Subsequence and Edit Distance Problem
- Discussion on longest Increasing Subsequence (DP)
Expected Learning Outcome
- Solve the Longest Common Subsequence (LCS) Problem based on DP
- Solve the Longest Increasing Subsequence (LIS)
- Exercise the Bin-packing, LCS, LIS Algorithm with some additional problems in the Lab.
Week-08 Plan
Week plan
|
Topics
|
Materials
|
Week-08: Lecture-01
|
Longest Increasing Subsequence(LIS)
|
Lecture Slide: LIS
|
Week-08: Lecture-02
|
Longest Common Subsequence (LCS)
|
Lecture Slide
|
Week-08: Lab - 07
|
Implementation of LCS, LIS
|
Lab Task - 7
|
- Week-09: Introduction to Graph And Graph Traversal
Week-09: Introduction to Graph And Graph Traversal
Topics of discussion
- Introduction to Graph
- Graph Representation
- Discussion on Graph Traversal
Expected Learning Outcome
- Solve the Breadth-First Search (BFS) algorithm
- Solve the Depth First Search (DFS) Algorithm
Week-09 Plan
Week plan
|
Topics
|
Materials
|
Week-09: Lecture-01
|
Graph and Graph Representation
|
|
Week-09: Lecture-02 |
BFS, DFS and Application of DFS
|
Lecture Slide: BFS+DFS
|
Week-09: Lab - 08 |
Implementation of Graph, DFS
|
Lab Task on Graph
|
- Week-10: Graph Application
Week-10: Graph Application
Topics of discussion
- DFS Application
- Quiz #03
Expected Learning Outcome
- Full Tree Traversal
- Cycle Finding
- Component FInding
- Topological Sort (TS)
- Strongly Connected Component (SCC)
Week-10 Plan
Week plan
|
Topics
|
Materials
|
Week-10: Lecture-01
- Video on Lecture
- PPT on Lecture
|
Full Tree Traversal Cycle Finding Component Finding
|
PPT link
|
Week-10: Lecture-02
- Video on Lecture
- PPT on Lecture
|
Ts, SCC
|
PPT link
|
Week-10: Lab - 09
- Video on Lab
- Manual on Lab
|
DFS, MST Lab performance-02
|
Manual Link
|
- Week-11: Graph: Single Source Shortest Path Algorithm
Week-11: Graph: Single Source Shortest Path Algorithm
Topics of discussion
- Discussion on Minimum Spanning Tree (MST)
- Discussion on Single Source Shortest Path
Expected Learning Outcome
- Solve MST using Kruskal’s Algorithm
- Solve MST using Prim’s Algorithm
- Single-Source Shortest Path(SSSP) by Dijkstra’s Algorithm
Week-11 Plan
Week plan
|
Topics
|
Materials
|
Week-11: Lecture-01
|
MST: Kruskal’s Algorithm
MST: Prim’s Algorithm
|
Slide
|
Week-11: Lecture-02
|
SSSP: Dijkstra’s Algorithm
|
Slide
|
Week-11: Lab
|
Dijkstra Implementation
|
Tutorial Resource
|
- Week-12: Graph: All Pair Shortest Path Algorithm
Week-12: Graph: All Pair Shortest Path Algorithm
Topics of discussion
- Discussion on All Pair Shortest Path Algorithm
Expected Learning Outcome
- Solve SSSP using Bellmen Ford Algorithm
- All Pairs Shortest Path: Floyd–Warshall algorithm
Week-12 Plan
Week plan
|
Topics
|
Materials
|
Week-12: Lecture-01
- Video on Lecture
- PPT on Lecture
|
SSSP: Bellman-Ford Algorithm
|
PPT link
|
Week-12: Lecture-02
- Video on Lecture
- PPT on Lecture
|
Floyd–Warshall algorithm
|
PPT link
|
Week-12: Lab - 11
- Video on Lab
- Manual on Lab
|
Implementation of Floyd–Warshall algorithm
|
Manual Link
|
Lab Project Submission Link
- Week-13: Final Presentation and Lab Final
Week-13: Final Presentation and Lab Final
- Week-14: Final Examination
Week-14: Final Examination
- Final Examination Summer 2021
This topic
Final Examination Summer 2021
- Topic 16
- Topic 17
- Topic 18
- Topic 19
- Topic 20