For those new to it, SQL can be difficult initially to wrap your head around. One of the reasons is because it requires a different type of thinking from other languages like Java, Python, or C. You have to learn to think in sets (remember all those Venn diagrams from various places throughout school?). [Read more…]
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
- Cliff Shaffer’s PDF Book Section 13.2.1
- AVL Trees at Tutorials Point
- AVL Tree Animation – let’s you see the operation of inserting, searching, and deleting in real time.
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:
- Shaffer’s book, Data Structures and Algorithm Analysis, 2013 edition.
- See chapter 4, page 95 – 148
- Linked List Notes from CMU
- Linked Data Structures Lecture Notes from UTK
There are plenty of videos on Youtube about these topics as well. Check them out.
C++ and Catch – Adding your Own Main Method
When you begin coding on a project, it is perfectly acceptable and even advisable to allow the Catch library to generate the main method for you. That is what the #define CATCH_CONFIG_MAIN (very first line in the tests.cpp file) directive tells Catch to do.
As you transition from implementing the data structures to implementing a higher-level project, you will want to eventually create your own main method. Here is how to transition to using your own main without getting rid of tests and testing.
In QtCreator, follow these steps
- Add a new cpp file to your project that will contain your main driver. If you still have the original main.cpp that was added when you created the project, that is fine to use as well; make sure it is listed in the project explorer on the left side of the code window.
- Comment out#define CATCH_CONFIG_MAIN at the top of the tests.cpp file. This will tell the Catch library NOT to generate its own main method.
- In your main driver file, copy and paste the following code (to start with). Read the comments throughout to help you understand what is going on.
//CATCH_CONFIG_RUNNER tells the catch library that this //project will now explicitly call for the tests to be run. #define CATCH_CONFIG_RUNNER #include "catch.hpp" //A macro used in main to determine if you want to run //the tests or not. If you don't want to run your tests, //change true to false in the line below. #define TEST true /* * runCatchTests will cause Catch to go ahead and * run your tests (that are contained in the tests.cpp file. * to do that, it needs access to the command line * args - argc and argv. It returns an integer that * ultimately gets passed back up to the operating system. * See the if statement at the top of main for * a better overview. */ int runCatchTests(int argc, char* const argv[]) { //This line of code causes the Catch library to //run the tests in the project. return Catch::Session().run(argc, argv); } int main( int argc, char* const argv[] ) { //If the TEST macro is defined to be true, //runCatchTests will be called and immediately //return causing the program to terminate. Change TEST //to false in the macro def at the top of this file //to skip tests and run the rest of your code. if (TEST) { return runCatchTests(argc, argv); } //start working on other parts of your project here. return 0; }
Once you’ve added that code, rebuild your project (Build menu| Rebuild All) then execute your project. Your tests should run as normal.
The Relational Model
As we being our foray into the world of database systems, our first stop is at the Relational Model of Data. In the relational model, some of the basic components are tuples, relations, and relationships. It was originally developed and proposed in the late 60’s by E. F. Codd. Perhaps one of the most influential papers related to the relational model is Codd’s “A Relational Model of Data for Large Shared Data Banks“.
Here are some of the topics we will cover right now [Read more…]
Command Line Args in C++
As you’re already familiar with, when you call some functions, you need to pass arguments to them. So, what about main? There are two different function headers for he main method in C++ that we can use:
int main (); //header 1
and
int main(int argc, char* argv[]); //header 2
Now, you should ask yourself, “What’s the difference?” Remember that when you execute a program (either from the command line or by double-clicking on an icon or something similar), you’re really asking the OS to load the executable and begin execution. When the OS is starting your program, you can use command line arguments to send arguments into the main method. Consider this program execution:
./myFunGame input.txt output.txt
Data Structures Intro
The first few weeks of the semester, we’ll take a deep(er) dive into pointers and dynamic memory management using C++. To get started, I wanted to provide you some links to useful information.
- Stackoverflow.com – A treasure trove of software development and programming Q&A. Very often, if you google an error message, you’ll see links to Stackoverflow.
- CPP Reference – a fantastic reference site
- learncpp.com – some good tutorials; great for a review of topics you may be rusty on.
- cplusplus.com – great reference material
- Cliff Shaffer’s Data Structures Book – This is what we’ll be using (for the most part) in class.
Regarding our first topic, pointers and memory management, here are some links to some other blog posts I did over the summer that might be helpful:
- Pointers (check out the video links at the bottom)
- Memory Management (again – check out the video links)
It’s Not Nice to Point… But Really, It’s OK.
Pointers are really important to the C and C++ language. They are actually really important in many different languages whether or not you have direct access to manipulate them. In our on-line gathering yesterday evening, I introduced you to the basic concepts of pointers and memory layout, well – at least how C++ sees it.
It’s time to read Section 6.3 of Overland (skip 6.3.7, 6.3.8 and 6.3.9). Also read Section 6.4, but stop before the paragraph that starts with “This analysis—what would the item imply…”. From that point down is about function pointers which should be in its own sub section. But in any event, you don’t need to worry about these.
Here are a couple videos that might also be useful to you that I made a few semesters ago: Video 1, Video 2.
Reading sections 10.1, 10.2, and 10.3 of Overland related to c-strings could be helpful if you need more info there.
Design before Coding
In the “real world”, it is a rare occurrence that a developer encounters a problem and starts to solve that problem with a blank project. Often times, a dev is working as part of a much larger contingent of folks on a much more massive software project. It doesn’t really make sense that you’d just walk in to that space and start hacking away on code without first attempting, at least in some small way, to wrap your brain around [Read more…]