COP3503.org

Programming Fundamentals 2 for CISE Majors

Introduction

• If you have an A going into the final you do not need to take it.
• Notify instructor ahead of time for test conflicts.
• We’re using C++
• C++ Programming in Emacs (http://www.cs.bu.edu/teaching/tool/emacs/programming/)

What is Computer Science?

• Underlying principles that allow for the design and implementation of computer solutions.
• Study of mathematical properties and underpinnings of computational processes.

Sorting Intro

A lot of different ways to sort objects or what we like to call data. These patterns work regardless of whatever is beung sorted.

• Words in a dictionary
• Numbers
• Cards
• Dates
• Times

Most important thing for sorting things is knowning the comparison.

Does one come before or after the other?

Insertion Sort

Keep the sorted part seperate from the unsorted. SET: 42 5 7 13 1 17 Take the 42 | 5 7 13 1 17 5 42 | 7 13 1 17 5 7 42 | 13 1 17

Skip to the 1, we’d have to move every number to the right to insert the one.

Worst case: Any number into position: n We would have to move n numbers n times so (n)^2

Quick Sort

Randomly choose a number to be our pivot SET: 42 5 7 13 1 17

Let’s choose pivot 13

Moves either to the left or right of the pivot as it moves through the list.

1 5 7 (13) 42 17

n swaps per level * log(n) levels

n * log(n)

Quick vs. Insertion

n = 10^(6)

Insertion: 10^12

10^6 * 20 = 2 * 10^7

IF: 1 GHz = 10^9 steps per second

(2 * 10^7)/10^9 = 2/100 = 1/50 second

10^12/10^9 = 10^3

Both correctly sort the list but Quick sort is much faster.

However, if the list is already sorted, Insertion sort kicks ass yo!

Stable vs. Unstable sorts

A stable sort will keep equal entrys in the same position.

• Merge Sort

Unstable sorts do not guarantee this

• QuickSort

Abstraction

Part of computer science involves a concept known as abstraction.

• involves determing the “least common denominator” held in common by sets of data or functionality within a program. We will be using a lot of abstraction as we go through this course.

Software Engineering

• Most of the time multiple people work on one project
• Testing is important
• Consider software bugs yo!

Object Orientation

• Programs need to meaningfully store and use some type of data.

Primative Data Types

Combinations of these can represent more complex entities. NOTE: string is lowercase in C++

• int
• long
• char
• float
• double
• bool
• string
• <type>[]

Orginization

• The cards deck
• Each Player’s hand
• each individual card

CardHand[] CardDeck::dealHands(int size)

Printing things

In Java:

System.out.println("The answer is " + 42);

In C++:

cout << "The answer is " << 42 << end1;

C++ Code Structure

• In Java the compiler is designed to make multiple passes over code files during compilation
  • In doing this the compiler first finds all objects, variables, etc.
• C++/C perform differently
• In C++ you must manually declare any object, variable, or function within a code file before using it.
• Note: declaring vs defining
  • Declare function “x” exists
  • Define function “x” is equal too.

Files

• Header file “*.h”
  • Contains relevant declarations
  • No functionality
• Source files ”.ccp (”.c” in C.).
  • Contains code definitions
• source and header files then #include other header files with needed definitions.
• Definitions in .cpp files or bust.

Librarys

• Use #include as opposed to Java’s import.
• For built-in resource files #include <NAME>

Important includes

#include <iostream>

// or

#include <string>

OOP Crash Course

• State: its fields, or “member variables”
• Behaviors: it’s associated methods or “member functions”

A very basic C++ object This is not exactly properly designed

using namespace std;

// A very basic c++ object
class Person 
{
public:
  string name;
  int age;
}

• Object orientation is all about rcognizing the different “actors” at work in the system being modeled.
• First, the different data avialable within the system are organized appropriately.
• Secondly, functionalities relating to the state of data and its management are bound to that data.
• Consider constraints
  • Some of our fields may allow values which make no sense in the context of what our object represents.
• Assumptions

Encapsulation

refers to the idea that an object should protect and manage it’s own state information

• Each object should funtion as it’s own entity.
• Should enforce that nobody can edit it in a bad way.

NOTE: a public field can be acessed and modified at any time from code that has a reference to the object. Encapsulation is motivated by the desire to enforce constraints.

• Use the private keywoed,
• Only the object can use these methods and fields.
• C++ default constructors have no internal code.
• You should intialize all values by hand.
• Make your own constructors or die.]

