Dear class,

I will take some notes during the comp 15 lectures to help you.  Please continue to take notes during class.  I will try to provide other interesting examples I find on the internet and add them here.  Please do not redistribute these notes, but feel free to use them to help you with the course.

Table of Contents

Notes for topics to cover (based on office hours)

Operator Overloading 6/9/13

Header file organization 6/9/13

Matrix Multiplication 6/10/13

General Notes

Introduction                         (Class 1 - 5/22/13)

Introduction to C++                 (Class 2 - 5/29/13)

Abstract Data Types                 (Class 3 and 5 - 6/3/13)

C++ Object Orientation Notes         (Class 5 6/10/13)

Dynamic Memory Allocation                                

Linked Lists                                (Class 5 6/10/13)

Stacks

Queues

Recursion

Sorting

Algorithm Complexity

Advanced C++ (Templates)

Binary Search Trees

Balanced Trees

Splay Trees

Graphs

Advanced Sorting Algorithms

Heaps

Union Find Algorithm

Review Questions (link to comp 15 post)

Appendix

Glossary of Terms

Unix Commands

Emacs

Provide System (Submitting your assignments!)

Computer Architecture

Common Errors

C++ Keywords and one-sentence meanings


Operator Overloading [Jump to Table of Contents]

Stack Overflow Resource

Copy Constructor

        Resources/Background Reading [wiki]

Header file organization [Jump to Table of Contents]

[Resource with some nice diagrams]

[Another resource explaining concepts]

So there is some confusion what exactly on what the difference is between a header(.h) and a c plus plus file(.cpp).  So lets debunk a few of the common questions:

  1. What is a header file
  2. What goes in a header file
  3. In what order are files compiled?
  4. How do I include files correctly
  5. What are some best practices with header files?

What is a header file

        When you include a header file, it verbatim copies that file with declarations into your source code.  So generally a header file contains the skeleton of a class, i.e. what will be in the class but not the actual algorithms that make each function work.

What goes in a header file

In what order are files compiled

        

How do I include files correctly

What are some best practices with header files

 


Matrix Multiplication  [Jump to Table of Contents]

Example: http://www.mathwarehouse.com/algebra/matrix/multiply-matrix.php


Introduction  [Jump to Table of Contents]

(May 22, 2013)

Data Structures:

        Goal: Given a problem, how do we solve it efficiently?

What we want to do as computer scientists is automate the process of solving specific problems.

Problem Solving Steps

        1.) Generate an initial naive solution.  Do this to validate your correctness.

        2.) Refine your initial solution(if possible).

                1.) Efficiency (Time and Space)

                2.) Algorithm Design (Number of Steps)

                3.) Data Structure Design (Organization of Data)

Exercises

Exercise 1: How would you find the maximum number from a given list of integers that are arranged in a random order(Example: {5,3,2,5,7,12,0} )

