Introduction to Computing

Problem Solving and Logic: A problem is a puzzle requiring logical thought to solve 1 . Solving any
problem typically follows an input → process → output model. For example, to sum two numbers you take
inputs (e.g. 3 and 2), apply a process (addition), and produce an output (5) 2 . The logic is the step-by-step
reasoning that defines the process. Logic is “a method of human thought that involves thinking in a linear,
step-by-step manner about how a problem can be solved” 3 . Different valid logics can exist for the same
problem (e.g., checking primality by dividing up to N–1 vs. N/2 vs. √N) 4 5 .

Computational Problems: A computational problem is one that can be solved by following precise rules to
transform input to output. Computation moves from one state to another by rule-based steps. Problems
can be classified (e.g., numerical, logical, data-processing tasks) though specifics may vary.

Computer Organization: At the hardware level, the Central Processing Unit (CPU) executes programs. It
consists of two main parts: the Arithmetic and Logic Unit (ALU) and the Control Unit (CU) 6 . The ALU
performs arithmetic and logical operations (such as + , - , * , / , AND, OR, NOT) 7 . The CU
orchestrates execution: it fetches instructions and data from memory, interprets them, and controls data
flow to/from memory and I/O devices 8 .

Memory: The computer memory is a sequence of storage cells, each with a unique address, used to hold
data, instructions, and results 9 . Memory size is measured in bits (0 or 1), bytes (8 bits), and words
(machine-dependent groups of bits) 9 . Memory is classified as primary (fast, volatile RAM/ROM) and
secondary (slow, nonvolatile storage). For example, RAM (Random Access Memory) is high-speed, read/write
primary memory whose contents are lost on power-off 10 , whereas ROM (Read-Only Memory) is non-
volatile, permanently storing system programs 11 . Secondary memory (e.g. disks) is non-volatile, used for
large data storage when not actively used 12 . Cache memory is very fast memory between CPU and main
memory, holding frequently used data 13 .

Operating System: An Operating System (OS) is a collection of programs that manages the computer and
makes it ready to run user programs 14 . It acts as an interface between hardware and user, handling
resources like CPU, memory, I/O devices and files 14 . Examples include Windows, Linux, and DOS 14 .

Programming Languages: Early programs were written in machine language (binary 0s and 1s). Assembly
language introduced symbolic mnemonics for instructions. Modern high-level languages (like C, C++,
Fortran) use English-like syntax focused on problem-solving, independent of hardware 15 . High-level
programs must be translated into machine code by a compiler (translates entire program at once) or an
interpreter (translates/executing one statement at a time) 16 . An assembler translates assembly
language to machine code 17 .

1
Algorithms and Flowcharts
Algorithm: An algorithm is a precise step-by-step procedure to solve a specific problem 18 . It has a clear
beginning and end, a series of steps, and yields the solution. A typical algorithm notation includes: an
algorithm name, a start point, numbered steps (each describing one simple task or decision), and a
termination/end point 19 20 . For example:

• Compute area of a circle:

• Start
• Read radius
• Compute Area = 3.1416 * radius * radius
• Print the Area

• Stop 21 22

• Swap two variables (A, B):

• Start
• Input A, B
• temp = A
•A=B
• B = temp
• Print A, B

• Stop 23 24

• Largest of three numbers (A, B, C):

• Start; read A, B, C
• If A > B go to step 5; else go to step 4 25 .
• [Compare B and C]: if B > C then print “B is largest”; else print “C is largest”; goto step 6 26 .
• [Compare A and C]: if A > C then print “A is largest”; else print “C is largest”; goto step 6 27 .

• Stop 28 .

• Factorial of N:

• Start; read N; set fact = 1 29 .

• For count = 1 to N:
◦ fact = fact * count 30 .
• Print fact ; stop 31 .

Such algorithms can be translated into code. For instance, the factorial algorithm above corresponds to C
code:

2
 int fact = 1;
for(int i = 1; i <= N; i++){
fact *= i;
}
printf("Factorial = %d", fact);

Each step in the algorithm becomes one or more statements in code.

Flowchart: A flowchart is a graphical representation of an algorithm 20 . Common flowchart symbols

