UE204 Intro to Computer Science 2: C Programming

• The material is for UE204 Introduction to Computer Science 2.
• The course focuses on the C programming language.
• It includes LC(Lecture and Class) sessions.

General Information

• The course is worth 3 credits.
• The written exam accounts for 3 credits.
• PWs(Practical Works)/Project is worth 3 credits.
• There are 10 IC(Introduction to Computer Science) sessions totaling 15 hours.
• There are 16 Ex(Exercise) sessions totaling 24 hours.
• There are 14 PW(Practical Works) sessions totaling 21 hours.

Course Outline

• Introduction
• How a computer works including hardware, instructions, memory, numbering system, OS, and programming languages
• Text Editor, Compiler, Integrated Development Environment
• C programming language
• Data types
• Operations
• Conditional statements
• Loops
• Command line
• Functions
• Variables and scopes
• Arrays
• Command line arguments
• Linear search
• Binary search
• Bubble sort
• Selection and Merge sort
• Recursion
• String.
• Hexadecimal
• Pointers
• Defining custom types
• Dynamic memory allocation
• Call stack
• File Manipulation
• Data structures
• Struct, Union, Enum
• Single linked lists
• Hash table
• Tries

Number Base Conversions

• Understanding conversions between different number bases like binary, octal, decimal, and hexadecimal is important in computer science
• Binary format represents data at computer systems’ lowest level, with converting between decimal (base-10) and binary (base-2) being crucial for understanding integer representation
• Memory addresses/storage are often represented in hexadecimal (base-16)
• Programmers frequently use hexadecimal values when dealing with memory addresses, bitwise operations, and low-level programming.
• Digital logic circuits use binary values (0 and 1).
• Binary and its conversion to other bases is key to understanding logic gates and circuits.
• In low-level programming, developers may manipulate data at the bit level that involves understanding binary representation and converting between different bases.
• IP addresses in networking, represented in dotted-decimal notation, require converting between decimal and binary
• Understanding decimal/binary conversions is crucial for network administration and programming.
• Security and cryptography use operations involving binary and hexadecimal.
• Understanding conversions helps implementing and analyzing cryptographic algorithms.
• Bitwise operations (AND, OR, XOR, etc.) are used in programming, especially in low-level and systems programming
• Understanding binary representation is crucial for working with bitwise operations effectively.
• In embedded systems programming, developers may need to optimize code at the bit level that makes understanding binary representation conversions beneficial.
• Memory addresses are typically represented in hexadecimal when working with pointers in languages like C or C++.
• For example, if int x = 42 is stored in memory at address 0x0012ABCD, then the value x is 42 in decimal and 2A in hexadecimal.

Lecture Overview

• Positional Numbering System
• Conversions
• Signed integer representation
• Floating-point representation

Positional Numbering System

