CE 303 Algorithms and Data Structures

Instructor:
Saptadi Nugroho, M.Sc.
Banu W. Yohanes, M.CompSc.

• Introduction
• Review C
1
 Algorithm
• A procedure for solving a problem in terms of
the actions to be executed and the order in
which the actions are to be executed.

2
 Why C?
• Modular procedural language with arrays,
structures, and references
• C vs. Pascal
– modern, portable, better textbooks and tools
– employment prospects (C, C++, Java)
• C vs. C++ or Java
– small, clean, simple
– can support learning data structures without learning
too much language extras

3
 What are computers?
• They can do simple operations incredibly fast
if you tell them every step to do
• They are like little children in their need for
specific and detailed instruction
• computers are not “brains” & are not “smart”
- they only as good as the program they are
running

4
 Programs and programming
• What is a program?
– A set of instructions working with data designed
to accomplish a specific task
– The “recipe” analogy
• Ingredients are the Data
• Directions are the Program Statements
• What is programming
– The art to control “children”.

5
 Commands and data

• Components of a program
– Data
– Commands (instructions)
• This is true on several levels
• Basic features of a machine language or a
programming language:
– Ways to represent information - data types
– Ways to act on information - operations

6
 Information Representation

• Computer store information digitally in

binary format
• Ultimately everything is ones and zeroes
– characters, numbers
– instructions (programs!!)
– pictures, video
• Binary arithmetic E.g., 7 = 00000111
99 = 01100011
7
From Commands to Algorithms
machine commands 0100 0001101 10001110

high-level language commands

a = 16; printf("Hello!\n”)

basic control structures while for if-else switc

simple patterns average maximum string reading

algorithms sorting binary searchmatching

8
 C Program Syntax
• Most C programs have the following (at
minimum):
main ([program arguments])
{
<one or more statements>
}
• Every program must have a “main” function.
Note that C is case sensitive (Main is not the
same as MAIN or main).
9
 Hello World Program

#include <stdio.h>

main()
{
printf(“Hello World!\n”);
}

Dissection adapted
10
From S. Pilachewski
 Hello World - dissected
#include <stdio.h>

main()
{
printf(“Hello World!\n”);
}
• Directive which tells the compiler that the
standard input / output library will be used.

11
Hello World - main() Function
#include <stdio.h>

main()
{
printf(“Hello World!\n”);
}
• Execution of a C program always begins at the
main() function. Every C program must have
one (only one) main() function.
12
 Hello World - the Braces
#include <stdio.h>

main()
{
printf(“Hello World!\n”);
}
• The open brace ({) marks the beginning of the function
body, which is one or more program statements which
perform some task.
• The closing brace (}) marks the end of the function body.
13
Hello World - the printf statement
#include <stdio.h>

main()
{
printf(“Hello World!\n”);
}
• This statement is a function call to the printf function in
the C Standard I/O Library. It displays the message which is
the argument to the function. The \n denotes the newline.

14
 Hello World - the semicolon
#include <stdio.h>

main()
{
printf(“Hello World!\n”);
}

• The semicolon marks the end of a C program

statement.
15
From Data to Data Structures

machine level data storage

0100110001101001010001

primitive data types 28 3.1415 'A'

data aggregates array structure

high-level data structures stack queue tree

16
 Primitive Data Types

• Integer data
1, 10, 999, 1000 10 999

• Floating point data

3.1415, 0.001, 2.0 3.1415 0.001

• Characters
'A', 'B', '_', '@' 'A' '@'

17
 Primitive data can be printed

#include <stdio.h>

main()
{
printf(“Hello, World!\n”);
printf(“Here are integers: %d %d\n”, 10, 99);
printf(“Here are floats: %f %f\n”, 3.1415, 0.001);
printf(“Here are characters: %c %c\n”, 'A', '@');
}

18
 Expressions?
• What is an expression?
• Anything that can have a value
• In C almost anything is an expression
• Expressions can have values of different type
• A literal constant is an expression:
4 3.1415 99 'A' 0.0001

19
 Three things to do with a variable

• Declare a variable
int grad;

• Assign a value
grad = 50; 50

• Use a variable
printf("%d grades”, grad); 50

20
 Important
• A variable has to be defined and initialized
before first use
• Each assignment changes the value of the
variable - only the last one is stored
• Each use does not change the value, so the
same value will be used

21
 Expressions again
• Expression: something that has a value
• Types of expressions
– Literal constants: 33 or 3.14
– Variables: count
– Simple - two operands and operator: 3 + 5
– Complex: (count - (44 - 12) / 7) * num

22
 From expressions to statements
• Statement: expression with a semicolon
33;
3+5;
x = 0;
x = y = 0; /* x = (y = 0); */
printf(“Hello, World!\n”);

23
 Block and sequential execution
• Block: { …..}
– A group of statements
– Statements are sequentially executed
– Syntactically equivalent to a statement
• Example:
{
a = a +1;
b = a % 2;
}
24
 Block and sequential execution
• Flowcharts are used to show the control flow inside
the program
• Sequential execution inside a block means that the
control (over the processor) flows downwards from
statement to next statement

a = a +1

b=a%2
25
 While loop
while (expression)
loopstatement

nextstatement

– If expression is not 0 (true) - dive into the loop

– If expression is 0 (false) - skip to nextstatement
– I.e, while expression is true, do the loop

26
Flowchart of the while loop

Yes
Expression is
equal to 0?
No
Statement1

StatementK

Nextstatement
27
Increment/decrement expressions
• Post-Increment: num++
• Pre-Increment: ++num
• There are also pre and post-decrements
count-- or --count

28
 Defining symbolic constants
• #define is a preprocessor directive for defining
symbolic constants
• Example:
#define commission 3.0
• commission is a symbolic constant
– Now every appearance of commission is literally
replaced by 3.0
– It is not a variable, it can’t be assigned a value

29
 More About Preprocessor
• Preprocessor is a separate part of C compiler,
which differs from the rest of it
• Makes file insertions
#include <stdio.h>
• Resolves definitions
#define NUM 100.0
• Removes comments
/* this is simply a comment */

30
 Example : Temperature Converter
#include <stdio.h>
#define FAHR 100.0 /* the temperature to be converted */

main() {

printf("%6.2f Fahrenheit = %6.2f Celsius\n",

FAHR, (5.0/9.0)*(FAHR-32));
}

31
 Example after preprocessing

...content of the file stdio.h...

main() {

printf("%6.2f Fahrenheit = %6.2f Celsius\n",

100.0, (5.0/9.0)*(100.0-32));
}

32
 Example : More Interest
main() {
int years; /* years the capital stays in bank */
float interest_rate; /* interest rate in percents */
float capital; /* capital in dollars */
float annual_interest; /* annual interest in dollars */

printf("Startup capital ($$$.cc): ");

scanf("%f",&capital);
printf("Interest rate in percents (xx.xx): ");
scanf("%f",&interest_rate);
printf("How many years? ");
scanf("%d", &years);
while (years) {
annual_interest = capital * interest_rate / 100;
capital = capital + annual_interest;
--years;
}
printf("New capital %9.2f\n", capital);
}

33
 Reference
Brusilovsky, Peter. 2001. INFSCI 0015 “Data Structures
and Programming Techniques”. Available at:
http://www2.sis.pitt.edu/~peterb/0015-
011/syllabus.html

34