// In the header file
class Person {
public:
  Person(string name, int age);
private:
  string name;
  int age;
} 
// In the source file
Person::Person(string name, int age) 
{
  // This is a pointer.
  // Dot operator is only used for reference by value.
  this->name = name;
  this->age = age;
}

Constructors and functions are defined separately from their declarations

• The Person:: prefix denotes that the Person() constructor belongs to the class Person.

A fully constructed and intialized class object is an instance.

Getter methods

string Person::getName()
{
  return this->name;
}

int Person::getAge()    
{
  return this->age;
}

• Suppose we had a “Person p” The line p.getName() would return the value for “name” from the object represented by “p”.

Setter methods

void Person::setName(string name)
{
  this->name = name;
}

void Person::setAge(int age) 
{
  this->age = age;
}

Do we really need these methods for our class? Always ask this. Probably not to necessary in this example.

If we will never change a value we should use the “const” keyword.

• Analagous to “final” in java

// Improved header
public class Person
{
private:
  const string name;
  int age;
}

Person::Person(string name, int age)
:name(name)
{
  // this->name = name;
  // Throws a compiler error
  this->age = age;
}

Should we allow a “Person” to change his or her age?

void Person::haveABirthday()
{
  this->age = age++;
}

Memory

• Any object in Java is a reference.
• Only prims are handled by value.
• Any time new appears you made an object in reference.

Pointers

Working with Data in C++

By default, most types in C++ will be treated as if they were direct values. Noteworthy exception:

• arrays are automatically pointers to the actual storage.
• The following code is valid:

int i[] = {1, 2, 3}; 

int* iArr = i; //Arrays ARE ptrs.

Conversely, any type in C++ can be referred to via a pointer.

• The following code will handle both variables “by reference.”


int *i = new int(4);

Person *p = new Person(“Joshua Horton”, 28);


The ‘*’ symbol denotes that the variable stores a pointer to that type.

A pointer can be obtained for any value – including pointers! This is done with the & operator.

Person p(“Joshua Horton”, 28);

Person *pPtr = &p;
Person **pPtrPtr = &pPtr;
// Yes, pointers to pointers 
// are completely legal.

Call By Reference

• Last time, we looked at some example “call by reference” code involving pointers.
• Let’s examine a few alternate forms that our code example could have taken.

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

void main()
{
	int a = 2;
	int b = 3;

	swap(a, b);
}

More memory shit

• Copy constructor is special constructor meant to copy objects when they are treated as value types.
• C++ provides on of these automatically unless you provide it yourself.
  • The problem - it performs a shallow copy; it copies contained pointers raher than duplicating the referenced objects
• C++ copy constructors must have one of the following signatures

MyClass(MyClass &old);
Myclass(const MyClass &old);

• Note that by necessity it takes the parameters by reference.
  • Otherwise, instant loop.

By value assignment

string a("apple"), b("banana")
a = b;

C++ also provides a default assignment operator/method for any object.

• This method works similarly to the default constructor - it performs a shallow copy

Operator overload

We’ll get more into the detils later, but classes may specify a custom assignment method.

C++ Destructor

Person::~Person()
{
// TODO Auto-generated destructor.
}

• Our person example held no by-reference fields, this its destructor was empty.
• However, for objects holdinh by

REST ON SLIDE FUCK NOTES, FUCK THEM

// Header
class IntVector
{
public:
  IntVector(int size);
  ~IntVector();
  
private:
  int[] arr;
  int len;
}
  
// Source
IntVector::IntVector(int size)
{
  arr = new int[size];
  len = size;
}
  
IntVector::~IntVector()
{
  delete[] arr;
}
  
// Header
class IntChainLink
{
public:
  IntChainLink(int size);
  ~IntChainLink();
  void setNext(IntChainLink* next);
    
private:
  int item;
  IntChainLink* next;
}
    
// Source
  
IntChainLink::IntChainLink(int size)
{
  item = 0;
  next = 0;
}
  
void setNext(IntChainLink* next)
{
  this->next = next;
}

IntChainLink::~IntChainLink()
{
  if(next != 0)
    {
      delete next;
    }
}

Copying contents of an array, so excite! Wow.

// Constructor
int* arr = new int[n];
int len = n;

// Method
int* temp = new int[2*len];

// Copy contents over... not shown.

delete[] arr;
arr = temp;
len = 2 * len;