Exercise 2: Find the max and min of n integers.

        Hints:

        Questions to ask yourself: How many comparisons do you have to make to find just the max or just the min?

        Can we think of the max and min as “defeating” the other numbers in a tournament?

        Can you avoid checking if certain numbers are a min or max more than once? (How can we minimize the set of winners or losers in our set when checking if they “win” or “lose” as a min or max.

Exercise 3: Find the max and second max of n integers.


Introduction to C++  [Jump to Table of Contents]

(May 29, 2013)

History of C++ [link]

C++ Reference [link]

C++ Tutorials [link]

Our Goal:

C is a proper subset of C++, and we would like to learn several of the features of C++ that can help us more conveniently create software.  By leveraging some of the features of C++, we will better be able to build data structures that can help us.

The Language

C++ adds features onto C which makes it more powerful(One of the main feature sets is the object-orientation-- we will learn what objects are in a future section in these notes.)  

Our first program

#include <iostream>

int main()

{

        std::cout << “My first program!” << std::endl;

        return 0;

}

Exercise 1: Type the above code into emacs (or your editor of choice), compile it, and then run it.

Breaking the program down:

        #include <iostream> - We are telling the compiler(The compiler being the program ‘gcc’) that we will be loading functions from <iostream>

int main() - Every program consists of a main function that tells us where we start

{ and } - The brackets break our code into blocks of code that are executed.  They help the compiler understand what the scope(scope meaning, what is the range that some statement should execute) is of our program.

std::cout - The preceding ‘std’ means that we are loading a function from our library ‘std’.  The ‘cout’ is a function that tells us we are going to be outputting some information to the terminal.

return - Every function needs a return, so

Variables

        A variable is some value that has a corresponding memory location.

        In C++ when a variable is declared, it is best if you can assign it a value.

        Why is this a best practice?

[example - for loops]

                        [why is this important? Reduces spilling in register allocator in the compiler.  We only have a limited number of registers on our processor, and we like to use them because they are fast!  If we don’t use registers, then we have to use the cache, or even worse, the disk!]

Pointers 

[Tutorials]

[Another excellent in-depth explanation]

        int* v - This means that “v is a pointer to int”

        v = &value;  The ampersand means that we are extracting a value.  When we use the ampersand we are dereferencing the value.

Functions

Type the following code into your editor and try to predict the result.

        int main()

{

        int x,y;

        x = 5;

        y = 6;

        swap(x,y);

        std::cout << “x=” << x;

        std::cout << “y=” << y;

        return 0;

}

void swap(int a, int b)

{

        int t = a;

        a = b;

        b = t;

}        

Question 1: What is call by value?

Question 2: What is call by value result?

        Question 3: What is call by reference?

See “the heap and the stack” discussion in Computer Architecture to gain some intuition about how values can and cannot be modified.

Arrays

        Single dimensional array: int A[50];

        Multi-dimensional array: int B[5][4];

Allocation of an array is always contiguous.  They are indexed starting from 0.  So if we declare an array of size 50, then we acces it from 0 to 49. Example: A[0], A[34], A[49].

        Exercise: What happens when we try to access A[50] or A[-1].

        Exercise: How do you think arrays are structured?

                        If we know this structure, can we access the array in a different way? (hint: memory in an array is allocated contiguously in arrays) Solution

        Some more examples from class:

example 1:

                int A[10]

                A -> & A[0];

                *(A+1) -> A[1]

        example 2:

                int A[5][4];

                A -> &A[0][0]

                A+1 -> &A[1]

                *(A+3) -> &A[1][0]

                *(A+1)+3 -> &A[1][3]

                *(*(A+1)+3) -> A[1][3]

        Confused? Try creating a single and multi-dimensional array this in the compiler and see if you get the same value.

Assignment

Save yourself some headaches when checking with variables.

        Example: Use if(7==c) as opposed to (c==7) Why? Because if we forget to put both =’s, then the compiler will not complain in the second example(c=7).

Lab Exercise

Create a directory: “mkdir lab0”

Go to that directory: “cd lab0”

Problem: Compute the roots of quadratic equation:

Divide into 2 functions:

        (i) Read Inputs()

        (ii) Compute Roots()

(1) Print whether

        (i) Roots are equal

        (ii) Roots are complex

        (iii) Roots are distinct real

(2) Print out the roots

Control Flow

        


Abstract Data Types  [Jump to Table of Contents]

Class 3 - 6/3/13

I was not at this class, but I want to add some notes on a few of the subjects that were discussed just to have a different perspective.


Examples from Professor:
http://www.cs.tufts.edu/comp/15/files/examples/ADTs/

Abstract data types allow us to build new abstractions of our own using the primitive data types that C++ provides.  These primitive or fundamental data types that are given to us can be found on this page in a nice table.

As you will notice from the table, C++ provides us with some data types like int, float, boolean, and it even gives us some functionality to convert these data types.  For example, C++ can figure out how to convert a Boolean to an integer for us.

However, in the programs we create, we may want to do create our own data types representing abstractions beyond numbers such as: vectors, matrices, shapes, vehicles, cars, planets, the universe!

In order to do this, C++ provides us a way to create these abstractions.

1.) structs

