EL2008 Problem Solving with C
Muhammad Ogin Hasanuddin
Sekolah Teknik Elektro dan Informatika
Institut Teknologi Bandung
Introduction
Time : Tuesday 13.00-14.40
Thursday 12.00-12.50
Place : Tuesday (9015 Classroom)
Thursday (9013 Classroom)
Instructor : Dr. Arif Sasongko, S.T., M.T.,
Muhammad Ogin Hasanuddin, S.T., M.T.
Office : Lab Sistem Kendali & Komputer (LSKK)
Phone : 081322104895
Email : moginh@[Link] or
moginh@[Link]
Office Hours : By Appointment through email/phone
Requisite
Prerequisite
KU1071 Introduction to Information Technology A
Corequistite
EL2208 Problem Solving with C Lab
Class Informations
Text Book
Hanly, Jeri, and Koffman, Elliot, "Problem Solving and Program
Design in C", 7th ed, Addison Wesley, New York, 2013
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
Clifford Stein, “Introduction to Algorithms”, The MIT Press, 3rd
edition, 2009
Outcome
Knowing the problem and alternative solutions
Algorithm
Flowchart / Pseudocode
Data Flow Diagram (DFD)
Implementation Flowchart / Pseudocode into C code
Testing
Syllabus
Week Topic
1 Introduction History and Overview
Programming Variables, types, expressions, and assignment
Construct Simple I/O, Conditional Structures, Iterative control structures
2 Programming Pointers, Strings and string processing, Functions and parameter
Construct passing, File I/O
3 Algorithms and Problem-solving strategies, Structured decomposition
problem-solving Debugging strategies
4 Algorithms and Problem-solving strategies, Structured decomposition
problem-solving Debugging strategies
5 Algorithms and Problem-solving strategies, Structured decomposition
problem-solving Debugging strategies
6 Data Structure Structure and Records
7 Data Structure Data representation in memory. Static, stack, and heap allocation
Runtime storage management. Linked structures
Midterm
Syllabus
Week Topic
8 Data Structure Implementation strategies for stacks, queues, and hash tables
Implementation strategies for graphs and trees
9 Recursion The concept of recursion. Recursive mathematical functions
Divide-and-conquer strategies. Recursive backtracking.
10 Basic Algorithm Asymptotic analysis of upper and average complexity bounds
Analysis Identifying differences among best, average, and worst-case
behaviors
Big "O," little "o," omega, and theta notation. Empirical
measurements of performance. Time and space tradeoffs in
algorithms.
11 Algorithm Strategy Brute-force/exhaustive search algorithms. Greedy algorithms.
12 Algorithm Strategy Divide-and-conquer. Backtracking.
13 Computing Algorithm Simple numerical algorithms
14 Project -
15 Project -
16 Final Exam
Grading Component
Assignment 10%
Quiz 20%
Mid term + Final Term 35%
Final Project 25%
Grading Scale
A > 90%
AB 80% - 90%
B 75% - 79%
BC 65% - 74%
C 56% - 64%
D 50% - 55%
E < 50%
A Tour of Computer Systems
Today Topics
Understanding of computer system
Compiler System
Hardware Organizations
Bus, I/O Device, Memory, Processor
Cache memory
Operating System
Virtual memory
Why you should be in this class?
To become knowledgeable about problem solving
techniques (using C programming language)
Learn to solve a variety of engineering and programming
problems as needed throughout their undergraduate
work
Computer System
Hardware and Operating system works together to
execute an application.
Implementation of a computer can change but not the
concept
Program hello
Classic first program
hello program is created using a text editor and saved as
hello.c
Source program is a sequence of bits, each with a value 0 or 1,
organized into 8 bits called byte
Each byte represents a character
hello.c is stored in a file as a sequence of bytes.
hello Program
Written in high level language C
Code :
1. #include <stdio.h>
2.
3. int main()
4. {
5. printf(“hello, world\n”);
6. return(0);
7. }
ASCII Table (Each byte represents a character)
Source: [Link]
ASCII Representation of hello Program
hello Program
Every C statement must be translated to machine
instructions (in binary)
These instructions are then packaged into an executable
object program and stored in a binary file
Translation process is performed by a compiler
Compilation System
Preprocessing phase
preprocessor (cpp) modifies the original C program according
to the # directive
Example: #include <stdio.h> tells the preprocessor to read the
stdio.h file and insert it into the program text.
Compilation phase
compiler (ccl) translates the text file hello.i into the text file
hello.s which contains an assembly language program. Each
statement in an assembly language represents one machine-
language instruction in a text form.
Compilation System
Assembly phase
assembler (as) translates hello.s into machine-language
instructions, packages then into a relocatable object program
and store the result into a file hello.o
Linking phase
linker (ld) merges hello.o with printf.o and the result is an
executable object file
Understand how compilation system works
Optimizing program performance
Example :
Which one more efficient?
switch or if-then-else ?
while or do ?
Using pointer or array indexes?
Which is faster local variable or passed by reference?
Understanding link time error
What is link error?
What is static or dynamic library?
Avoid security holes
Buffer overflow bugs
Hardware Organization
To understand what happens when we run the hello
program, we need to know how the hardware is
organized.
In general the component of a computer system consists
of :
Bus
I/O devices
Main Memory
Processor
Hardware Organization
Hardware Organization
Bus
Parallel conduits that carry bytes of information between
components.
Bus size is usually given in words
Intel Pentium, word size = 4 bytes
Intel Itanium, word size = 8 bytes
Embedded, word size = 1 or 2 bytes
I/O Devices
Connection to the outside world
Example: keyboard, mouse, monitor, disk drive (disk)
Every I/O device is connected using a controller or adapter
Controller : chip set in the device itself or on the motherboard
Adapter : card that plugs into to the slot of the motherboard
Hardware Organization
Main Memory
Temporary storage that holds both program and data it manipulates
while the processor is running the program.
Physically, the main memory is a collection of Dynamic Random Access
Memory (DRAM)
Logically, the main memory is a organized as a linear array
Processor (Central Processing Unit % CPU)
The engine that executes the instructions stored in the main memory
Consists of registers, ALU and program counter (PC)
At any point of time the PC (contains address) is always points to an
instruction in the main memory.
Processor is always doing the same task over and over again
Read an instruction from memory
Execute it
And read the next instruction
Hardware Organization
Processor
Has only a few (?) instructions that revolve around main
memory, registers and arithmetic/logic unit ALU
Register : fast memory but only a few, reside inside the CPU
ALU : computes new data or address
Types of CPU operation:
Load : copy a byte or a word from main memory to a register
Store : copy a byte or a word from register to the main memory
Update : copy the content of two registers to ALU, adds the two
words and store the result into a register
I/O Read : copy a byte or a word from an I/O device to a register
I/O Write :copy a byte or a word from a register to an I/O device
Executing hello program (1)
CPU
Read the hello command
Register file
from keyboard
PC ALU
System bus Memory bus
I/O Main "hello"
Bus interface
bridge memory
I/O bus
Expansion slots for
other devices such
USB Graphics Disk
as network adapters
controller adapter controller
Mouse Keyboard Display
User Disk
types
"hello"
Executing hello program (2)
CPU
Loading the executable
Register file
from disk to main
PC ALU memory
System bus Memory bus
Main "hello,world\n"
I/O
Bus interface
bridge memory
hello code
I/O bus Expansion slots for
other devices such
as network adapters
USB Graphics Disk
controller adapter controller
Mouse Keyboard Display
hello executable
Disk stored on disk
Executing hello program (3)
CPU Writing output from
Register file
memory to the display
PC ALU
System bus Memory bus
I/O Main "hello,world\n"
Bus interface
bridge memory
hello code
I/O bus Expansion slots for
other devices such
as network adapters
USB Graphics Disk
controller adapter controller
Mouse Keyboard Display
hello executable
"hello,world\n" Disk stored on disk
Cache Memory
Cache memory is needed to solve the problem of speed
difference between the processor and main memory
Cache is a high-speed static RAM (faster than DRAM still slower
than registers)
Cache holds the most recently accessed information
L1 cache size is about tens thousand to a hundred thousand
bytes
L2 cache size is about hundred thousand to millions of bytes
Memory Hierarchy
The OS manages the HW
Primary Purpose:
Manages all hardware components
Provide applications with simple and uniform mechanism for
manipulating hardware
Application programs Software
Operating system
Hardware
Processor Main memory I/O devices
Abstractions
Process
Is the OS abstraction of running program
Multiple process can run concurrently
OS keeps track of all the state information that the process needs in
order to run
Threads
A process can have multiple execution units that can run
concurrently
Threads shares the same code and global data
Processes
Virtual memory
Files
Processor Main memory I/O devices
Virtual Memory 0xffffffff
Memory
invisible to
user code
Kernel virtual memory
Is an abstraction that 0xc0000000
User stack
provides an illusion that a (created at runtime)
process has exclusive use of
the main memory
Each process has the same Memory mapped region for
shared libraries
printf() function
view of memory (virtual 0x40000000
address space)
Contents
Run-time heap
Program and data (created at runtime by malloc)
Heap
Read/write data
Shared library Loaded from the
Stack hello executable file
Read-only code and data
Kernel virtual memory 0x08048000
Unused
0
Files
A sequence of bytes
Every I/O device is modeled as a file
All input and output is performed by reading and writing
files (Unix I/O)
Thank You!