Mathematical Problem Solving
Teacher
Dr. Sasmita Kumari Nayak
Category
Course Attendees
Still no participant
Course Reviews
Still no reviews
Course Name : Mathematical Problem Solving
Code(Credit) : CUTM1037(2-2-0)
Course Objectives
- To understand and analyze algorithms
- To understand efficiency of algorithms and alternative approaches
- To understand data structures and major algorithms and how they together play a role in efficiency
- To apply important algorithm design techniques using a programming language
Course Outcomes
COs |
Course Outcomes |
Mapping COs with POs (High-3, Medium-2, Low-1) |
CO1 |
Ability to get knowledge on appropriate data type and data structure for a given problem |
PO1 (3), PO12(1) |
CO2 |
Analyze to compare algorithms with respect to time and space complexity |
PO2(3) |
CO3 |
Ability to select the best algorithm to solve a problem by considering various problem characteristics, such as the data size, the type of operations, etc |
PO2(3) |
CO4 |
Design and develop different algorithms for solving the problems |
PO3 (3) |
Course Syllabus
Module I: Introduction (4 Hrs)
Mathematics in Computer Science, Problem Solving and Algorithms, Data Structures and Algorithms, Algorithm Efficiency and Importance.
Module II: Problem Types (4 Hrs)
Sorting, Searching, String Processing, Graph and Numerical Problems
Module III: Algorithm Efficiency (6 Hrs)
Orders of Growth, Best-Case, Worst-Case and Average-Case Efficiencies, Analysis of Recursive and Non-Recursive Algorithms
Module IV: Brute Force and Exhaustive Search (10 Hrs)
Selection Sort and Bubble Sort, Sequential Search and Brute-Force String Matching, Exhaustive Search, Depth-First Search and Breadth-First Search.
Module V: Divide and Conquer (10 Hrs)
Merge Sort, Quick Sort, Binary Tree Traversal, Closest-Pair and Convex-Hull Problems
Module VI: Dynamic Programming and Greedy Technique (16 Hrs)
Dynamic programming- Floyd ‘s algorithm, Optimal Binary Search Trees, Knapsack Problem and Memory functions.
Greedy Technique- Prim’sAlgorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman Trees.
Module VII: Limitations of Algorithm Power (4 Hrs)
Lower-Bound Arguments, Decision Trees, P, NP and NP- Complete Problems.
Text Books:
- Fundamentals of Computer Algorithms, 2nd Edition, Ellis Horowitz, Sartaj Sahni and S. Rajasekharan
- Introduction to the Design and Analysis of Algorithms, Anany Levitin
Reference Books:
- Design and Analysis of Algorithms: S. Sridhar
- Design and Analysis of Algorithms: P. H. Dave, H. B. Dave
- Algorithm Design: Foundations, Analysis and Internet Examples: M. T. Goodrich and R. Tomassia, John Wiley and sons
- Algorithms Illuminated (Part 2): Graph Algorithms and Data Structures:Tim Roughgarden
Session Plan
Session 1 & 2 (Module I)
Mathematics in Computer Science, Problem Solving and Algorithms:PPT
https://www.youtube.com/watch?v=BP8UzIZj-nU
https://www.youtube.com/watch?v=0IAPZzGSbME&list=PLch-RuUgf43mvNLxnsYjXffEG0fRdQ5KB
Session 3 & 4
Data Structures and Algorithms, Algorithm Efficiency and Importance: PPT
Session 5 & 6 (Module II)
Sorting, Searching, String Processing:PPT
Session 7 & 8
Session 9 & 10 (Module III)
Orders of Growth, Best-Case, Worst-Case and Average-Case Efficiencies: PPT
Session 11 & 12
Analysis of Recursive algorithms: Substitution method, recursion tree method and master method: PPT
https://www.youtube.com/watch?v=JPAA1FbM7jk
Session 13 & 14
Analysis of Non-Recursive Algorithms with example: PPT
Session 15 (Module IV)
Selection Sort: Problem-solving, Algorithm, Find Best, worst, and average case Time complexity: PPT
Session 16
Practice 1:
- Sort the list E, X, A, M, P, L, E in alphabetical order by selection sort.
Session 17
Bubble Sort: Problem-solving, Algorithm, Find Best, worst, and average case Time complexity:PPT
Session 18
Practice 2:
- Sort the list E, X, A, M, P, L, E in alphabetical order by Bubble sort.
Session 19 & 20
Sequential Search and Brute-Force String Matching, Exhaustive Search:PPT
https://www.youtube.com/watch?v=Fit5lRYZAm4
Session 21
Practice 3:
You are given a string “s” and s pattern “p”, you need to check if the pattern is there in the string.
S = “prodevelopertutorial”
P = “rial”
We need to check if “rial” is present in “prodevelopertutorial” string. Use Brute Force Search Approach
Session 22 & 23
Depth-First Search and Breadth-First Search: problem solving, Find Time complexity:DFS-PPT, BFS-PPT
Session 24
Practice 4:
- Write down the adjacency matrix and adjacency lists specifying this graph. (Assume that the matrix rows and columns and vertices in the adjacency lists follow in the alphabetical order of the vertex labels.)
- Starting at vertex a and resolving ties by the vertex alphabetical order, traverse the graph by depth-first search and construct the corresponding depth-first search tree. Give the order in which the vertices were reached for the first time (pushed onto the traversal stack) and the order in which the vertices became dead ends (popped off the stack).
Session 25, 26 & 27 (Module V)
Merge Sort: Problem-solving, Algorithm, Find Best, worst, and average case Time complexity: LECTURE NOTES
https://www.youtube.com/watch?v=mB5HXBb_HY8
https://www.youtube.com/watch?v=g1AwUYauqgg
Practice 5:
- Sort the list E, X, A, M, P, L, E in alphabetical order by Merge sort.
Session 28, 29 & 30
Quick Sort: Problem-solving, Algorithm, Find Best, worst, and average case Time complexity: LECTURE NOTES
Practice 6:
- Sort the list E, X, A, M, P, L, E in alphabetical order by Quick sort.
Session 31, 32, 33 & 34
Binary Tree Traversal, Closest-Pair and Convex-Hull Problems: Closest pair-convex hull problem
Session 40 & 41
knapsack problem: Problem solving, Algorithm, Time complexity
Practice 8:
a. Apply the bottom-up dynamic programming algorithm to the following instance of the knapsack problem:
b. How many different optimal subsets does the instance of part (a) have?
c. In general, how can we use the table generated by the dynamic programming algorithm to tell whether there is more than one optimal subset for the knapsack problem’s instance?
Session 42, 43, 44 & 45
Greedy Technique- Prim’sAlgorithm, Kruskal’s Algorithm: Problem solving, Algorithms, Different cases of Time complexities: LECTURE NOTES
VIDEO 1, VIDEO 2, VIDEO 3, VIDEO 4
Practice 9 & 10:
a. Apply Prim’s and Kruskal's algorithm to the following graph.:
Session 48 & 49
Huffman Trees: Problem solving, Algorithms, Different cases of Time complexities:LECTURE NOTES
Practice 12:
Consider the five-symbol alphabet {A, B, C, D, _} with the following occurrence frequencies in a text made up of these symbols:
Session 50, 51 & 52 (Module VII)
Lower-Bound Arguments, Decision Trees, P, NP and NP- Complete Problems:LECTURE NOTES 1, LECTURE NOTES 2, VIDEO
Our Main Teachers
Dr. Sasmita Kumari Nayak
Associate Professor, Department of Computer Science & Engineering
VIEW PROFILEReceived M.Tech in Information Technology from BPUT University in the year of 2010 and completed Ph.D. in Computer Science and Engineering at Sambalpur University in 2022. Currently working as an Associate Professor at Centurion University of Technology and Management since 2009.
G RAMA DEVI ,MCA,M.TECH(CSE),(Ph.d) working as Assistant professor, Department of CSE, Centurion University of Technology and Management, Andhra Pradesh. Interested to work on Data Structures, Python, Machine Learning, Database Management Systems and Web Development, Problem Solving Methodologies. Programming Skill: Data structures, C programming, python, Web development (Html, CSS,JS), Database Management Systems.