2.) classes (The primary way you will create your new data types)

(optional) classes versus structs (keep this in mind for later)

C++ Object Orientation Notes [Jump to Table of Contents]

What is an object?

Exercise:

What is the difference between a struct and a class in C++?

struct someStruct {

        int data1;

        int data2;

}

class someClass{

        int data1;

        int data2;

}

Hint: Think about data encapsulation!

Answer: structs by default have all members public and classes have by default all members private.

Exercise: Would these two items be equivalent?

struct someStruct {

private:

int data1;

int data2;

};

class someClass {

    int data1;

    int data2;

};

Answer: Yes! So why use a struct over a class? Sometimes it is for clarity or structs are used without any members.  The reason structs exist in C++ is to maintain compatibility with C code. Link to more information

Data Hiding

        Interface between my code and my partner’s code should be simple!

        [protection] 1.) Prevents my data from becoming corrupted

        [flexibility] 2.) Improve my implementation without affecting my clients.

What is inheritance? (See your handout on Inheritance in C++)



Dynamic Memory Allocation [Jump to Table of Contents]

Contents

        Discussion

        Examples

        Exercises

Examples from Professor: http://www.cs.tufts.edu/comp/15/files/examples/dynamic_allocation/

(Full Section is a work in progress as of 6/9/13)

Discussion

Static Memory Allocation Concept

In order to understand dynamic memory allocation, let us also make sure we understand static memory allocation first.  Static memory allocation is something that we do at compile-time.  This means, that when we compile our program(using the gcc or g++ command), we can figure out exactly how much static memory our program means.

        An example: int a = 5;

        The compiler figures out at compile-time (so before the program executes), that we are requesting enough memory to store an integer value.

        Another example: int a[40];

        This time, the compiler has figured out that we need to request enough memory before the program runs so that we can have space to store 40 integers.

To understand the exact structure of a program, we need to know a little bit about the operating system itself.  Once we know about the operating system, we can figure out how it organizes programs.  Once we know about programs, we can look at how the memory is organized, and how the compiler statically and dynamically creates memory.

Okay, so step 1, looking at the operating system at a very high level (the forty-thousand foot view if you will).  The operating systems (OS) job is no different than traffic light.  Its job is to make sure some things get a chance to run, some things are paused, no one is crashing, and ultimately that things are moving along as fast as possible!  

So lets make sure this analogy is concrete.  The traffic light is your operating system.  At the end of the day, the traffic light has finite resources and all it cares about is getting lots of cars through as fast as possible**.  The roads are your hardware with limited “bandwith”, i.e. how much traffic can you handle.  Each car represents a program.  Within each car sits a human who has a memory of their own.  Humans have short term memory and long term memory.  Lets think of static memory as long term memory(something that needs to last a long time) and dynamic memory as a humans short term memory(items that are important for a little while, but can be deleted from our minds.)

**(Operating systems are all about speed! There are active debates on who is responsible for security--should it be the hardware, the OS, each individual software, some other online DRM, etc.)

Okay, so we have some analogy we can build off of, but I want you to take a minute and think about your computer architecture.  One of the really neat things about C and C++ is that it is really close to the physical machine level.  That is, we are interacting with our machine very closely, and having an understand of the hardware can help us make design choices that directly impact our code.  

Exercise: So as an exercise, list all of the static and dynamic memory sources on your computer.  (Also for fun, think about ourselves(human beings) and the dynamic and static memory we have.)

        Dynamic sources:

1.) RAM (Random access memory, it’s cleared every time you power down)

        Static sources: Your hard drive (The memory stays forever!)

So working our way back, static memory is the memory that will stay forever in a persons long term memory.  The dynamic memory may come or go, and is equivalent to our short term memory.  And remember, we are all people, sitting in cars.

Ah, so remember that the car is the program in this analogy.  Each program is allocated

