Scribd Logo
Upload

Welcome to Scribd!

  • 34 views

    Important Questions Algo

    Uploaded by

    Harsha Varthini

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Important Questions Algo

    Uploaded by

    Harsha Varthini
    34 views10 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    34 views10 pages

    Important Questions Algo

    Uploaded by

    Harsha Varthini

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 10

    CS3401/CS8451/AD8351

    MOST IMPORTANT QUESTIONS

    Theory

    Numerical/Programs

    Pass Understand Mark Score

    Easy Medium Hard Easy Medium Hard Easy Medium Hard


    Unit 1
    1. Algorithm analysis:
    a. Time and space complexity
    b. Asymptotic Notations and its properties Best case, Worst case and average case analysis
    2. Recurrence relation: substitution method
    3. Searching: linear search, binary search and Interpolation Search
    4. Pattern search: The naïve string- matching algorithm - Rabin-Karp algorithm - Knuth-Morris-Pratt
    algorithm.
    5. Sorting: Insertion sort – heap sort
    Unit 2
    1. Graph algorithms: Representations of graphs
    2. Graph traversal: DFS – BFS
    3. - applications - Connectivity, strong connectivity, bi-connectivity
    4. Minimum spanning tree: Kruskal’s and Prim’s algorithm
    5. Shortest path: Bellman-Ford algorithm - Dijkstra’s algorithm - Floyd-Warshall algorithm
    6. Network flow: Flow networks - Ford-Fulkerson method – Matching: Maximum bipartite
    matching
    Unit 3
    1. Divide and Conquer methodology:
    a. Finding maximum and minimum
    b. Merge sort
    c. Quick sort
    2. Elements of dynamic programming
    a. Matrix-chain multiplication
    b. Multi stage graph
    c. Optimal Binary Search Trees
    3. Greedy Technique: Elements of the greedy strategy
    a. Activity-selection problem
    b. Optimal Merge pattern
    c. Huffman Trees.
    Unit 4
    1. Backtracking:
    a. n-Queens problem
    b. Hamiltonian Circuit Problem
    c. Subset Sum Problem
    d. Graph colouring problem
    2. Branch and Bound
    a. Solving 15-Puzzle problem
    b. Assignment problem
    c. Knapsack Problem
    d. Travelling Salesman Problem
    Unit 5
    1. Tractable and intractable problems: Polynomial time algorithms – Venn diagram
    representation - NP- algorithms - NP-hardness and NP-completeness
    2. Bin Packing problem
    3. Problem reduction: TSP – 3- CNF problem.
    4. Approximation Algorithms: TSP
    5. Randomized Algorithms: concept and application - primality testing - randomized
    quick sort - Finding kth smallest number
    ORDER OF UNITS PREPARATION

    MARK SCORING PASS MARK ONLY


    CS8451 PYQ
    https://n.stucor.in/qp/STUCOR_QP-CS8451.pdf?_gl=1*1csn0b6*_ga*MTQ1MDMz
    NzE5My4xNjcxOTM4MDU3*_ga_D6D5Z4RF97*MTY4MzM0ODI0OC4zNi4xLjE2
    ODMzNDg4MDEuMC4wLjA.*_ga_N9LJVDX1HR*MTY4MzM0ODI0OC4zNS4xLjE
    2ODMzNDg4MDEuMC4wLjA.*_ga_54331VJR2D*MTY4MzM0ODI0OC4zNC4xLjE
    2ODMzNDg4MDEuMC4wLjA.&_ga=2.95052572.14298984.1683348248-1450337
    193.1671938057
    AD8351
    https://drive.google.com/file/d/10LEPqgexYpVdGpOQDT_wyyWag87lWdqB/view
    Resources with Video Link
    Asymptotic Notation https://www.youtube.com/watch?v=N3Pnr-uccq
    Recurrence Relation substitution M&list=PLR4Rlu17MDY4mzyAs0KcpzB9peeuhY
    Linear and Binary Search 1Zg&index=2&t=21s
    Naive string Matching and KMP

    MST- Prims and Kruskal https://www.youtube.com/watch?v=HRAL44RTF


    Insertion sort Uw&list=PLR4Rlu17MDY7SGvgxtRW7Z7NO5Ft
    N0Lma&index=1&t=3s&pp=gAQBiAQB
    From Abdul Bari https://www.youtube.com/watch?v=0IAPZzG
    SbME&list=PLDN4rrl48XKpZkf03iYFl-O29szj
    Trs_O&index=1

    Topic Video number

    Rabin Karp 9.2

    DFS BFS 5.1

    Dijkstra 3.6

    Merge,quick sort 2.7.2,2.8.1

    Matrix Chain 4.3

    Multi Stage,Optimal BST 4.1.1,4.6

    Merge Pattern,Huffman Coding 3.3,3.4

    N queen, hamiltonian,subset,graph coloring 6.1 to 6.4

    Knapsack TSP using branch bound 7.2 and 7.3

    Bin Packing https://www.youtube.com/watch?v=qbuMPi44bVQ

    You might also like