Programming 622 Study Hub

1.2 Development Phase

The development process is broken into analysis, design, implementation, testing and debugging. Analysis comes first because the programmer must understand the problem, requirements, data and expected output.

1.7 Identifying Classes, Objects And Operations

In object-oriented design, identify the objects in the problem, list the data each object must store, then list the operations that act on that data.

2.3 Sequence Container: vector

A vector manages objects in a dynamic array. It supports random access like an array, makes end insertion fast, and uses the <vector> header.

#include <vector>
#include <iostream>
using namespace std;

vector<int> marks;
marks.push_back(76);
marks.push_back(84);

cout << marks[0] << endl;

3.2 Item Insertion And Deletion

Insertion and deletion are done by changing links. The core discipline is to preserve access to the rest of the list before rerouting pointers.

4.2 Problem Solving Using Recursion

Recursive algorithms work well when the problem naturally breaks into smaller copies, such as factorial, recursive list processing and tree traversal.

int sumTo(int n) {
	if (n == 0)
		return 0;
	return n + sumTo(n - 1);
}

5.2 Linked Implementation Of Stacks

A linked stack stores stack elements in nodes. The top pointer identifies the node that will be read or removed next.

6.2 Implementation Of Queues As Arrays

An array-based queue needs indexes for the front and rear. Because insertion and deletion happen at different ends, careful index movement is essential.

7.4 Binary Search

Binary search uses divide and conquer on an ordered list. It compares the search item with the middle element, then continues in the half where the item could exist.

int first = 0;
int last = length - 1;

while (first <= last) {
	int mid = (first + last) / 2;
	if (list[mid] == item)
		return mid;
	if (item < list[mid])
		last = mid - 1;
	else
		first = mid + 1;
}

8.2 Insertion Sort

Insertion sort divides the array into a sorted upper portion and an unsorted lower portion. The first unsorted element is moved into its correct place in the sorted portion.

for (int firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++) {
	if (list[firstOutOfOrder] < list[firstOutOfOrder - 1]) {
		elemType temp = list[firstOutOfOrder];
		int location = firstOutOfOrder;

		do {
			list[location] = list[location - 1];
			location--;
		} while (location > 0 && list[location - 1] > temp);

		list[location] = temp;
	}
}

9.2 Binary Tree Traversal

Traversal visits every node. The order matters: preorder, inorder and postorder place the root visit at different points in the left-root-right sequence.

10.5 Graph Traversals

Graph traversal is more complex than tree traversal because graphs may contain cycles and may not be connected. The guide uses a visited array to prevent repeated visits.

visited[v] = true;
for each vertex u adjacent to v
	if (!visited[u])
		traverse from u;