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:

  1. Fundamentals of Computer Algorithms, 2nd Edition, Ellis Horowitz, Sartaj Sahni and S. Rajasekharan
  2. Introduction to the Design and Analysis of Algorithms, Anany Levitin

Reference Books:

  1. Design and Analysis of Algorithms: S. Sridhar
  2. Design and Analysis of Algorithms: P. H. Dave, H. B. Dave
  3. Algorithm Design: Foundations, Analysis and Internet Examples: M. T. Goodrich and R. Tomassia, John Wiley and sons
  4. Algorithms Illuminated (Part 2): Graph Algorithms and Data Structures:Tim Roughgarden

Session Plan

Session 1 & 2 (Module I)

Session 3 & 4

Data Structures and Algorithms, Algorithm Efficiency and Importance: PPT

https://www.youtube.com/watch?v=ovz54KoZo9o

https://www.youtube.com/watch?v=tEI9XrxXhwY

Session 5 & 6 (Module II)

Session 7 & 8

Session 9 & 10 (Module III)

Orders of Growth, Best-Case, Worst-Case and Average-Case Efficiencies: PPT

https://www.youtube.com/watch?v=D9SlLpPQRK8

https://www.youtube.com/watch?v=lj3E24nnPjI

Session 11 & 12

Analysis of Recursive algorithms: Substitution method, recursion tree method and master method: PPT

https://www.youtube.com/watch?v=JPAA1FbM7jk

https://www.youtube.com/watch?v=LC96q_6r3BQ

https://www.youtube.com/watch?v=OynWkEj0S-s

Session 13 & 14

Session 15 (Module IV)

Selection Sort: Problem-solving, Algorithm, Find Best, worst, and average case Time complexity: PPT

https://www.youtube.com/watch?v=8ps1XQigk7U

https://www.youtube.com/watch?v=peLS-S23TvE

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

https://www.youtube.com/watch?v=peLS-S23TvE

https://www.youtube.com/watch?v=o4bAoo_gFBU

Session 18

Practice 2: 

  • Sort the list E, X, A, M, P, L, E in alphabetical order by Bubble sort.

Session 19 & 20

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

https://www.youtube.com/watch?v=pcKY4hjDrxk

https://www.youtube.com/watch?v=vf-cxgUXcMk

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

VIDEO 1VIDEO 2VIDEO 3

Session 35, 36 & 37 (Module VI)

Dynamic programming- Floyd ‘s algorithm : Problem-solving, Algorithm, Find Best, worst, and average case Time complexity:PPT

VIDEO 1,VIDEO 2

Practice 7:

  • Solve the all-pairs shortest-path problem for the digraph with the following
    weight matrix:

Session 38 & 39

Write pseudocode for a linear-time algorithm that generates the optimal binary search tree from the root table.

VIDEO 1VIDEO 2

Session 40 & 41

knapsack problem: Problem solving, Algorithm, Time complexity

VIDEO 1VIDEO 2VIDEO 3

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 1VIDEO 2VIDEO 3VIDEO 4

Practice 9 & 10:

a. Apply Prim’s and Kruskal's algorithm to the following graph.:

Session 46 & 47

Dijkstra’s Algorithm: Problem solving, Algorithms, Different cases of Time complexities: PPT

VIDEO 1VIDEO 2

Practice 11:

Solve the following instances of the single-source shortest-paths problem with
vertex a as the source:

Session 48 & 49

Huffman Trees: Problem solving, Algorithms, Different cases of Time complexities:LECTURE NOTES

VIDEO 1VIDEO 2

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 2VIDEO

Our Main Teachers

Dr. Sasmita Kumari Nayak

Associate Professor, Department of Computer Science & Engineering
VIEW PROFILE

Received 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

Assistant Professor
VIEW PROFILE

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.