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

Learning Outcomes

• Ability to decide the appropriate data type and data structure for a given problem.
• 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.
• Ability to compare algorithms with respect to time and space complexity

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)

Mathematics in Computer Science, Problem Solving and Algorithms :PPT

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

Graph and Numerical Problems: PPT

Session 9 & 10 (Module III)

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

Session 11 & 12

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

Session 13 & 14

Analysis of Non-Recursive Algorithms with example

Session 15 (Module IV)

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

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

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

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

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

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

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

Session 35, 36 & 37 (Module VI)

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

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.

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

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

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

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.