DSA

• Title


  Data Structures and Algorithms
• Course Code

  CSS/CSC 2051
• Course Name


  Data Structures and Algorithms
• Semester


  Spring 2024
• Instructor


  Surayya Obaid
• Department


  Department of Computer Science and Software Engineering
• Marks Distribution


  Midterm(20) + Lab(30) + Terminal(40)+ Sessional(10)
• Prerequisites


  Programming Fundamentals
• Contact Hours


  Monday(01-02pm), Wednesday(12-01pm)
• Course Outline


  • Abstract data types
  • Complexity analysis
  • Big O notation
  • Stacks (linked lists and array implementations)
  • Recursion and analyzing recursive algorithms
  • Divide and conquer algorithms
  • Sorting algorithms (selection, insertion, merge, quick, bubble, heap, shell, radix, bucket)
  • Queue
  • Dequeuer
  • Priority queues (linked and array implementations of queues)
  • Linked list & its various types
  • Sorted linked list
  • Searching an unsorted array
  • Binary search for sorted arrays
  • Hashing and indexing
  • Open addressing and chaining
  • Trees and tree traversals
  • Binary search trees
  • Heaps
  • M-way tress
  • Balanced trees
  • Graphs
  • Breadth-first and depth-first traversal
  • Topological order
  • Shortest path
  • Adjacency matrix and adjacency list implementations
  • Memory management and garbage collection
• Reference Material

  • Data Structures and Algorithm Analysis in Java by Mark A. Weiss
  • Data Structures and Abstractions with Java by Frank M. Carrano & Timothy M. Henry
  • Data Structures and Algorithms in C++ by Adam Drozdek
  • Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss
  • Java Software Structures: Designing and Using Data Structures by John Lewis and Joseph Chase
• Course Learning Outcomes


  • Implement various data structures and their algorithms and apply them in implementing simple applications
  • Analyze simple algorithms and determine their complexities
  • Apply the knowledge of data structure to other application domains
  • Design new data structures and algorithms to solve problems
• Ground Rules


  • 75% attendance is a criterion of HEC, completely non-negotiable. Keeping up with the criterion is your primary responsibility
  • Respect timings. Being in class for the first 5 minutes is better than your last 5 minutes presence
  • Maintain class decorum
  • Cell phone usage is strictly prohibited
  • Respect deadlines as extension will not be granted
• Muḥammad ibn Mūsā al-Khwārizmī

  Latinization of Al-Khwarizmi's name is 'algorithm'
• Computational Thinking


  A problem-solving methodology that involves breaking down complex problems into smaller, more manageable parts and systematically analyzing and solving them with the help of computers and algorithms
• Elements of Computational Thinking

  • Problem Decomposition
  • Pattern recognition
  • Abstraction
  • Algorithm design
  • Algorithm evaluation
  • Data representation
• Examples of Algorithms


  • Recommendation Algorithms
  • Search Algorithms
  • GPS Navigation Algorithms
  • Ad Targeting Algorithms
  • Image and Speech Recognition Algorithms
  • Social media algorithms
• Algorithm


  A step-by-step procedure or set of instructions for solving a problem or accomplishing a task. It is a finite sequence of well-defined, unambiguous, and executable steps that, when followed, produce a desired output or result within a finite amount of time.
• Key Characteristics of Algorithms

  • Finite
  • Well-Defined
  • Effective
  • Input
  • Output
  • Deterministic
• Data Structure


  A way of organizing, storing, and managing data in a computer so that it can be accessed and manipulated efficiently. It defines the relationship between data elements, the operations that can be performed on the data, and the rules or constraints governing those operations.
• Key Characteristics of Data Structures

  • Organization
  • Access
  • Manipulation
  • Efficiency
  • Memory Management
• Types of Data Structures

  • Linear data structure
  • Non linear data structure