include: - Oval (Start/End), - Parallelogram (Input/Output), - Rectangle (Process/assignment), - Diamond
(Decision). For example, the flowchart for “compute area of circle” would start with an input symbol for
radius, a process box to compute A = πr² , an output box to display A, and an end terminator (Stop).
Flowcharts help visualize the sequence of operations and decisions in an algorithm.

Pseudo-code vs Flowchart: Algorithms may be written in text (pseudo-code) or drawn as flowcharts. For
example, “Find Factorial of N”: - Algorithm (pseudo-code): See steps above 32 33 . - C code example:

#include <stdio.h>
int main() {
int N, i, fact = 1;
printf("Enter N: ");
scanf("%d",&N);
for(i = 1; i <= N; i++)
fact = fact * i;
printf("Factorial = %d\n", fact);
return 0;
}

- Flowchart: Would show a loop construct (typically a flow line back to a decision) representing the for-loop.
(One could draw a loop arrow from the bottom of the loop back to its top decision.)

Variables, Data Types, and Expressions

Variables: A variable is a named storage location in memory 34 . In C, every variable must be declared with
a data type before use 34 . For example:

int count; // declares an integer variable named count

float average; // a floating-point variable
char grade; // a character variable

A declaration specifies the variable’s type and name. After declaration, you can assign values:
count = 10; stores 10 in count, average = 9.5; , etc.

3
Data Types: C has basic built-in data types for integers, real numbers, characters, and void. The primary
types are int, float, double, char, and void 35 . Their meanings are: - int : integer numbers (no decimals)
35 . - float : single-precision real numbers (with decimals) 36 . - double : double-precision real
numbers (typically twice as precise/large as float) 36 . - char : single characters (e.g. 'a', '7') 37 . - void :
special type indicating “no type” (used for functions returning nothing) 38 .

Each type has a size and range that may depend on the machine (common sizes: 16/32/64 bits for int).
Modifiers can change size or sign: e.g., short , long , signed , unsigned 39 40 . For example, on a
typical 32-bit system, short int is 16 bits, int is 32 bits, and long int is 32 or 64 bits 39 .
unsigned int allows only non-negative values but doubles the positive range.

Constants: Constants are fixed values used in code, like 100 , 3.14 , or 'A' . C supports integer
constants (e.g. 123 ), floating constants ( 3.14 ), character constants ( 'A' ), and string literals
( "Hello" ). Constants with no decimal default to int , those with a dot are double by default.

Expressions and Operators: An expression combines variables, constants, and operators to compute a
value. For example, a + b * 2 is an arithmetic expression. C supports many operators: - Arithmetic: + ,
- , * , / , % (modulo).
- Relational: == , != , < , > , <= , >= (compare values).
- Logical: && (AND), || (OR), ! (NOT) for boolean logic.
- Bitwise: & , | , ^ , << , >> for bit-level operations on integers.
- Assignment: = , += , -= , *= , etc., which assign values.
- Increment/Decrement: ++ , -- to add or subtract 1.

Operators follow a precedence (e.g. * before + ) and associativity rules. When an expression mixes types
(say int and float ), C converts types according to its type conversion rules (usually promoting to the
larger type, e.g. int → float). For example, in 3 + 4.5 the integer 3 is converted to 3.0 so the result is a
float 7.5.

Example:

int a = 5, b = 2;
float result;
result = a / (float)b; // Casting b to float: result = 2.5
if (a > b) {
printf("a is greater\n");
}

Here a / (float)b is a mixed-type expression yielding 2.5 . The if uses a relational operator > to
compare a and b .

Decision Making, Branching, and Looping

Programs control flow using selection (branching) and iteration (looping) structures.

4
Sequential execution means statements run in order. Selection allows conditional branching: some code
executes only if a condition holds.

• if Statement: Executes a block only when a condition is true.

if (condition) {
// executed if condition is nonzero (true)
}
// next statement always executes after

For example, to check even/odd:

if (x % 2 == 0) {
printf("Even\n");
}

If the condition is false (zero), the block is skipped 41 .

• if-else Statement: Chooses between two blocks.

if (score >= 60) {

printf("Pass\n");
} else {
printf("Fail\n");
}

If the test is true, executes the first block; otherwise executes the else block 42 .

• Nested if and else if : You can nest if statements or chain multiple conditions:

