Data Structures: Home

1 Use C++ and Object Orientation

1.1 Create HelloWorld style programs Description Explain the entry point of a program, how it handles input and output, some fundamental data types and their conversions. Introduce the basic steps for its compilation and linking. In the module we stick with the Visual Studio Code possibilities.
(Goodrich2011)Ch01P01: Basic C++ Programming Elements (SOF:Khachaturyan2019)What is Plain Old Data (POD)   (de:Franneck2016A)Erstes Progrde:de:amm (Hel (de:Franneck2016B)Datentypen & Variablen (de:Franneck2016AD)Arrays (Erstellen & Initialisieren)
1.1.1. Create a simple HelloWorld program Basic examples; whey they posess the main characteristics of an algorithm and how to run them in graphical IDEs (Visual Studio Code, etc).

1. Write a program that also transforms input data
2. Use correct indentation and other basic coding conventions
3. Identify compiler and linker actions
4. Show the difference between the development environment and runtime environment.

1.1.2. Introduce fundamental types Describe all kinds of “built in” C++ types; their bitwise structure and how to initialize them.

1. Introduce integer types (short, int, long)
2. Introduce bool type
3. Define and use enum types
4. Introduce floating point types (float and double)
5. Introduce char type
6. Use type casts between the fundamental types

1.1.3. Declare and use arrays, pointers, references and struct types How to build “derived types” from fundamental types and other derived types.

1. Declare, define and initialize arrays of fundamental types
2. Declare and use pointers to variables
3. Refer to arrays using pointers
4. Declare and use references
5. Use C-style struct types
6. Use std:string to manipulate strings; convert to strings

1.1.4. Use namespaces, typedefs, local and global variables Introduce the identifiers (fully qualified with namespaces or local); understand the scope of a variable.

1. Define variables inside a scope
2. Refer to namespaced variables (with or without “using” statement)
3. Use “typedef” to give shorthand names for new types
4. Understand C++ variable scoping rules

1.2 Use expressions, control structures and functions in C++ Description This module introduces longer code fragments, builds larger expressions and assignments, explains the structures of loops, branching and switching statements.
(Goodrich2011)Ch01P02: Expressions (Goodrich2011)Ch01P03: Control Flow   (de:Franneck2016C)Rechnen mit Variablen (de:Franneck2016D)If Abfragen (de:Franneck2016E)Switch Anweisung
1.2.1. Declare, define and initialize variables, know their scope Distinguish between declarations and definitions; understand scoping and namespace rules.

1. Define variable pointers and references
2. Use namespaces explicitly or implicitly
3. Use literal values in variable initializations
4. Use “external” keyword and global variables (accessible in multiple modules)

1.2.2. Write conditional statements Use correct syntax and best practices for conditional statements (3 kinds)

1. Write if and if-else statements
2. Write chains of if statements; place next if statement in the else branch only.
3. Write switch statements, use breaks; understand performance implications of “switch” vs. “if”

1.2.3. Write loop statements. Use correct syntax and best practices for loop statements

1. Write pre-increment and postincrement loops, loop variable scope
2. Write while statements

1.2.4. Declare enum datatypes
1.2.5. Declare struct datatypes

1.3 Use C++ classes Description Explain the structure of class definition, public, private members, nested classes, constructors and destructors.
(Goodrich2011)Ch01P05: C++ Classes (Goodrich2011)Ch01P06: C++ Program and File Organization   (de:Franneck2016CA)Eigene Klassen & Header
1.3.1. Define and use struct types Describe struct types as aggregations of (public) data members.

1. Define struct as a heterogeneous collection of different types
2. Understand struct layout in memory and reinterpret type casts
3. Explain C++ Plain Old Data (POD) concept

1.3.2. Define and use class types Explain why classes are used differently from types; what changes as we use “single concern” and “encapsulation” principles (i.e. hiding implementation details).

1. Define public and private members
2. Use encapsulation principle in OO
3. Recognize Dijkstra’s “one concern per class” principle

1.3.3. Understand class member instantiation Understand what happens as new class members are instantiated, in which order parent/child objects are instantiated; initializer lists, etc.

1. Write simple class constructors
2. Write class destructors
3. Use “public” class inheritance

1.3.4. Use class design principles Specify the function/method prototypes using public/private/protected, also “const” specifiers.

1. Use Liskov principle (subclass can replace parent class)
2. Use “const” modifier for methods and their formal parameters
3. Understand the visibility of class members by other members, clients and friends.

1.3.5. Use C++ build utilities and Makefiles Create and build C++ sources and headers to reflect the design of your C++ classes.

1. Use Linux command-line utilities g++ and similar.
2. Build your code from multiple files inside the C++ IDEs.
3. Understand the use of macro commands; use macros to do definition guards.
4. Understand the process of compilation and linking.
5. Separate declarations/definitions between header (H) and source (CPP) files.
6. Write Makefile for typical
7. Best practices and mistakes when setting up build practices (typical linker errors; not recompiling or not including all dependencies, name conflicts)

1.4 Use arrays, pointers and references in functions Description Define functions with appropriate prototypes (to pass arrays and large objects). Separate concerns go into different files and mutual function calls.
(Goodrich2011)Ch01P04: Functions
1.4.1. Use various flavors of function calls Describe the typical patterns of parameter passing to C++ functions

1. Define and call functions passing parameters by value
2. Define and call functions passing parameters by reference

1.4.2. Pass arrays and large objects as parameters to functions

1. Pass static arrays as parameters, specify array length as an extra paramater
2. Pass dynamic arrays as parameters
3. Pass large objects as references with “const” modifier

1.4.3. Use recursive functions in C++ Some flavors of recursion, their implications on memory use, time efficiency and declaration order in the source files

1. Use plain recursion and tail recursion
2. Use mutual recursion
3. Use function pointers

2 Express algorithms through ADTs and data structure libraries

2.1 Analyze algorithms by counting data related operations Description Here we analyze the algorithms at pseudocode level (making assumptions regarding the cost of data structure library calls). More detailed analysis that takes into account alternatives of implementing the data structures themselves is postponed to other modules.
(Goodrich2011)Ch04P02: Analysis of Algorithms
2.1.1. Identify the key characteristics of an algorithm
2.1.2. Determine function growth classes using O-notation, Ω-notation, Θ-notation.
2.1.3. Define the time complexity of an algorithm; make assumptions about the data structure manipulations
2.1.4. Define the space complexity of an algorithm
2.1.5. Describe the difference between feasible and infeasible algorithms
2.1.6. Worst-case, expected and amortized complexity
2.2 Use Object Orientation concepts in C++ Description The module explains the thinking behind keywords “public”, “private”, inheritance – and how this is typically used in writing algorithms and data-structure libraries.
(Goodrich2011)Ch02P01: OO Goals, Principles and Patterns (Goodrich2011)Ch02P02: Inheritance and Polymorphism (Goodrich2011)Ch02P03: Templates
2.2.1. Explain abstraction as an OO principle
2.2.2. Explain encapsulation as an OO principle; keywords public/private and friends
2.2.3. Explain inheritance as an OO principle; inheriting class contract
2.2.4. Explain polymorophism as an OO principle; keywords virtual/abstract
2.2.5. Define class hierarhies following the OO principles
2.2.6. Explain function overriding with inheritance
2.2.7. Explain abstract classes and virtual functions.
2.2.8. Define template functions and template classes.
2.2.9. Define and use overloaded operators

2.3 Define and implement functions for simple Abstract Data Types (ADT) Description This module discusses just the simplest ADTs.
(Goodrich2011)Ch01P05: C++ Classes (Goodrich2011)Ch06P01: Vectors (Goodrich2011)Ch06P02: Lists (Goodrich2011)Ch06P03: Sequences
2.3.1. Define stack as an ADT
2.3.2. Define a deque as an ADT
2.3.3. Define a list as an ADT
2.3.4. Define a sequence as an ADT
2.3.5. Define a binary tree as an ADT
2.3.6. Define a map as an ADT
2.3.7. Understand how one ADT can have different implementations
2.3.8. Implement data structures in arrays
2.3.9. Implement data structures with pointers
2.3.10. Understand advantages of encapsulation and hiding implementation details
2.3.11. Indentify the main container classes typically implemented by data structure libraries

1. Identify the key manipulations (initialize, sort, search, transform) on containers
2. Identify the iterators and ways to visit each element in a container for custom processing

2.3.12. Understand representation invariants (rep invariants)

1. Understand the representational exposure
2. Use defensive copying, proper get/set methods, verbal contract with client classes to avoid exposure

2.3.13. Use STL to initialize vectors, stacks and maps
2.3.14. Use C++ constructs to iterate over data structures
2.4 Define OO design patterns in C++ Description The module only lists those design patterns that are typically used with data structures. One can certainly write good code without using “Gang of Four” jargon, but it can explain the thinking behind some popular APIs and data structure libraries.
(Goodrich2011)Ch02P01: OO Goals, Principles and Patterns (Goodrich2011)Ch05P03: Deques: Adapter Design Pattern (Goodrich2011)Ch07P03: Binary Trees: Template Method Pattern (Goodrich2011)Ch11P04: Sets: Template Method Pattern
2.4.1. Describe the tradeoffs between top-down and bottom-up design
2.4.2. Define the singleton OO design pattern
2.4.3. Define the factory OO design pattern
2.4.4. Define the composite OO design pattern
2.4.5. Define the template method OO design pattern
2.4.6. Use virtual functions in C++ also in factory or template method patterns
2.5 Test and debug algorithms in C++ Description The module explains general techniques to do unit testing and system testing, code inspection, printouts, logging and debugging in order to find bugs in algorithmic software.
(Goodrich2011)Ch01P07: Writing a C++ Program (Goodrich2011)Ch04P03: Loop Invariants
2.5.1. Identify the reasons why software can contain errors
2.5.2. Write reasonably complete set of testcases.
2.5.3. Enforce invariants and Hoare logic to your data structure manipulations
2.5.4. Use printouts and/or efficient logging
2.5.5. Analyze runtime behavior using breakpoints.

3 Analyze the implementations of some data structures.

3.1 Construct and manipulate list-like data structures Description Define list and also vector (a.k.a. arraylist) allowing random access. In this and subsequent modules we start with the ADT we want, then show some ways to implement it.
(Goodrich2011)Ch03P01: Using Arrays (Goodrich2011)Ch03P02: Using Singly Linked Lists (Goodrich2011)Ch03P03: Using Doubly Linked Lists (Goodrich2011)Ch05P01: Stacks (Goodrich2011)Ch05P02: Queues (Goodrich2011)Ch05P03: Doubly-Ended Queues (Goodrich2011)Ch06P01: Vectors (Goodrich2011)Ch06P02: Lists (Goodrich2011)Ch06P03: Sequences
3.1.1. Define list and vector ADTs
3.1.2. Define an iterator ADT
3.1.3. Implement list as a singly linked list
3.1.4. Implement list as a doubly linked list
3.1.5. Implement vector as an extendable array
3.1.6. Implement vector as an extendable cicular array

3.2 Construct and traverse tree-like data structures Description Trees in this course are always assumed to be rooted (one node is root) and ordered (we always know, which is the 1st, 2nd etc. child of the same parent). This module only deals with trees in the most general sense (to store certain hierarchies). Trees with additional structural requirements (with keys ordered for fast search and/or balanced) are called search trees; they will be discussed later.
(Goodrich2011)Ch07P01: General Trees (Goodrich2011)Ch07P02: Tree Traversal Algorithms
3.2.1. Define graph-theoretic concepts: root, internal nodes, leaves, children, parent, siblings.
3.2.2. Define path-related concepts in trees
3.2.3. Define full, complete and perfect n-ary trees.
3.2.4. Define tree ADT
3.2.5. Parse algebraic expressions and convert them to trees
3.2.6. Evaluate algebraic expression trees using stack data structure
3.2.7. Implement trees with two-way pointers
3.2.8. Implement (preferably, complete) trees with arrays
3.2.9. Representing a rooted n-ary tree as a binary tree.

3.3 Construct and manipulate priority queues and heaps Description Unlike more universal structures (binary search trees or hashtables) the data structures may only need to return (or remove) the minimal or maximal element; in this case they are called priority queues. A typical way to implement them is a tree-like structure called a heap.
(Goodrich2011)Ch08P01: The Priority Queue ADT (Goodrich2011)Ch08P02: Implementing a Priority Queue with a List (Goodrich2011)Ch08P03: Heaps
3.3.1. Priority queue ADT
3.3.2. Analyze priority queue implementation as a regular binomial heap
3.3.3. Analyze skew binomial heap implementation
3.3.4. Analyze leftist binomial heap implementation
3.3.5. Analyze Huffman algorithm to compress a sequence of independent messages

3.4 Construct and manipulate maps and dictionaries Description Finding values by non-integer keys (typically strings) defines the difference between maps and lists. Dictionaries are a variant of maps allowing repeated keys. In this module the ADTs are defined and also their implementations
(Goodrich2011)Ch09P01: Maps (Goodrich2011)Ch09P02: Hash Tables (Goodrich2011)Ch09P03: Ordered Maps (Goodrich2011)Ch09P04: Skip Lists
3.4.1. Define map ADT
3.4.2. Define a hashtable and a corresponding hash function

1. Describe a hash collision and hash tables with chaining
2. Growing and shrinking hash tables
3. Analyze worst-case and amortized operation complexity in hashtables

3.4.3. Define a rolling hash ADT (append, skip)
3.4.4. Analyze Rabin-Karp algorithm
3.4.5. Implement map as a doubly-linked list
3.4.6. Implement skiplists
3.4.7. Adjust data structures for dictionaries with repetitive keys

3.5 Construct and manipulate BST structures Description Binary Search Trees is one possible way to store maps with totally ordered keys. This is an overview chapter that shows the general principles how the search trees can be built and manipulated. Inserting nodes in certain patterns can lead to skinny and inefficient trees; so they need some balancing.
(Goodrich2011)Ch10P01: Binary Search Trees (Goodrich2011)Ch10P02: AVL Trees (Goodrich2011)Ch10P03: Splay Trees (Goodrich2011)Ch10P04: 2-4 Trees
3.5.1. Define BST operations as ADT.
3.5.2. Run node search, insert and delete in an abstract BST
3.5.3. Implement node search, insert and delete in pointer implementation.
3.5.4. Implement node search, insert and delete in array implementation
3.5.5. Implement tree balancing as AVL tree
3.5.6. Implement tree balancing as red-black tree
3.5.7. Implement balancing as splay tree
3.5.8. Introduce (a,b)-search-trees and (2,4)-trees in particular
3.6 Analyze and compare sorting algorithms Description This chapter describes general-purpose sorting algorithms (sorting also appears in STL module and as an illustration to various algorithm paradigms in later modules).
(Goodrich2011)Ch11P01: Merge-Sort (Goodrich2011)Ch11P02: Quick-Sort (Goodrich2011)Ch11P03: Sorting through an Algorithmic Lens
3.6.1. Analyze insertion sort and bubble sort
3.6.2. Analyze merge sort algorithm
3.6.3. Analyze quicksort algorithm
3.6.4. Analyze heapsort algorithm

3.7 Construct and manipulate set-like structures Description This module explains ways to represent sets and also bags (allowing repetition of elements); their order relations and set-level operations. Element-level operations on sets were explained earlier – in fact, maps and dictionaries can be used for that.
(Goodrich2011)Ch11P04: Sets and Union/Find Structures
3.7.1. Revisit generalized container ADTs that are used to represent (unordered) sets.
3.7.2. Introduce additional operations in ordered sets.
3.7.3. Revisit iterator ADTs in set-like data structures.

1. Analyze set-level operations (union, difference, etc.) in the list implementation.
2. Analyze set-level operations in the hashtable implementation
3. Analyze set-level operations in tree implementations.

3.7.4. Analyze some algorithms for the selection problem (identifying the n-th element)
3.8 Describe graph and directed graph structures and traversals Description The module explains the most complex data structures covered in this course (undirected and directed graphs); their ADT and some general tasks associated with graphs (such as BFS and DFS traversal). Any weighted graph issues are postponed.
(Goodrich2011)Ch13P01: Graphs (Goodrich2011)Ch13P02: Data Structures for Graphs (Goodrich2011)Ch13P03: Graph Traversals (Goodrich2011)Ch13P04: Directed Graphs
3.8.1. Revisit graph concepts: undirected vs. directed, simple graphs vs. multigraphs, degrees, indegrees, outdegrees; their input via matrices and adjacency lists.
3.8.2. Introduce graph ADTs, their iterators, accessor and update methods.
3.8.3. Describe alternatives of graph input, output and storage.
3.8.4. Describe the BFS traversal algorithm template
3.8.5. Describe the DFS traversal algorithm flavors.

1. Use the DFS traversal to analyze mazes
2. Use the DFS traversal to find paths and cycles in a graph.

3.9 Analyze Shortest Paths and MST algorithms Description Various general algorithmic ideas can be illustrated on weighted graph optimization problems. This module analyzes source-to-sink (or all-pairs) shortest paths and also the minimum spanning tree (MST) algorithms.
(Goodrich2011)Ch13P05: Shortest Paths (Goodrich2011)Ch13P06: Minimum Spanning Trees
3.9.1. Introduce the weighted graph framework and input data
3.9.2. Analyze Dijkstra’s algorithm
3.9.3. Analyze Bellman-Ford algorithm (and negative edge weights)
3.9.4. Analyze Kruskal’s algorithm
3.9.5. Analyze Prim’s algorithm
3.9.6. Analyze Boruvka’s algorithm

4 Introduce general paradigms for algorithms.

4.1 Describe types of algorithmic problems and overview their algorithms Description The last module provides a high-level overview of some large classes of algorithmic problems; what algorithms were covered in each one of them and what paradigms were used.
(Goodrich2011)Ch12P03: Pattern Matching Algorithms
4.1.1. Describe searching and sorting problems
4.1.2. Describe string processing problems
4.1.3. Describe some examples of graph problems
4.1.4. Describe some examples of combinatorial problems
4.1.5. Describe some examples of geometric problems
4.1.6. Describe some examples of numerical problems
4.2 Describe exhaustive, brute-force paradigms Description Introduce algorithms that split the problem into subcases and then verify subcases in some order
(Goodrich2011)Ch12P03: Pattern Matching Algorithms
4.2.1. Define exhaustive search paradigm
4.2.2. Describe tactics to generate combinations
4.2.3. Describe examples of “naive” search algorithms
4.2.4. Describe examples of “naive” string matching algorithms
4.3 Describe decrease and conquer paradigm Description Algorithm can reduce a problem to a simpler one. We discuss paradigms to solve a problem by stepwise reducing it to a simpler one.
(Goodrich2011)Ch13P04: Directed Graphs
4.3.1. Describe decrease and conquer paradigm
4.3.2. Revisit insertion sort algorithm
4.3.3. Analyze topological sorting algorithm
4.3.4. Generate permutations or subsets of a given set
4.3.5. Discuss heap implementations in terms of decrease and conquer.

4.4 Describe divide and conquer paradigm Description Many algorithmic problems can be solved or “conquered” by subdividing them in parts
(Goodrich2011)Ch11P01: Merge-Sort
4.4.1. Describe divide and conquer paradigm
4.4.2. Revisit mergesort and quicksort
4.4.3. Revisit BSTs
4.4.4. Analyze recurrence equations, apply Master method

1. Run Karatsuba’s fast multiplication
2. Run Strassen’s fast matrix multiplication

4.5 Describe dynamic programming paradigm Description Data structure manipulations are often a means to an end. Here we list some application areas that often lead to data structures; and this will help to introduce different algorithm creation paradigms – very general ideas that are behind the algorithm development.
(Goodrich2011)Ch12P02: Dynamic Programming
4.5.1. Describe dynamic programming paradigm
4.5.2. Revisit shortest paths problems
4.5.3. Analyze optimal matrix multiplication problem
4.5.4. Analyze longest common subsequence algorithm
4.6 Describe greedy paradigm Description Some algorithms searching for the optimal (cheapest, fastest, etc.) way to complete the task follow the following rule: At every step select the “locally best” alternative and it will eventually lead to the globally best solution. This approach is usually efficient, but for many problem classes this could give a solution that is not the best possible.
(Goodrich2011)Ch12P04: Text Compression and the Greedy Method
4.6.1. Revisit Prim’s algorithm
4.6.2. Revisit Kruskal’s algorithm
4.6.3. Revisit Huffman’s algorithm