Course Objectives

• Evaluate algorithms and data structures in terms of time and memory complexity of basic operations
• Define basic static and dynamic data structures and relevant standard algorithms for them: stack, queue, dynamically linked lists, trees, graphs, heap, priority queue, hash tables, sorting algorithms, min-max algorithm
• Determine and demonstrate bugs in program, recognize needed basic operations with data structures
• Formulate new solutions for programming problems or improve existing code using learned algorithms and data structures

Learning Outcomes

• Evaluate algorithms and data structures in terms of time and memory complexity of basic operations
• Define basic static and dynamic data structures and relevant standard algorithms for them: stack, queue, dynamically linked lists, trees, graphs, heap, priority queue, hash tables, sorting algorithms, min-max algorithm
• Determine and demonstrate bugs in program, recognize needed basic operations with data structures
• Formulate new solutions for programming problems or improve existing code using learned algorithms and data structures

Course Syllabus

• Module I: Problem Solving Analysis (6 hrs) Define the problem, Identify the problem, Introduction to Problem Solving, Problem solving basics, Defining creativity v/s innovationFind Creative Solutions using creativity tools

  Effective problem solving approaches , Critical thinking and information analysis , Brainstorming, Reverse Brainstorming, Imagineering, Mind Mapping, Six Thinking Hats: A Tool to Strengthen Critical Thinking, Collaboration, Communication, and Creativity Skills , Analyzing the situation, Gathering information, Identifying solution criteria , Decision Making Methods , Charts and Diagrams , Applying outcome-based thinking

  Evaluate and Select solution

  Pro‟s and Con‟s, Force field analysis, Feasibility/Capability Analysis, Decision analysis, evaluating problems , Choosing among alternatives , Qualitative analysis, discussing qualitative analysis techniques , Establishing objectives , Assigning weight to objectives in order to make the best decision , Creating a satisfaction scale to choose between alternatives

  Implementing Decisions

  Create an action plan, Break solution into action steps, Prioritize actions and assign roles (setting priorities for taking action) ,Follow-up at milestones

  Programs:

  1. Problem solving (Control structures, Arrays) using Raptor Tool.

  Module II: Array & Stack (9 hrs)

  Analysis of different Algorithms, Asymptotic analysis, Algorithm analysis, Complexity Analysis, Application of Data structures

  Basic Data Structures, Arrays, Stacks and its applications (Recursion, Infix to Postfix Conversion and Postfix Evolution

  Programs:

  1. Write a program to perform the following menu driven program on the input array.
  2. Insertion
  3. Deletion
  4. Searching
  5. Sorting
  6. Merging
  7. Display
  8. Exit
  9. Write a program to perform the following menu driven program on the STACK.
  10. Push
  11. Pop
  12. Display
  13. Exit

  Module III: Queue & Linked List (9 hrs)

  Queues, Priority Queues, Dequees.

  Linked lists: Single Linked List and Operations on Single Linked List (Creation Insertion , Deletion , Sorting and Reverse ).

  Programs:

  1. Write a program to perform the following menu driven program on the Queue.
  2. Insertion
  3. Deletion
  4. Display
  5. Exit
  6. Write a program to create a single linked list performs the following menu driven program.
  7. Insertion at front
  8. Insertion at end
  9. Insertion at particular position
  10. Deletion at front
  11. Deletion at end
  12. Deletion at particular position
  13. Display

  Module IV: Stack & Queue Using Linked List (8 hrs)

  Circular linked list and Double linked list, Stack implementation using Linked List and Queue implementation using Linked List

  Programs:

  1. Write a program to create a Double linked list performs the following menu driven program.
  2. Insertion at front
  3. Insertion at end
  4. Insertion at particular position
  5. Deletion at front
  6. Deletion at end
  7. Deletion at particular position
  8. Display
  9. Write a program to create a circular linked list and display it.
  10. Write a program to implement Stack Using Linked List.
  11. Write a program to implement Queue Using Linked List.

  Module V: Trees (10 hrs)

  Trees and hierarchical orders ,Introduction to trees , Abstract trees , Tree traversals , Forests , Ordered trees , Binary trees , Perfect binary trees , Complete binary trees , Search trees , Binary search trees , AVL trees

  Programs:

  1. Write a program to create Binary tree and display it.
  2. Write a program to create a BST and display it.
  3. Write a program to print all pairs from two BSTs whose sum is greater than the given value.
  4. Write a program to remove duplicate entries from the BST.
  5. Write a program to create a AVL tree and display it.

  Module VI: Searching & Sorting (8 hrs)

  Searching & Sorting algorithms , Objectives of Searching , The Sequential Search , Analysis of Sequential Search , The Binary Search , Analysis of Binary Search , Introduction to sorting , Insertion sort , Bubble sort , Heap sort ,Merge sort ,Quick sort

  Programs:

  1. Write a program to perform linear and binary search.
  2. Write a program to perform selection sort, Bubble sort and Insertion sort.
  3. Write a program to perform merge and quick sort.
  4. Write a program to perform Heap sort.

  Module VII: Hashing (8 hrs)

  Hash functions and hash tables ,Hashing& Introduction to hash tables ,Hash functions , Mapping down to 0 ... M – 1 , Chained hash tables , Scatter tables , Open addressing , Linear probing , Quadratic probing , Double hashing, Poisson distribution , Collision Resolution

  Graph Terminology and Traversals.

  Programs:

  1. Write a program to perform Linear Probing.
  2. Write a program to perform Double Hashing

  Text Books:

  1. Data Structures, Algorithms and Applications in C++, Sartaj Sahani, 2nd Edition.
  2. Data Structures and Algorithms in C++, Michael T.Goodrich, R, Tamassia and D.Mount, wiley Student Edition, 7th edition, John Wiley and Sons.

  Reference Books:

  1. Data Structures and Algorithms Analysis in C++ by Mark Allen Weiss.
  2. Data Structures and Algorithms in C++, 3rd edition, Adam Drozdek, Cengage Learning.

Session Plan

Session 1

I am text block. Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

Session 2

I am text block. Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

Case Studies

Case Studies