if (grade == 'A') {
printf("Excellent\n");
} else if (grade == 'B') {
printf("Good\n");
} else {
printf("Try again\n");
}

Only the first matching condition’s block runs.

• switch Statement: A multi-way branch on an integer or char expression 43 . Its syntax:

5
 switch (expr) {
case value1:
// statements
break;
case value2:
// statements
break;
...
default:
// statements
}

The value of expr is compared to each case . When a match is found, execution starts there and
continues until a break or end of switch. The default case (optional) runs if no match is found
44 . For example, grading:

switch (score) {
case 100: case 90: case 80:
grade = 'A'; break;
case 70: case 60:
grade = 'B'; break;
default:
grade = 'F'; break;
}

A switch is a multiple-branching statement, transferring control based on a discrete value 43 . (The

controlling expression must be integer or char; no floating-point.)

Iteration (Loops): Repeating statements:

• for loop: Best when the number of iterations is known. General form:

for (initialization; condition; update) {

// loop body
}

• Initialization runs once at the start (e.g. i = 0 ).

• Condition is tested before each iteration; if false, loop ends.

• Update executes after each iteration (e.g. i++ ) 45 . For example, sum numbers 1–N:

int sum = 0;
for (int i = 1; i <= N; i++) {
sum += i;

6
 }
printf("Sum = %d\n", sum);

This loop sets i =1, checks i<=N , executes body ( sum += i ), then does i++ , and repeats until
i>N . It is entry-controlled (condition tested first) 46 .

• while loop: Also entry-controlled. Syntax:

while (condition) {
// loop body
}

As long as condition is true, the body repeats 47 48 . Example: print numbers 1–N:

int i = 1;
while (i <= N) {
printf("%d\n", i);
i++;
}

If the condition is false initially, the body may never execute 49 .

• do-while loop: Exit-controlled. Syntax:

do {
// body
} while (condition);

The body executes first, then condition is checked; if true, repeat 50 . This guarantees the loop
runs at least once 51 . Example:

int n = 0;
do {
printf("Enter a positive number: ");
scanf("%d", &n);
} while (n <= 0);

• Nested loops: You can place one loop inside another. For example:

for (i = 0; i < 3; i++) {

for (j = 0; j < 2; j++) {

7
 printf("%d %d\n", i, j);
}
}

Loop Control: The statements break and continue alter loop flow (though not covered in slides, they
are common). break; exits the nearest loop or switch. continue; skips to the next iteration of the
loop.

One-Dimensional Arrays
An array is a collection of elements of the same type stored in contiguous memory, all referenced by a
single name 52 . In C, a one-dimensional array (vector) has a single index (subscript). For example:

int arr[5]; // declares an array of 5 ints

This allocates 5 contiguous int cells, named arr[0] through arr[4] 53 . The first index is 0 (zero-
based indexing). We can initialize an array at declaration:

int x[3] = {9, 11, 13}; // x[0]=9, x[1]=11, x[2]=13

Or partially initialize; unspecified elements default to 0. For example int a[5] = {1,2}; yields
{1,2,0,0,0} 54 . To declare without specifying size, one can do int b[] = {4,5,6}; which sets the
size to 3.

Accessing Elements: Use the index in brackets. For example:

arr[0] = 10;
printf("%d\n", arr[0]); // prints 10

Indices must be integers from 0 up to one less than the array size. Accessing an out-of-range index causes
undefined behavior.

Total Memory: The total memory used by an array of size n is n * sizeof(element_type) . (E.g., an
int arr[10] on a 32-bit machine uses 10 * 4 = 40 bytes).

Example – Reading/Printing an Array:

#include <stdio.h>
int main() {
int n;
printf("Enter number of elements: ");

8
 scanf("%d", &n);
int arr[n]; // or a fixed maximum size
printf("Enter %d elements:\n", n);
for(int i = 0; i < n; i++){
scanf("%d", &arr[i]); // read each element
}
printf("You entered: ");
for(int i = 0; i < n; i++){
printf("%d ", arr[i]); // print each element
}
return 0;
}

This uses a loop to input and output the elements 55 56 .

Arrays are used for data structures and algorithms (like sorting/searching).

Searching and Sorting

Searching: Finding whether a value exists in a collection.