Examples

        1.) Allocating a static array.

        The general format: Datatype name_of_array left_bracket size right_bracket

        Concrete examples:

                int A[20];

                float B[25];

                char some_text[] = {‘h’,’i’,’!’,’\0’ };

                                

Exercises

        1.) What are the disadvantages of using arrays (Example: int A[7] = {1,2,3,4,5,6,7}; ) for storing a list of data?

                Answer: Inserting an element in the middle or in the beginning is hard.

                Why: Imagine in our above array ‘A’ that we need to insert the item 8 in the middle.  Then we need to shift every element over, and we’d have to allocate a new array.  This leads to our second disadvantage below.

                Arrays have a fixed size, i.e. A[7] holds and will forever hold 7 items as a maximum (And what if we only want to store 2 items? We’ve just wasted space!).


Linked Lists  [Jump to Table of Contents]

Contents

[Excellent Resource]

Discussion

Examples

Exercises

Discussion

Examples

Source code example from class

class LLNode{

        int mItem;        // Remember by default this information is private in a class

        LLNode* mNext;

public:

// Here are our constructors

LLNode(int mItem, LLNode aNext): mItem(nItem),mNext(aNext) {}

LLNode(int nItem) : mItem(aItem),mNext(NULL) {}

// Here are our ‘getters’

        int getItem() const { return mItem;}        // Note that we put const at the end because this item is read-only.  Many compilers may make this optimization for you, but you should add it in as a best practice.

        LLNode* getNext() { return mNext; }

// Here are our ‘setters’

        void setItem(int aItem) { mItem = aItem; }

        void setNext(LLNode* aNext) { mNext = aNext }

}

// Usage of our class

LLNode L1 = new LLNode();

        L1-> setItem(10);

LLNode L2 = new LLNode();

        L2 -> setItem(20);

LLNode L3 = new LLNode();

        L3 -> setItem(30);

                L1->setNext(L2);

                L2->setNext(L3);

                L3->setNext(NULL);        // Ask yourself, why is this null?

                                        // Try drawing a picture of what this looks like.

Inserting into a linked list

LLNode::insertAfter(int aItem)

{

        // note that mNext here is the old value that we have, so we are adding this to the tail of our linked list.

        mNext = new LLNode(aItem, mNext);

}

Usage

        L2 -> insertAfter(50);

        // Our list should now have the numbers 10,20,50,30

        // So keep in mind that the data of L2 does not change, it’s only the pointer that changes for L2, in that it now points to a new node.

Creating our first linked list

class LL{

        LLNode* mHead;

        int mSize;

        public:

        LL() { mHead = NULL; mSize = 0;}

        int length() const { return mSize; }

        void insertFront(A &mItem){

                mHead = LLNode(aItem, mHead);

                mSize++;

}

};

LL::deleteFront(){

        if(mhead != NULL){

                LLNode* temp = mHead;

                mHead = mHead->getNext();

                delete(temp);

                mSize--;

}

}

invariants:

1.) mSize is always correct

        2.) My list does not have a cycle.

What does a doubly-linked list look like?

// note that ‘A’ means any data type in these notes

class DLL {

        A mItem;

        DLLNode* mNext;

        DLLNode* mPrev;

};

Sentinel Node in linked list:

What is the advantage: No need for tail pointer (i.e. the sentinel node is a way to simplify your implementation of a linked list).

Exercises

        1.) What are the advantages of using a linked list over an array?

        2.) What is the runtime of a linked list?

        3.) What is a singly linked list? What is a doubly linked list? What are the advantages of using one over the other? What about a cyclic linked list?

        3.) What are the runtimes of the following operations

Lookup an item at an index

Insert an item

Linked List

O(n)

O(1)

Array

O(1)


Stacks  [Jump to Table of Contents]


Queues  [Jump to Table of Contents]


Recursion  [Jump to Table of Contents]


Sorting [Jump to Table of Contents]


Algorithm Complexity  [Jump to Table of Contents]


Advanced C++ (Templates)  [Jump to Table of Contents]


Binary Search Trees  [Jump to Table of Contents]