• Numeric values are represented through increasing powers of a base, referred to as a weighted numbering system.
• Any numeric value is represented through increasing powers of a base.
• The set of valid numerals (digits) equals the base size of that system.
• The smallest numeral is 0, while the largest is 1 less than the base.
• The most important bases in computer science are:
• Decimal with base 10 and numerals {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
• Binary with base 2 and numerals {0, 1}.
• Octal with base 8 and numerals {0, 1, 2, 3, 4, 5, 6, 7}.
• Hexadecimal with bas 16 and numerals {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}.
• Bases are used as a subscript to distinguish numbers in different bases, eg 2310
• Numbers without a subscript are assumed to be decimal.

Decimal and Integer Conversions

• Any decimal integer can be expressed in any other integral base system, and vice versa.
• Example:
• 243.5110 = 2x10² + 4x10¹ + 3x10⁰ + 5x10⁻¹ + 1x10⁻²
• 10110.01₂ = 1x2⁴ + 0x2³ + 1x2² + 1x2¹ + 0x2⁰ + 0x2⁻¹ + 1x2⁻² = 22.25₁₀
• The first position (right-hand side) of the integer part is multiplied by the base raised to the power 0.
• The first position (left-hand side) of the fractional part is multiplied by the base raised to the power -1.
• Numbers may have integer and fraction parts separated by a base point.
• Base points separate the integer part of a number from its fractional part.
• The base point is called a "decimal point" in a decimal system or a "binary point" in a binary system.

Converting to Decimal

• To convert the integer part, divide the number by n, the base.
• Derive the Quotient and Remainder where the remainder is always less than the base n.
• Keep each remainder aside.
• Repeat the above steps using the quotient until it equals 0.
• Group the remainders in order, where the first remainder is the least significant bit, and the last is the most significant bit.
• MSB is the highest-order bit (leftmost bit).
• LSB is the lowest-order bit is the rightmost bit
• A binary number with N bits can represent 2^N unsigned integers from 0 to 2^N-1.
• When converting from decimal to any base to obtain them.

Converting fraction to decimal

• Fractions in a decimal system can be converted/approximated to fractions in any other base using negative powers of a base.
• Example of fractions (the integer part is italic and the fractional part is bold)
• Base 10 : 2390167.1208
• Base 2 : 1011110.111011
• Use multiplication to convert fractions, because fractions are expressed in negative powers of the base.
• When multiplying, use only the integer part of the product after multiplication by the base.
• Given the fractional part of a decimal number, you can find the equivalent value in any base, n.
• Multiply the fraction by the base n.
• Deduct the integer part from the product, and keep it aside.
• Take the remaining fraction and repeat the process with the new value, until the fraction is zero or if there are enough digits after the base point.
• Group the deducted integers that have been set aside from top to bottom and put them in the fraction form.
• To convert fractions from decimal to any other base system we repeatedly multiply by the destination base.

Converting from Any Base to Decimal

• To convert from any base, n, to decimal, multiply the digits by the base n raised to the position of that digit.
• Given a number in base n, multiply each digit with the base raised to the power of its location.
• The LSB digit has a position of 0, and the digits after the base point (fraction part) have negative powers starting from -1.
• Add all the intermediate results to get the final equivalent decimal value.

Converting Between Power-of-Two Bases

• For binary to hexadecimal conversion:
• Group the bits into sets of 4 (from right to left for the integer part, from left to right for the fraction part).
• Pad with zero(s) the left for the integer part, or the right side for the fraction part to complete the last hextet (if not complete)
• Convert each hextet to its corresponding Hexadecimal digit,
• Concatenate the digits.

Signed Integer Representation

• Conversion so far presented involved unsigned numbers ONLY
• Computer systems allocate the high-order bit to represent signed integers to indicate the sign of a number.
• The high-order bit is the leftmost bit and is called the most significant bit, where 0 is positive, and 1 is negative.
• The remaining bits contain the value of the number and those can be interpreted in different ways.
• Signed binary integers may be expressed in three ways:
• Signed magnitude
• One's complement
• Two's complement
• Binary addition has only four rules:
• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 10

Signed Magnitude Representation

• Signed magnitude is the most intuitive method for representing the unsigned numbers.
• The MSB of a binary number is kept as the "sign" of the number:
• MSB = 1: negative number
• MSB = 0: positive number
• The remaining bits represent the magnitude of the numeric value.

Example

• In an 8-bit word signed magnitude system:
• 00000001 has an MSB of 0, making it positive.
• The number corresponds to +1.
• 10000001 has an MSB of 1, making it negative.
• The number corresponds to -1.
• In an N bit word signed magnitude system:
• 1 bit is used for the sign of the number (MSB).
• N-1 bits are used for the magnitude
• The largest integer is 2^(N-1) - 1
• The smallest integer is -(2^(N-1) - 1)

Floating-Point Representation

• Floating-point numbers allow an arbitrary number of decimal places to the right of the decimal point
• They are often expressed in scientific notation for example: 0.125 = 1.25 × 10^-1
• Computers use a form of scientific notation for floating-point representation.
• Numbers written in scientific notation have these components:
• Sign
• Mantissa
• Exponent
• In digital computers, floating-point numbers consist of three parts:
• A sign bit
• An exponent part: representing the exponent on a power of 2
• A fractional part called a significand

Hypothetical "Simple Model"

• The simple model is used to explain the concepts surrounding floating-point numbers.
• In this model:
• A floating-point number is 14 bits in length
• The sign bit field is 1 bit
• The exponent field is 5 bits
• The significand field is 8 bits
• The significand is always preceded by an implied binary point that means the significand always contains a fractional binary value.
• The exponent indicates the power of 2 by which the significand is multiplied.
• Normalization results in a unique pattern for each floating-point number.

Example

• To resolve the problem of synonymous forms, the first digit of the significand always MUST be 1, with no ones to the left of the base point
• Examples, 4.5 = 100.1 x 2⁰ = 1.001 x 2² = 0.1001000 x 2³. The last expression is correctly normalized.
• Conventions include stopping when MSB of the significand is 1
• A biased exponent is more efficient because we can use simpler circuits designed specifically for unsigned numbers when comparing the values of two floating-point numbers.
• An excess-16 bias:
• All negative and positive exponents are added by 16 .
• It is said that the real exponent is replaced by a biased exponent.
• Exponent values less than 16 indicate negative exponent values.
• Exponent values of more than 16 indicate positive exponent values.
• Exponents of all zeros or all ones are typically reserved for special numbers.
• The details of the floating-point representation are determined by the floating-point standard implemented by the computer's hardware or software, including:
• Number of bits for the exponent
• And the specific bias used
• The most used standard for binary floating-point representation is the IEEE 754 standard, of both 32 and 64 bits.
• Specifically, the sign bit, the exponent, and the mantissa/significand are specified in different formats.
• Bias values are pre-defined for each format.
• Single precision IEEE 754 format (32 bits) has 1 bit, 8 bits exponent, 23 bits mantissa
• The bias for the exponent is 2^(8-1)-1 = 2^7-1 = 127
• Double precision IEEE 754 format (64 bits) has 1 bit, 11 bits exponent, 52 bits mantissa
• The bias for the exponent is 2^(11-1)-1 = 2^10-1= 1023

Computer Code

#include <stdio.h>
#include <float.h>
int main() {
printf("Number of bits in float: %d\n", FLT_MANT_DIG);
printf("Number of bits in double: %d\n", DBL_MANT_DIG);
return 0;
}

Debate in Computing

• Selection of programming language is a main debate.
• For application development, the debate still rages, but for system programming, a language other than C is rarely argued for.
• C is closest to the hardware, and provides the least abstraction.
• Most single C statements translate simply to machine code.
• The available data types in C tend to reflect what the hardware directly supports.
• Memory access ia indirection (pointers) provides the programmer with the ability to access all parts of the system.
• The three main tools a system programmer usess are: a shell, a text editor, and a debugger.
• Familiarity with these tools increases programming skill and decreases the time it takes to get programs working properly.

Shell Commands

Listing Files and Directories:

• ls: Lists files and directories in the current working directory.
• ls -l: Lists files and directories in long format, providing detailed information.
• ls -a: Lists all files and directories, including hidden ones (starting with a dot).
• ls /path/to/directory: Lists files and directories in a specified directory.

Creating an Empty File:

• touch filename: Creates an empty file or updates the access and modification timestamps of an existing file.
• Example: touch myfile.txt

Copying Files:

• cp sourcefile destination: Copies a file to a specified destination.
• Example: cp file.txt /path/to/destination/

Moving/Renaming Files:

• mv oldname newname: Moves or renames a file.
• Example: mv oldfile.txt newfile.txt

Creating Directories:

• mkdir directoryname: Creates a new directory.
• Example: mkdir mydirectory

Removing Files:

• rm filename: Removes (deletes) a file.
• Example: rm unwantedfile.txt

Removing Directories:

• rmdir directoryname: Removes an empty directory.
• rm -r directoryname: Removes a directory and its contents recursively.

Searching for Files:

• find /path/to/start/directory -name "filename": Searches for files by name.

Shell Command Examples

Create Folders and Files

• commands to create folders A, B, and C: mkdir A B C
• commands to create files in folder A: touch A/file1.txt A/file2.txt A/file3.txt
• command to List contents of folder A: ls A

Display Folder Contents

• Command to list contents of all folders: ls A B C

Copy Files

• Command to copy file1.txt from folder A to folder B: cp A/file1.txt B/
• Command to list contents of folder B: ls B

Move/Rename Files

• Command to move file2.txt from folder A to folder C and rename it to newfile.txt: mv A/file2.txt C/newfile.txt
• List contents of folders A and C: is A C

Create and Remove Directories

• Command to Create a new directory inside folder A: mkdir A/new_directory
• Command to List contents of folder A to confirm the new directory: Is A
• Remove the empty directory from folder A: rmdir A/new_directory
• List contents of folder A after removal: Is A

Remove Files

• Remove file3.txt from folder A: rm A/file3.txt
• List contents of folder A after removal: Is A

Search for Files

• Search for file1.txt in the entire directory structure: find . -name "file1.txt"