Data Structures & Algorithms
Data structures for computer engineers, implemented in Python and C: abstract data types and the cost of operations, Big-O analysis, arrays, memory layout and dynamic arrays, linked lists and fixed node pools, stacks, queues and circular buffers, recursion, binary trees and traversals, balanced search trees and B-trees, heaps and priority queues, hash tables, sorting algorithms, and searching and graph traversal, ending with the data-structure design of an embedded traffic counter and its server.
CMP-200 Year 2 3 credits 12 lessons · 4 h 22 min ▶ Video lessons coming soon
Offered by HSM University · Computer Engineering
This is the Canadian version of this course. See the American version.
What you'll learn
- Distinguish abstract data types from the data structures that implement them, and choose a structure by listing the operations, their frequency, the data size and the constraints of the target machine.
- Analyze the cost of code with Big-O, Big-Omega and Big-Theta notation, including best, worst, average and amortized cases, and recognize what asymptotic analysis hides.
- Explain array address arithmetic, row-major layout and cache behaviour, and implement a dynamic array whose appends cost O(1) amortized.
- Implement singly and doubly linked lists with sentinels and fixed node pools, and compare their costs and memory behaviour with arrays.
- Implement stacks and queues, including circular buffers shared safely between an interrupt and a main loop, and apply them to bracket checking and expression evaluation.
- Write and analyze recursive functions with base cases, recurrences and stack-depth limits, and convert deep recursion into loops or explicit bounded stacks.
- Describe binary trees, their height and storage in linked and array forms, and apply preorder, inorder, postorder and level-order traversals.
- Implement binary search tree search, insertion, deletion and range queries, and explain how rotations in AVL and red-black trees, and B-trees, keep operations logarithmic.
- Implement binary heaps with sift-up and sift-down, build heaps in linear time, and use priority queues for scheduling and top-k selection.
- Design hash tables with suitable hash functions, load factors and collision resolution by chaining or open addressing, and recognize when ordered structures are needed instead.
- Compare insertion sort, merge sort, quicksort, heapsort, counting sort and radix sort by cost, stability, memory and adaptivity, and choose a sort for a given situation.
- Apply lower-bound binary search, represent graphs with adjacency lists and matrices, use breadth-first and depth-first search, and justify the data structures of a complete embedded and server system.
Course content
12 lessons · 4 h 22 min total · final exam
- 1 Data structures, abstract data types and the cost of an operation 24 min · quiz
- 2 Algorithm analysis and Big-O notation 20 min · quiz
- 3 Arrays, memory layout and dynamic arrays 21 min · quiz
- 4 Linked lists 21 min · quiz
- 5 Stacks and queues 22 min · quiz
- 6 Recursion 20 min · quiz
- 7 Binary trees and traversals 23 min · quiz
- 8 Binary search trees and balancing 22 min · quiz
- 9 Heaps and priority queues 21 min · quiz
- 10 Hash tables 21 min · quiz
- 11 Sorting algorithms 24 min · quiz
- 12 Searching, graphs and a capstone design 23 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
Data structures for computer engineers, implemented in Python and C: abstract data types and the cost of operations, Big-O analysis, arrays, memory layout and dynamic arrays, linked lists and fixed node pools, stacks, queues and circular buffers, recursion, binary trees and traversals, balanced search trees and B-trees, heaps and priority queues, hash tables, sorting algorithms, and searching and graph traversal, ending with the data-structure design of an embedded traffic counter and its server.
Part of the Engineering stream, typically taken in year 2.