531 final Flashcards
Output of the following program?
#incude <studio.h>
#include <stdib.h>
struct name {
int a;
};
int main(){
struct name *ptr;
int i,n=5;
ptr(struct name*)malloc(n*sizeof(struct name));
for(i=0;i<n; ++i{
(ptr+i)->a=n-i;
}
printf("%d\n", (ptr+3)->a);
free(ptr);
return 0;
}</stdib.h></studio.h>
2
using ascii chart what’s the output?
#incude <studio.h>
int main(){
char ch[6] = "CS531";
printf("%x", ch[2]);
return 0;
}</studio.h>
35 (%x is hexadecimal)
incude <studio.h></studio.h>
#include <stdib.h>
struct st{
int a[5];
char ch[10];
};
int main(void){
struct st obj;
struct st *stobj = &obj;
obj.a[3] = 7;
stobj->a[3] = 5;
strcpy(obj.ch, 'Midterm");
stobj->ch[1] = 32;
printf("\nobj.a[3]==%d obj.ch==%s \n", obj.a[3],obj.ch);
return 0;
}</stdib.h>
obj.a[3]== 5 obj.ch == M dterm
(32 is spacebar cuz dec in ascii)
output using ascii chart?
#incude <studio.h>
#include <stdib.h>
int main(int argc, char *argv[]){
if(argc ==1)
{
printf("Program name: %s\n", argv[0]);
}
else{
printf("%x\n"argv[1][2]);
}
return 0;
}</stdib.h></studio.h>
$ gcc MT c-o MT
$./MT CS531
35 (MT is argc and CS531 is argv, therefore you get [1][2] of argv which is 5 and then turn it into hexadecimal)
find output:
#incude <studio.h>
int main(){
char array[10] = "CS 531";
char *a_ptr = array;
int x=4;
printf("%s",a_ptr+x);
return 0;
}</studio.h>
31(a_ptr+x means it starts printing at 31 since x = 4)
time complexity for traversing a singly linked list?
O(N)
find output:
#incude <studio.h>
int main(){
int x[3][4] =
{
{110,161,302,453},
{11,16,30,45},
{1100,1600,3000,4500}
};
int y,z;
for{y=2;y>0;y--){
for(z=0;z<4;z+=2){
printf("$d\n",x[y][z]);
}
}
return 0;
}</studio.h>
1100,
3000,
11,
30
include <studio.h></studio.h>
int main(void){
int n=28,
lcv,
flag;
for(lcv=2, flag=1; lcv<=(n/2);lcv++){
if((n%lcv)==0){
if(flag)
printf(“%d \n”, n);
flag = 0;
printf(“%d\n”,lcv);
}
}
}
28
2
4
7
14
incude <studio.h></studio.h>
int main(){
int s=0,x,y,z=3;
for(x=0;x<z;x++)
for(y=x;y<z; y++)
s+= x*y;
printf(“%d\n”,s);
return 0;
}
7
get output, assume push pop and isEmpty as Stack functions (first in last out)
int main(){
int num1,quotient,rem;
num1 = 41;
quotient = num1;
while(qutient!=0){
rem = quotient%3;
quotient = quotient/3;
push(rem);
}
while(!isEmpty()){
printf(“%d”,pop());
}
return 0;
}
1112
using a stack data structure, the pop operationmay be categorized as having what computational time value?
O(1)
recursion base case
prove the statement true for some specific value or
values of n (usually 0 or 1).
induction step
assume the statement to be true for all positive
integers less than n, then use that fact to prove it true for n
BST depth
number of edges from the root to the node
BST height
number of edges from the node to its deepest leaf.
full binary tree
each node has either 0 or 2 children
complete bst
a binary tree which is completely filled with the possible exception of the bottom level which is filled left to right
preorder traversal
visit parent first then left and right children ( in that order)
inorder traversal
visit left child then parent and then the right child
postorder traversal
visit left child, then right child, and then parent
logarithms
each level has max 2^n amount of nodes. n being the height level from root.
BST vs Binary tree
Binary tree isn’t ordered. BST is.
each node contains one key
the keys in the left are less than the parent. the keys in the right are greater than the parent. no duplicates
deletion in BST
leaf nodes are trivial.
if the node being deleted only has one child then the node is replaced by the only child.
if the nose being deleted has two children, replace the deleted node with its inorder successor or inorder predecessor
pass by value vs pass by reference (int vs int *)
pass by value indicates a copy of the data that is passed to the function. any changes to the parameter have no affect on data in the calling function.
Pass by reference involves use of a reference parameter. it referes to the original data, therefore any changes made to the original data will be passed into the original variable.
01000011 convert into hexadecimal
split into 4 bit parts (0100) (0011) and then convert to decimals (12^2 = 4), (12^1 +1*2^0 = 3) therefore you get 0x43 (0x just says it’s hexadecimal). using ascii chart it becomes C
01000011 convert into decimal
(12^0 +12^1+1*2^6 = 67) = C
HEAP
Variables allocated on the heap, or dynamic variables, have their memory allocated at run time . This memory
remains allocated until explicitly freed by the program and, as a result, may be accessed outside of the block in which it was
allocated.
structure vs union
Structures in C is a user-defined data type available in C that allows to combining of data items of different kinds. Structures are used to represent a record.
Union in C is a special data type available in C that allows storing different data types in the same memory location. You can define a union with many members, but only one member can contain a value at any given time. Unions provide an efficient way of using the same memory location for multiple purposes.
Big and Little Endian
Big-Endian: the most significant byte is stored at the lowest
memory address.
Little-Endian: the least significant byte is
stored at the lowest memory address.
Bubble sort
sorting algorithm that iteratively
steps through an array while comparing
adjacent elements and swapping them if they
are in the wrong order. The iteration loops
until the array is sorted O(n^2)
strcmp
function compares two
strings s1 and s2. It returns an
integer less than, equal to, or greater
than zero if s1 is found, respectively,
to be less than, to match, or be
greater than s2.
fgets
reads a character string from the specified stream (use stdin for keyboard input) and stores it into the
string pointed to by str. It stops when either (n-1) characters are read, the newline character is read, or the end-of-file is reached, whichever
comes first. If any characters are read and there is no error, a null byte (ascii 0, or ‘\0’) is appended to end the string.
scanf vs fgets
Recall from lecture that while reading from the keyboard using scanf(), the ‘\n’ is
not read in from the input buffer
strncmp
function is similar,
except it compares only the first (at
most) n bytes of s1 and s2
strchr
function returns a pointer to the first occurrence of the character c in the string s.
arrays and pointers
&a[1] is equivalent to (a+1) AND, a[1] is equivalent to *(a+1).
&a[2] is equivalent to (a+2) AND, a[2] is equivalent to *(a+2).
&a[3] is equivalent to (a+3) AND, a[3] is equivalent to *(a+3)
Bit Operations:
c = FLAG1 & FLAG2; FLAG1 = 00111100
printf(“Line 1 - Value of c is %d\n”, c ); FLAG2 = 00001101
00001100 = 12
c = FLAG1 | FLAG2;
printf(“Line 2 - Value of c is %d\n”, c );
c = FLAG1 ^ FLAG2;
printf(“Line 3 - Value of c is %d\n”, c );
c = ~FLAG1;
printf(“Line 4 - Value of c is %d\n”, c );
c = FLAG1 «_space;2;
printf(“Line 5 - Value of c is %d\n”, c );
c = FLAG1»_space; 2;
printf(“Line 6 - Value of c is %d\n”, c );
The & (bitwise AND) in C takes two numbers as operands and does AND on every bit of two numbers. The result of AND is 1 only if both bits are 1.
The | (bitwise OR) in C takes two numbers as operands and does OR on every bit of two numbers. The result of OR is 1 if any of the two bits is 1.
The ^ (bitwise XOR) in C takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different.
The «_space;(left shift) in C takes two numbers, the left shifts the bits of the first operand, and the second operand decides the number of places to shift.
The»_space; (right shift) in C takes two numbers, right shifts the bits of the first operand, and the second operand decides the number of places to shift.
The ~ (bitwise NOT) in C takes one number and inverts all bits of it.
means either one can have one
&Mask
removes removes the bits that are 0 in mask
AVL tree
self balancing binary search tree, because it’s self balancing all operations are O(logn) (insertion,removal, lookup)
avl balance factor
difference between left and right subtrees, must be (-1,0,1) else it has to balance (<-1 means left rotation, >1 means right rotation)
rotations
look at avl tree rotations powerpoint
int fstat(int fildes, struct stat *buf)
The fstat() function shall obtain information about an open file associated with the file descriptor fildes, and shall write it to the area pointed to by buf.
Graph
is a data structure that consists of a vertex set and an
edge set. In other words, a graph contains a finite set of vertices (nodes) and a finite set of ordered pairs (edges).
vertex degree
how many edges it connects to
Inode
a complex data-structure that contains all the
necessary information to specify a file. It includes the memory
layout of the file on disk, file permissions, access time, number
of different links to the file etc
Global (Open) File table
contains information that is global to
the kernel, such as the byte offset in the file where the user’s
next read/write will start along with the access rights allowed
to the process from which the file was opened
Process File Descriptor table
Local to every process and
containing information such as the identifiers of the files
opened by the process. Whenever, a process creates a file, it
receives an index from this table known as a File Descriptor
extra information about inodes, global file tables and descriptor tables
A file descriptor is not directly related to an inode.
* inode numbers are like pointers within the file system, and are stored
within the file system itself.
* A directory entry is the combination of a name and an inode.
* File descriptor numbers, are not stored anywhere within the file system.
They are dynamically generated by the kernel when you call open(), etc… .
They are pointers into the kernel’s file descriptor table for a particular
process.
* An inode number always refers to an entity on a device. A file descriptor
may also refer to an anonymous pipe, a socket, or some other resource.
* Every file or directory on a given device has a unique inode number. If two
files on the same device have the same inode number, then they are in fact
the same file with two different names (i.e. hard link). On the contrary, a file
or directory may be opened several times by the same process or by
different processes, and thus have many different file descriptors.
Additionally, files/directories that are not currently open by any process do
not have any file descriptors referring to them.
* A valid file descriptor is associated with file mode flags and offset, however
it does not contain any metadata associated with the file itself, such as
timestamps or Unix permission bits. An inode contains timestamps and Unix
permission bits, but no file mode flags or offset.
Hard link vs Symbolic (soft) link
hard link may be viewed as a pointer to an inode.
A symbolic link (also known as a soft link) is similar to a file shortcut. It may be viewed as a special file whose content is
essentially a pathname to another file.
Whereas multiple hard links may point to the same inode. Each symbolic link contains a separate inode value that points to the
original file. If the original file is deleted, the symbolic link is rendered useless and is referred to as a hanging link.
Since each hard linked file is assigned the same inode value as the original, they reference the same physical file location. This
allows hard links to remain intact even if the original (or linked) file is moved throughout the file system
Unix processes
A process may be described as a program in execution
Parent process: Every process (except kernel process 0) is created from within another process by use of the system call fork(). The
process that invoked fork() is the parent process. The newly created process is the child process. Every process (again, with the
exception of kernel process 0) has only one parent process, but may have many child processes.
* Child process: A process created by the parent process using fork(). The child process enters the world as a copy of the parent.
* Daemon Process: A non-interactive, typically long-running process which runs in the background and has no controlling terminal.
The role of Daemon processes is frequently to answer service requests. Examples include: httpd, sshd, inetd, lpd,named, anacron…
* Orphan process: A process whose parent process has terminated, yet it remains running itself.
* Zombie process: When a child process terminates, its entry in the process table remains until its parent process fetches the status
information of the terminated child. Until this fetch occurs, the terminated child process is referred to as a zombie process.
fork
creates a new process by duplicating the calling process. The new process is referred to as the child process. The calling process is referred to as the
parent process. The child process and the parent process run in separate memory spaces. At the time of fork() both memory spaces have the same content.
Memory writes by one of the processes do not affect the other
Signal Handling
A Signal is a notification, a message sent by either the operating system or
some application to your program (or one of its threads).
Each signal is identified by a number, from 1 to 31. A robust program needs
to handle signals in order to allow asynchronous events (interrupts) to be
delivered to the application.
A user hitting ctrl+c, a process sending a signal to kill another process, etc, are
all such cases where a process needs to handle signals.
In Linux, every signal has a name that begins with characters SIG. For example
:
A SIGINT signal is generated when a user presses ctrl+c. This is the way to
terminate programs from terminal.
A SIGALRM is generated when the timer set by alarm function goes off.
A SIGABRT signal is generated when a process calls the abort function
alarm(), getpid(), getppid()
alarm sends a signal to the child processes.
getpid gets the process id
getppid gets the parant’s process id
pause(
causes the calling process (or thread) to sleep until a signal is delivered that either terminates the process or
causes the invocation of a signal-catching function
time
d runs the specified program command with the given arguments.
When command finishes, time writes a message to standard error giving timing statistics about this program run
Hash table
is based on an array structure. In Open Hashing (or Chaining), A hash function takes a key as input and provides an array index
into which we store a reference to the key’s associated value
Closed Hashing
all elements are stored within the hash
table itself. A dataset involving N key/value pairs
requires a hash table (array) of size greater than or
equal to N. Table size can be increased by copying old
data if needed, however that is time consuming and
therefore not desirable
linear probing
searching sequentially
quadratic probing
Quadratic probing is an open-addressing scheme where we look for the i2‘th slot in the i’th iteration if the given hash value x collides in the hash table
Let hash(x) be the slot index computed using the hash function.
If the slot hash(x) % S is full, then we try (hash(x) + 11) % S.
If (hash(x) + 11) % S is also full, then we try (hash(x) + 22) % S.
If (hash(x) + 22) % S is also full, then we try (hash(x) + 3*3) % S.
This process is repeated for all the values of i until an empty slot is found
Hash Function for Strings
A common (although inefficient) way to compute a
numeric hash value for a string is to sum the ASCII values
of the characters within the string followed by computing
the modulus of this sum against the size of the array.
wait
execution
of the parent is suspended until the child is
terminated
execvp
Using this command, the created child process does not have to run the same program as the parent process does. The exec type system calls allow a process to run any program files, which include a binary executable or a shell script .
execlp() or execl()
functions and they will perform the same task i.e. replacing the current process the with a new process
envp
his argument is an array of pointers to null-terminated strings and must be terminated by a null pointer. The other functions take the environment for the new process image from the external variable environ in the calling process
grep
searches the named input files (or standard input if no
files are named) for lines containing a match to the given
pattern. By default, grep prints the matching lines
tty
stands for teletype
/dev/tty
stands for the controlling terminal of the current process
dup()
creates a copy of the file descriptor oldfd
Unix Pipes
A pipe is a method of connecting the standard output of one process to the standard input of another. It provides a method for oneway communications (i.e. half-duplex) between processes. Data traveling through the pipe moves through the kernel. Under Linux,
pipes are actually represented internally with a valid inode. Since a child process will inherit all open file descriptors from the parent,
pipes provide a basis for interprocess communication (between parent and child).
waitpid
waits until the supplied processing id stops
WIFEXITED(),
WIFSIGNALED(), WIFSTOPPED(),
WIFCONTINUED(), WIFEXITED()
wait and if it does the next part then continue
ftok
convert a pathname and a project identifier to a System V
IPC key
Termination Signals
The SIGKILL signal is used to cause immediate program termination. It cannot be handled or ignored, and is
therefore always fatal. It is also not possible to block this signal.
The SIGINT (“program interrupt”) signal is sent when the user types the INTR character (normally C-c).
The SIGQUIT signal is similar to SIGINT, except that it’s controlled by a different key—the QUIT character,
usually C-\ and produces a core dump when it terminates the process
The SIGSTOP signal stops the process. It cannot be handled, ignored, or blocked.
The SIGTSTP signal is an interactive stop signal. Unlike SIGSTOP, this signal can be handled and ignored
System V Shared Memory
has a shared memory across processes that can share data between them
shmget
allocates a System V shared memory segment or retrieves an identifier
for an already existing memory segment.
shmat
attaches the given shared memory segment to the memory space of
the calling process.
void *shmat(int shmid, const void *shmaddr, int shmflg);
Shmdt
shared memory detach operation
int shmdt(const void *shmaddr)
Function Pointers
A function pointer is a pointer variable that stores the address of a
function’s executable code. Function pointers may be used to call
functions and to pass functions as arguments to other functions. Pointer
arithmetic cannot be performed on function pointers
POSIX Threads
Threads within the same process share resources.
Changes made by one thread to shared system resources (such as opening/closing a file) will be seen by all other
threads. Multiple threads may read and write to the same memory location, thus requiring explicit synchronization.
Thread-safe code refers to an application’s ability to execute multiple threads simultaneously without corrupting
shared data or creating race conditions.
Thread management
Routines that work directly on threads - creating, detaching, joining, etc. They also include
functions to set/query thread attributes (joinable, scheduling etc.)
Mutexes:
mutex is an abbreviation for mutual exclusion. A mutex is a locking mechanism that allows only one
thread to access a critical section of code at a time, thus enabling synchronization of threads while avoiding issues
such as race conditions. Mutex functions provide for creating, destroying, locking and unlocking mutexes. These
are supplemented by mutex attribute functions that set or modify attributes associated with mutexes.
Condition variables
: A condition variable uses signaling to enable the blocking of a thread until notified to resume.
Condition variables are used in conjuction with a mutex.
Synchronization
Routines that manage read/write locks.
htons()
host to network short
htonl()
host to network long
ntohs()
network to host short
ntohl()
network to host long
socket
is the endpoint in a two-way
communication link between two programs
running on a network. k. For our discussion, this
endpoint is a combination of an IP address and
a port number. The socket is bound to a port
number in order to identify the application for
which the associated data is destined. Typically,
only the receiving socket (server) needs to
explicitly bind the socket to a port number
SOCK_DGRAM
Supports datagrams (UDP)
(connectionless, unreliable messages of a fixed maximum
length)
The protocol specifies a particular protocol to be used with
the socket. Normally only a single protocol exists to support a
particular socket type within a given protocol family, in which
case protocol can be specified as 0
int bind(int sockfd, const struct sockaddr *addr,
socklen_t addrlen);
bind() assigns the address specified by addr to the socket
referred to by the file descriptor sockfd
ssize_t recvfrom()
may be used to receive data on a socket
whether or not the socket is connection-oriented.
Canonical mode
This is the normal processing mode for
terminals. Data are accumulated in a line editing buffer,
and do not become “available for reading” until line
editing has been terminated by sending a line delimiter
character.
Non-canonical (raw) mode
: Data are accumulated in a
buffer and become “available for reading” according to
the values of two input control parameters, the
c_cc[MIN] and c_cc[TIME] members of the termios data
structure. In other words, Non-Canonical Input
Processing will handle a fixed amount of characters per
read, and allows for a character timer. This mode should
be used if your application will always read a fixed
number of characters, or if the connected device sends
bursts of characters.
ioctl()
manipulates the underlying
device parameters of special files. In particular,
many operating characteristics of character special
files (e.g., terminals) may be controlled with ioctl()
requests. The argument d must be an open file
descriptor.
fileno(
examines the argument stream and returns its integer
descriptor.
sa_family_t
type of the address structure – typically unsigned short
AF_UNIX Local communication
AF_INET IPv4 Internet protocols
AF_INET6 IPv6 Internet protocols
in_port_t
Equivalent to the type uint16_t as defined in <inttypes.h></inttypes.h>
unsigned short htons(unsigned short hostshort)
This function converts 16-bit (2-byte) quantities from host byte
order to network byte order.
unsigned long htonl(unsigned long hostlong)
This function converts 32-bit (4-byte) quantities from host byte order
to network byte order.
unsigned short ntohs(unsigned short netshort)
This function converts 16-bit (2-byte) quantities from network byte
order to host byte order
unsigned long ntohl(unsigned long netlong)
This function converts 32-bit quantities from network byte order to
host byte order.
output?
#include <stdio.h>
#include<string.h>
void what();
char string1[20] = "CS531";
char string2[20] = "GMU";</string.h></stdio.h>
int main(){
what();
printf(“%s”,string1);
return 0;
}
void what(){
char s,t;
s = string1;
t = string2;
while(*s){
s = s+1;
} s = s-3;
*s = t;
while(s){
s++;
t++;
*s = *t;
}
return;
}
Answer is “CSGMU”
first while loop moves s from pointing at C to pointing to the null character at the end. Then it moves the pointer 3 steps back to point to 5. then s=t meaning 5 is replaced with G. keep looping through the last while until there is no more space in string1, therefore “CSGMU”
include <stdio.h></stdio.h>
for the following program array == 0x2b9e
int main(){
char array[10], *ptr;
ptr = &array[5];
printf(“%p”, ptr);
return 0;
}
answer:0x2ba3
the array value at the beginning points to array[0] since char array has allocated 10 memory spots.
ptr=&array means it points to the address of array, and since it’s array[5] you go up 5 spaces: b9f, ba0,ba1,ba2,ba3. therefore you get 0x2ba3