• Linear (Sequential) Search: Checks elements one by one from the start. It works on unsorted data.
Algorithm: Compare the search key to each element in order; stop if found or end of list 57 . Its
complexity is O(n) in the worst case. Example C code:

int found = 0, pos = -1;

for(int i = 0; i < n; i++){
if(arr[i] == key) { found = 1; pos = i; break; }
}
if(found) printf("Found at index %d\n", pos);
else printf("Not found\n");

(Slide [15] outlines this procedure 57 .)

• Binary Search: Applicable only to sorted arrays. It repeatedly halves the search range. Algorithm:

• Set low = 0 , high = n-1 .

• While low <= high :
◦ Compute mid = (low+high)/2 .
◦ If arr[mid] == key , found.
◦ Else if key < arr[mid] , set high = mid-1 ; else set low = mid+1 .
• If the loop ends without finding, the key is absent.
This runs in O(log n) time. It uses divide-and-conquer on a sorted array 58 .

9
Sorting: Arranging data in order (usually ascending). Two simple methods:

• Bubble Sort: Repeatedly “bubbles” the largest (or smallest) element to the end by comparing
adjacent pairs and swapping if out of order 59 60 . One pass through N elements moves the largest
element to the last position. Repeat for N–1 passes. Pseudocode (ascending order):

for (i = 0; i < N-1; i++) {

for (j = 0; j < N-1-i; j++) {
if (A[j] > A[j+1]) {
swap A[j] and A[j+1];
}
}
}

Example C code:

for(int i = 0; i < n-1; i++){

for(int j = 0; j < n-1-i; j++){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}

On each inner loop, the largest remaining element moves (“bubbles”) to position n-1-i . This
method is simple but inefficient on large lists (worst-case O(n²)). Slides illustrate bubbling the
largest up the list 59 60 .

• Selection Sort: Repeatedly selects the smallest remaining element and swaps it with the first
unsorted position. Algorithm for ascending order:

for (i = 0; i < N-1; i++) {

minIndex = i;
for (j = i+1; j < N; j++) {
if (A[j] < A[minIndex]) minIndex = j;
}
swap A[i] and A[minIndex];
}

Example C code:

10
 for(int i = 0; i < n-1; i++){
int min = i;
for(int j = i+1; j < n; j++){
if(arr[j] < arr[min]) min = j;
}
// swap arr[i] and arr[min]
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}

Each pass increases the sorted portion by one (placing the next smallest element in order). Selection
sort also runs in O(n²) but generally makes fewer swaps than bubble sort.

• Comparison (Bubble vs. Selection):

| Feature | Bubble Sort | Selection Sort |
|-------------------|------------------------------------|--------------------------------------| | Method | Compare adjacent
elements and swap | Find min each pass and swap with front | | Number of swaps | Many swaps
(every out-of-order pair) | Fewer swaps (one per pass at most) | | Efficiency | Generally less efficient
(slow) | Faster than bubble on average | | When to use | Simple to code/teach | Slightly better
performance |

(This aligns with the summary: bubble sort is an exchanging method using adjacent swaps, while selection
sort is a selection method that places the smallest element into position each pass 61 .)

In practice, more advanced sorts (quick sort, merge sort) are used for large data, but bubble and selection
sorts illustrate fundamental ideas of in-place comparison sorting.

Summary: Searching and sorting are fundamental array operations. Linear search checks each element
(O(n)), binary search uses divide-and-conquer on sorted arrays (O(log n)) 57 58 . Bubble and selection sorts
arrange unsorted data into order via repeated passes (both are O(n²) algorithms) 59 62 . These methods
form the basis for understanding more complex algorithms.

Sources: The above notes and examples are drawn from the provided lecture materials 1 21 43 47 52

57 61 .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 L1-L2 Introduction to [Link]

[Link]

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 L3-L5 Algorithm, [Link]

[Link]

34 35 36 37 38 39 40 L6-L9-Variables, Data types, [Link]

[Link]

11
41 42 43 44 45 46 47 48 49 50 51 L10-L13-Decision making, Branching and [Link]
[Link]

52 53 55 56 [Link]
[Link]

54 57 58 59 60 61 62 L16-L17-Searching -[Link]
[Link]

12