Uses of C

Solving Real Problems

Building Awesomeness

Scoring in UPTU

To get Hacker's Swag

What is C?

• C is the third letter of English alphabets. LOL!
• It’s a computer programming language.
• That means, you can use C to give your computer instructions to follow.

Dennis Ritchie

And this guy created C

What was the result??

Line By Line BreakDown

                       #include<stdio.h>
            

To teach C, how to take input and display output

                       int main{
            

main() is the door through which compiler enters your program

                       printf("Hello World");
            

This tells C to show output

                       return 0;
                       }
            

The program ended

Arrays

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together.

Example:

              A character array in C/C++/JAVA
              char arr1[] = {'g' , 'e' , 'e' , 'k' , 's'};
          

              An integer array in C/C++/JAVA
              int arr2[] = {10 , 20 , 30 , 40 , 50 , 60 , 70};
          

Index of array

Item at i'th index in array is typically accessed

as "arr[i]". For example: arr[0] gives us 10

and arr[3] gives us 40.

Array Decleration

In C, we can declare an array by specifying its type and size or by initializing it or by both.

But How?

1) int arr[10];   (just the declaration)

2) int arr[] = {10, 20, 30, 40}    (declaration as well as initialization without specifying size)

3) int arr[6] = {10, 20, 30, 40}    (declaration, initialization as well as the size is also specified)

A simple program implementing the arrays and strings

           #include<stdio.h>
           #include<string.h>
            int main() 
              { 
              char arr[20],arr2[20]={"_World"}; 
              int len; 
              printf("Enter the first string - "); 
              scanf("%s",arr); 
              len = strlen(arr); 
              printf("Length of this string - %d\n",len); 
              printf("Second string is - %s\n",arr2); 
              strcat(arr,arr2); 
              printf("Combined string is - %s\n",arr); 
              printf("Given 2nd string is - %s\n",arr2); 
              strcpy(arr2,arr); 
              printf("New copied with -  %s\n",arr2); 
              return 0; 
              } 
          

Input:

Hello

Output:

Length of this string - 5

Second string is - _World

Combined string is - Hello_World

Given 2nd string is - _World

New copied with - Hello_World

Pointers

Pointers store address of variables or a memory location.

        General syntax: int *ptr; 
        

To use pointers in C, we must understand below two “unary” operators.

The '&' Operator

The '*' Operator

'&' Operator

To access address of a variable to a pointer, we use the unary operator & (Ampersand) that returns the address of that variable. For example &x gives us address of variable x.

'*'Operator

One more operator is unary * (Asterisk) which is used for two things: To declare a pointer variable. When a pointer variable is declared in C/C++, there must be an * before its name. And to access the value stored in the address we use this unary operator that eventually returns the value of the variable located at the address specified by its operand.

The picture explains it well.

Functions

A function is a set of statements that take inputs, do some specific computation and produces output.

Function Declaration

Function declaration tells compiler about number of parameters function takes, data-types of parameters and return type of function.

Example:

          int func( char, int );
          //A function that takes a char and an int as parameters
          //and returns an integer
        

Line by Line Breakdown of a function

Some Interesting points about functions

1) Every C program has a function called main() that is called by operating system when a user runs the program.

2) Every function has a return type. If a function doesn’t return any value, then void is used as return type.

3) In C, functions can return any type except arrays and functions. We can get around this limitation by returning pointer to array or pointer to function.

Parameters passing to functions

Here you have:

• The parameters passed to function are called actual parameters. For example, in the above program 10 and 20 are actual parameters.
• The parameters received by function are called formal parameters. For example, in the above program x and y are formal parameters

There are two most popular ways to pass parameters

• Pass By Value
• Pass By Reference

Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

Example: A function to return factorial of a number

                        int fact(int n)
                          {
                            if (n <= 1) // base case
                            return 1;
                            else    
                            return n*fact(n-1);     
                          }
      

That was all about functions

Searching Algorithm

A search algorithm is the step-by-step procedure used to locate specific data among a collection of data

Linear Search

Binary Search

In this approach the array keeps on dividing untill it finds the key element

Sorting

Types of Sorting

• Bubble
• Selection
• Insertion

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

Structure & Typedef

Declaring a Structure:

      struct name {

        structure element 1;
        structure element 2;
        structure element 3;
        ---
        ---

    };
    

Typedef

Typedef keyword is used to assign a new name to a type. This is used just to prevent us from writing more.

Syntax:

      typedef current_name new_name;
    

Example:

      #include <stdio.h> 
        int main() { 
            typedef long l;
            l i = 5; 
            printf("i = %d\n", i);
            return 0; 
        }
    

Time Complexity

Time complexity is a concept that deals with the quantification of the amount of time taken by a set of code or algorithm to process or run as a function of the amount of time. In other words it describes the amount of time it takes to run an algorithm

Example:

Imagine a classroom of 100 students in which you gave your pen to one person. Now, you want that pen. Here are some ways to find the pen and what the O order is

O(n2)

You go and ask the first person of the class, if he has the pen. Also, you ask this person about other 99 people in the classroom if they have that pen & So on, This is what we call O(n2).

O(n)

Going and asking each student individually is O(N).

O(n) is Big O Notation and refers to the complexity of a given algorithm. n refers to the size of the input

O(logN)

O(log n): Now I divide the class in two groups, then ask: “Is it on the left side, or the right side of the classroom?” Then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one student who has your pen. This is what you mean by O(log n).

Number theory

a) Modular Arithmetic

When one number is divided by another, the modulo operation finds the remainder. It is denoted by the %symbol.

b) Modular Exponentiation

Exponentiation is a mathematical operation that is expressed as xn and computed as xn = x⋅x⋅...⋅x (n times).

c) Greatest Common Divisor (GCD)

The GCD of two or more numbers is the largest positive number that divides all the numbers that are considered. For example, the GCD of 6 and 10 is 2 because it is the largest positive number that can divide both 6 and 10.

d) Extended Euclidean algorithm

This algorithm is an extended form of Euclid’s algorithm. GCD(A,B) has a special property so that it can always be represented in the form of an equation i.e. Ax+By=GCD(A,B).

Modular multiplicative inverse

What is a multiplicative inverse? If A.B=1, you are required to find B such that it satisfies the equation. The solution is simple. The value of B is 1/A or A−1. Here, B is the multiplicative inverse of A. What is modular multiplicative inverse? If you have two numbers A and M, you are required to find B such it that satisfies the following equation: (A.B)%M=1 Here B is the modular multiplicative inverse of A under modulo M.

Basic Bit Manipulation

Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a byte.

Prime Sieve

In mathematics, the sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.[1] This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.