Data Structure and Algorithms syllabus

Data Structure and Algorithms

• 1 Introduction to data structure and algorithms (4 LHs)

  • Data types, data structures and ADTs
  • Algorithm and computational complexity
  • Big-O, Big-Omega and Big-Theta
  • Best-, average- and worst-case analysis
• 2 Linked Lists (7 LHs)

  • List ADT and array implementation
  • Singly, doubly and circular lists
  • Node creation, insertion and deletion
  • Skip lists; Java LinkedList and ArrayList
• 3 Stack (4 LHs)

  • Stack ADT and array/linked implementations
  • Infix-to-postfix/prefix conversion and evaluation
  • Java stack utilities
• 4 Queues (4 LHs)

  • Queue ADT and primitive operations
  • Array and linked implementations
  • Circular and priority queues; applications
• 5 Recursion (2 LHs)

  • Direct, indirect, tail and nested recursion
  • Factorial, Fibonacci, GCD and Tower of Hanoi
  • Recursion versus iteration
• 6 Trees (9 LHs)

  • Tree ADT and binary-tree types
  • Traversals and binary search tree operations
  • AVL and expression trees
  • Heaps, Huffman algorithm and self-adjusting trees
  • B-trees
• 7 Graphs (7 LHs)

  • Graph ADT, representation and traversals
  • Greedy algorithms and Dijkstra shortest paths
  • Floyd-Warshall all-pairs shortest paths
  • Minimum spanning trees: Kruskal and Prim
  • Topological sorting
• 8 Sorting (6 LHs)

  • Internal and external sorting
  • Bubble, insertion, selection and heap sorts
  • Quicksort, mergesort and radix sort
  • Sorting efficiency and Java utilities
• 9 Searching and Hashing (5 LHs)

  • Linear and binary search
  • Hash functions: division, folding, mid-square and extraction
  • Collision resolution and Java hashing
• 10 Laboratory Works

  • Java list, stack and queue implementations
  • Recursion and binary search trees
  • Graph representation, spanning trees and shortest paths
  • Sorting, searching and hashing algorithms