CS-A1140 Data Structures and Algorithms

These are the online lecture notes for the Aalto University course CS-A1140 Data Structures and Algorithms for the Autumn \(2020\). This course has the Aalto course CS-A1120 Programming 2 as a prerequisite and assumes programming skills in Scala.

Contents:

• Round 1: Recap and basic data structures
  • Describing algorithms
  • Basics of Analysis of Algorithms
  • Experimental analysis
  • Arrays
  • Resizable arrays
  • Linked lists
  • Stacks
  • Queues and Deques
• Round 2: Sorting
  • Basic definitions
  • Selection sort
  • Insertion sort
  • Mergesort
  • Quicksort
  • Asymptotic lower bounds
  • Counting and Radix Sorts
• Round 3: Trees
  • Basic definitions
  • Traversing trees
  • Priority queues with binary heaps
  • Disjoint-sets with the union-find data structure
• Round 4: Binary Search Trees
  • Introduction: sets and maps
  • Binary search trees
  • Balancing Binary Search Trees
  • AVL Trees
  • Red-Black Trees
  • Extra: B-trees
• Round 5: Hashing
  • Intro: small key universe, bit sets and direct-access tables
  • Hashing and hash tables
  • Building hash functions
  • Extra: Cryptographic hash functions
• Round 6: Dynamic programming and greedy algorithms
  • Dynamic programming
  • Greedy Algorithms
• Round 7: Graphs, part I
  • Mathematical definitions
  • Representations
  • Breadth-first search
  • Depth-first search
  • Topological sort
  • Strongly Connected Components
• Round 8: Graphs, part II
  • Edge-weighted graphs
  • Minimum spanning trees
  • Single-source shortest paths
• Round 9: Multithreaded algorithms
  • Introduction
  • Basic definitions
  • Threads
  • Parallel for-loops
  • Embarrassingly parallel problems
  • Fork-join framework
  • Example: Implementing parallel count
  • Parallel mergesort
  • Some parallel methods in the standard libraries
• Round 10: Computationally more difficult problems
  • Computational problems
  • Polynomial-time solvable problems
  • Problems in NP (Non-deterministic Polynomial time)
  • NP-complete problems
  • How to prove a new problem NP-complete?
  • Approaches for Solving NP-Complete problems

Indices and tables

• Index

• Module Index

• Search Page