COMP 2140
          Structures - University of Manitoba - Winter 2019

Course Information

    • Abstract data types

    • Java Programming (review)
      • object-oriented design & classes
      • private, public, protected methods

    • Algorithm Analysis
      • measuring the time complexity of iterative code
      • big Oh, big Omega, Theta notations

    • Stacks and Queues
      • push, pop, enqueue, dequeue
      • implementation as an array
      • implementation as a linked list
    • Recursion
      • iteration vs recursion
      • Fibonacci numbers
      • tail recursion

    • Binary Trees
      • insertion, deletion, searching; height, depth
      • children, parents, leaves, ancestry
      • tree traversal
      • implementation as a dynamic data structure
      • implementation as an array
      • binary search trees
    • Heaps
      • reheapUp, reheapDown, buildHeap
      • priority queues: insert, extractMax
      • binomial heaps and their merging
      • binomial trees

    • B-Trees
      • 2-3-4 trees
      • insertion in a B-tree

    • Sorting
      • insertion sort
      • mergesort: merging two sorted lists
      • quicksort: partitioning an array
      • heapsort
      • in-place sorting

    • Hash Tables
      • dictionary abstract data type
      • hash functions
      • chaining vs. open addressing
      • resolving collisions using open addressing

    • Graph Theory
      • implementation: adjacency list vs. adjacency matrix
      • minimum spanning tree: Prim's algorithm, Krukal's algorithm
      • graph colouring
      • graph isomorphism

List of topics & course material

        4. Sorting

                 Sorting: slides and handouts    
Here is Lab3 and the related java code
                 and solutions for Lab3 (for the updated code refer to Piazza).

        5. Arrays & Linked Lists

                 Arrays & Linked Lists: slides and handouts    
A midterm sample

Here is Lab4 and the related java code
                 and solutions for Lab4 (for the updated code refer to Piazza).

                 solutions for the midterm

                assignment 3 and test file for its programming parts are now posted.
                solutions for the written part of assignment 3.

        6. Hash Tables

                Hash Tables: slides and handouts

                Here is Lab5 and the related java code
                and solutions for Lab5 (for the updated code refer to Piazza).            

        8. Heaps

                Binary Heaps: slides and handouts
                Here is Lab6 and the related java code
                Solutions for Lab6

        9. Graph Theory   

               Graphs: slides and handouts
               assignment 5 and solutions for assignment 5

               sample for final