Balanced Trees  [Jump to Table of Contents]


Splay Trees  [Jump to Table of Contents]


Graphs  [Jump to Table of Contents]


Advanced Sorting Algorithms  [Jump to Table of Contents]


Heaps  [Jump to Table of Contents]


Union Find Algorithm  [Jump to Table of Contents]



Review Questions [Jump to Table of Contents]

1. What do you understand by a declaration, a definition, and an instantiation?

2. What are the four basic member functions of a C++ class that are defined by the compiler by default?

3. What does the default constructor do (when you don’t write one)? When would you need to redefine a constructor for a class?

4. What are the scenarios when a copy constructor is invoked?

5. How do you decide whether to pass an argument by a pointer or a reference?

6. When you are implementing an operator overloading, how do you decide whether you want it to be a member function or a non-member function?

7. Could you point out a flaw in the following class declaration?

class A {
public:
        void erase() { delete this; }
private:
        int data;
};

8. Discuss the different usages of const keyword in C++.

9. Why do you need the following wrapper around a class declaration in the header file?

#ifndef BLAHBLAH_H

#define BLAHBLAH_H

class …
#endif

10. When do you need to implement a destructor?


Appendix

Glossary of Terms [Jump to Table of Contents]

Unix Commands [Jump to Table of Contents]

Compiling Source:  type “g++ -o maxmax1 -g maxmax1.cpp

g++ the compiler we are using

-o build an object file

maxmax1 is the name of our executable file

-g build a debuggable program

maxmax1.cpp is the C++ source code file we are compiling

Debugging Source file

type: “gdb maxmax1”

Emacs [Jump to Table of Contents]

Escaping a program, press Ctrl+g

Ctrl+X+1 destroys split screen


Provide System [Jump to Table of Contents]

Contents

1.    Submitting your Assignment

2.    Viewing your Grades

1.    Submitting your Assignment

Throughout this semester you will be using the provide system to submit your assignments.  Provide itself is a computer program that takes your files and uploads them into a directory for your Professors and TA to grade.

The provide system runs on a Unix system, so all of your files that you submit must be on your Unix account.

The provide program works issuing the following commands through a terminal.

provide comp15 hw1 list_of_files

provide = the name of the program we are executing

comp15 = the course name in which we are submitting assignments for

hw1 = the assignment we want to submit

list_of_files = the program files and readme that we would like to submit.

        The list of files can be specified in a few different ways.  You can list all of the files out one by one.

Example if you have the files: main.cpp main.h my class.cpp class.h class2.h class2.cpp.  The provide syntax is as follows:

provide comp15 hw1 main.cpp main.h my class.cpp class.h class2.h class2.cpp

        If all of those files are in the same directory, then you can alternatively use the provide command as follows.

        

        provide comp15 hw1 *.*

        In the above, the asterisk (“*”) is a wildcard, that means, any combination of characters of any length can be put in this position.  Once another period is found however, it then finds another asterisk that says any combination of characters of any length can be put into this position.

        

        Note: You cannot provide a directory to provide.  You must provide individual files through the system.  It is however allowed to zip a bunch of files together, and then provide the single zip file.

        Example: provide comp15 hw1 myFiles.zip

        (In the above example, we put main.cpp, main.h, etc. into a zip file called myFiles.zip)

        

2.    Viewing your Grades

        

        In order to view your grades, you can use the “progress” command.

        Example: progress comp15

View grades for a specific assigment:

Example: progress comp15 hw2


Computer Architecture [Jump to Table of Contents]

Von Neumann Architecture [Brief Notes]

The heap and the Stack

        Link to resource - Describes how a programs memory is broken structured.

Common Errors [Jump to Table of Contents]

        1.) A constructor in the private part of your class will not be callable, it is useless.  Make sure it is public!

C++ Keywords and one-sentence meanings [Jump to Table of Contents]

const - Means “read-only”

        Example Usage:

volatile - Means some variable is modifiable by the program, operating system, or other running threads. (resource)

        Example: