Gearing Up for Spring 22 Data Structures

Happy New Year!  I hope your winter break has been restful and relaxing!

I’ve gotten a few requests from folks about how to prepare for CS 2341.  So I thought I’d provide a list of things to review before class starts:

  • C++ Language
    • Pass by value vs pass by reference vs pass by pointer
    • Pointers and dynamic memory allocation
    • How to declare classes and their main methods (constructors, destructors, etc)
    • Operator overloading in a class
    • Object composition 
    • Did I mention Pointers?  
      • How to declare a pointer?
      • How to dynamically allocate memory on the heap?
      • How to dynamically allocate an array of pointers? 
      • the & operator and the * operator
    • How to separate interface from implementation 
    • reading and writing files and parsing data 
  • Conceptual Things
    • How to break a problem down into bite-sized chunks. 
    • The idea that a function should do one thing and it should only do that one thing
    • Developing algorithmic solution to basic problems involving a simple 1D array
      • make use of control structures like ifs and loops
      • example: Find the 2nd smallest value in an array with only 1 loop. 
    • The conceptual relationship between pointers and arrays.
    • How to use a debugger

Perhaps the thing that is the biggest curve ball to students in 2341 is the scope and scale of the programming projects.  They will be much larger than you’ve encountered in previous classes.  This is intentional.  Learning to take a really large project description and break it down into manageable pieces (said another way: how to functionally decompose a problem) is as important of a skill to develop as actually being able to write the code to solve one of those pieces. 

 

What are the gcc system include paths?

The #include preprocessor directive in c++ is one of the first things that people learn. They come in two varieties:

  1. #include<> – usually meant for system-level includes such as iostream or other headers from libraries installed at the system level.
  2. #include " " – usually meant for files included from a location relative to the code being written… for instance, another header file for a class you just wrote.

But, where are system level headers stored?  On Linux with the gcc tool chain installed, you can execute the following command to find out:

g++ -E -x c++ - -v < /dev/null

  • -E – Stop after the pre-processing step
  • -x c++ – language of interest is c++
  • -v – verbose output

In the output, look for the section that starts with #include <...> search starts here.  A collection of paths is listed after this line which is where the pre-processor will look for any includes that are in <...> (angle brackets).

FWIW, there’s also a way to include additional paths to be used as system includes on the command line when compiling code.

Customizing CLion

Clion LogoSome folks get a lot of enjoyment out of tweaking the UI of a piece of software.  In an IDE like CLion, the color scheme used for the code editor is highly customizable.  If you’d like to explore the settings and/or find a new theme for CLion or just the code editor, check out the CLion JetBrains tutorial at https://www.jetbrains.com/help/clion. Specifically, here are some tutorials you might want to look at:

Linux, C++, and Libraries like myHTML

Whenever you write c++ code for a project, have you ever wondered where the actual implementations for iostream’s << and >> operators are?  What about the implementations for all of the algorithms that are in the algorithm header? Whenever you’re building a project and linking in things from external libraries, where’s the compiled version of those functions?  The secret is in libraries of code external to your project. [Read more…]

Testing More than One Thing with Catch

In a modern piece of software, you wouldn’t have tests for just one class.  You’d have exhaustive tests for all the functionality in your program.  However, it would be challenging to put all of the tests in one single tests.cpp file.   [Read more…]

Spring 2018 Data Structures Prep

It is no secret that CSE 2341 – Data Structures – is a very demanding course.   The course requires a great deal of dedication and perseverance.  I have received a few requests about what to do over winter break in terms of review and prep.  This blog post has some suggestions and links to possibly useful info.

[Read more…]

Binary Trees and Binary Search Trees

Trees are a very important data structure, especially binary trees and its variants.  Please watch the videos linked below to get up to speed on Trees, Binary Trees, Binary Search Trees.

 

B+ Trees

B+ Trees are very efficient search tree data structures that are related to binary search trees.  They are particularly useful in indexing situations where the entire data set cannot fit into main memory at one time.  Each node in a B+ Tree contains multiple keys and pointers (as compared to 1 key and two pointers in a binary search tree).   [Read more…]

Binary Trees

Binary trees are a very fundamental data structure in computer science.  As you continue to learn and explore in different sub-domains of CS, you’ll see them pop up quite frequently.  Here are some things you should Binary Trees and their cousins.

  • General Binary Trees
    • Pre -, In -, and Post-order traversals
    • The height (or depth) of a tree
    • Different node terminology (leaf, level, ancestor, descendant, etc.)
    • Some info to peruse
  • Binary Search Trees
    • Remember, binary search trees are binary trees that also conform to the binary search property: all values in the left subtree of a node are smaller and all values in the right subtree of a node are larger (duplicates not withstanding)
    • Some algorithms you should think about w.r.t. bin search trees:
      • inserting a new value
      • searching for a value
      • deleting a value from the tree
      • determining the height of the tree
      • determining if a binary tree is indeed a binary search tree
      • what’s the most efficient way to create a copy of a binary search tree?
      • what’s the best way to destroy (delete all nodes) a binary search tree?
    • Some info to peruse
      • David Eck link above
      • Cliff Shaffer’s Data Structures and Algorithms book linked above Section 5.4 starting on page 168.
  • AVL Tree – a Self Balancing Binary Search Tree
    • AVL Balance Property: for every node n in an AVL tree, the height of the left subtree and the height of the right subtree may differ by no more than 1.
    • Some info to peruse

Lists, Stacks, and Queues

Lists, stacks, and queues are some of the most fundamental data structures to computer science.  Below are some links to information you may find helpful as you explore these data structures:

There are plenty of videos on Youtube about these topics as well. Check them out.