Scribd Logo
Upload

Welcome to Scribd!

  • 97 views

    DSA 1 Note-An Introduction

    Uploaded by

    uttam
    This document outlines a course on data structures and algorithms. The course covers fundamental data structures like arrays, linked lists, stacks, queues, trees, and graphs. It teaches algorithms for searching, sorting, string matching, and graph problems. Topics include asymptotic analysis, recursion, greedy algorithms, divide and conquer, and dynamic programming. The goal is for students to understand various data structures, algorithms, and analyze their time and space complexities.

    Copyright:

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

    DSA 1 Note-An Introduction

    Uploaded by

    uttam
    97 views6 pages
    This document outlines a course on data structures and algorithms. The course covers fundamental data structures like arrays, linked lists, stacks, queues, trees, and graphs. It teaches algorithms for searching, sorting, string matching, and graph problems. Topics include asymptotic analysis, recursion, greedy algorithms, divide and conquer, and dynamic programming. The goal is for students to understand various data structures, algorithms, and analyze their time and space complexities.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document outlines a course on data structures and algorithms. The course covers fundamental data structures like arrays, linked lists, stacks, queues, trees, and graphs. It teaches algorithms for searching, sorting, string matching, and graph problems. Topics include asymptotic analysis, recursion, greedy algorithms, divide and conquer, and dynamic programming. The goal is for students to understand various data structures, algorithms, and analyze their time and space complexities.

    Copyright:

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

    DSA 1 Note-An Introduction

    Uploaded by

    uttam
    This document outlines a course on data structures and algorithms. The course covers fundamental data structures like arrays, linked lists, stacks, queues, trees, and graphs. It teaches algorithms for searching, sorting, string matching, and graph problems. Topics include asymptotic analysis, recursion, greedy algorithms, divide and conquer, and dynamic programming. The goal is for students to understand various data structures, algorithms, and analyze their time and space complexities.

    Copyright:

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

    Data Structures & Algorithms

    (ESO1-CSE 201)

    Prasanta K. Jana, IEEE Senior Member


    Department of Computer Science and Engineering
    Indian Institute of Technology (ISM), Dhanbad
    E-mail: prasantajana@iitism.ac.in
    Course Course
    Name of Course L T P Credit
    Type Code

    ESO1 CSE201 Data Structures & Algorithms 3 0 0 9

    Unit Lecture
    Topics to be Covered Learning Outcome
    No. Hours

    Objectives of time analysis of algorithms; Big Oh Learning towards algorithm performance


    1 3
    and Theta notations analysis in terms of time and space complexity

    Elementary data-structures: arrays, linked lists, Understanding of elementary data structures


    2 6
    queues, stacks and their applications. with some applications

    Binary search algorithm, binary trees, binary-search- Learning of efficient searching solution using
    3 tree data-structure, Balanced binary-search-tree: 7 binary tree and their variations
    Red-Black trees,

    Bubble, Insertion, Merge, Heap and quicksort Understanding of various sorting algorithms
    4 6
    Sorting algorithms with varying complexity

    Greedy paradigm with examples, Divide and learning of various algorithm paradigms with
    5 conquer paradigm with examples, Dynamic- 6 application in example problems
    programming paradigm with examples

    Definition of graphs, paths, trees, cycles. Data Understanding of graph data structure with
    structures for graphs: adjacency lists, adjacency their representation, traversal methods,
    matrix. Graph algorithms: Depth First Search, Learning of shortest path problem and various
    6 7
    Breadth First Search, Minimum Spanning tree, standard shortest path algorithms
    Dijkstra’s, Bellman ford and Floyd Warshell’s
    shortest path algorithms

    Naive, Automata based, KMP String matching Understanding of various string matching
    7 4
    algorithms algorithms with varying complexity

    Hashing techniques Understanding of efficient searching solution


    8 2
    using hash table

    Text Books:

    1. J .P . Tremblay and P. G . Sorenson, An Introduction to Data Structures with Application, Tata Mc-Graw Hill.
    2. Horowitz and Sahani, Fundamentals of Computer Algorithms, Galgotia
    3. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, Prentice Hall of India, 3rd Edition, 2010.

    Reference Books:

    1. AV Aho, J Hopcroft, JD Ullman, Data Structures and Algorithms, Addison- Wesley, 1983.
    2. MT Goodrich, R Tamassia, DM Mount, Data Structures and Algorithms in Java, 5th Ed., Wiley, 2010.
    What is Data Structure?
    A way of organizing all data items that considers not only data elements stored but also
    their logical relationships to each other.
    Examples: Array, Tree, graph etc.

    Array: A[1] A[2] A[3] A[4] A[5]

    Tree:

    What is Storage Structure?


    The representation of a particular data strcuture in the main memory of a computer.

    Classification of Data Structure:


    Primitive vs. Non-primitive:
    Linear vs. Non-linear

    The study of data strcure covers:


     Representation
     Allocation/Access methods
     Operations, their applications
     Complexity Analysis
    What is an Algorithm?

    An Algorithm of summing array elements:


    Example:

    Proof: 3n + 2 <= 5n for all n>=1


    We write:

    Note: 3n +2 = O(n2) because 3n + 2 <= 3n2 for all n>=2.


    O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)
    Note that

    You might also like