Week 1 : Assignment 1

Due date: 2022-08-10, 23:59 IST.

Assignment not submitted

1 point

The input given from keyboard is converted to computer understandable unit (bit) by the standard

a) ISO

b) ANSI

c) ASCII

d) EBCDIC

1 point

The execution nature of C program is

a) Event-based

b) Concurrent

c) Multi-threaded

d) Sequential

1 point

Choose the correct statements from the following
i) In high-level language, testing and debugging a program is difficult than assembly language.
ii) C programs are highly portable on any type of operating system platform.
iii) A flowchart is a visual representation of the sequence of steps for solving a problem.
iv) The role of a compiler is to translate source program statements to decimal codes.

a) (i) and (ii)

b) (ii) and (iii)

c) (i), (ii), and (iii)

d) (ii), (iii), and (iv)

1 point

When we write X=Y in C, which of the following statements is valid?

a) X and Y both have same values but different locations.

b) X and Y both have same location and same values.

c) X and Y have different values and same location.

d) X and Y have different values and different locations.

1 point

a) 4

b) 8

c) 16

d) 20

1 point

a) 21

b) 28

c) 30

d) 40

1 point

a) a=4, b=6

b) a=6, b=4

c) a=10, b=2

d) a=2, b=10

1 point

The program which translates high level program into its equivalent machine language program is called

a) a translator

b) a language processor

c) a converter

d) None of the above

1 point

An interpreter reads the source code of a program

a) one line at a time

b) two line at a time

c) complete program in one stroke

d) None of these

1 point

The C language has been developed at

a) IBM, USA

b) Borland International, USA

c) Sun Microsystems

d) AT & T Bell Labs, USA

You may submit any number of times before the due date. The final submission will be considered for grading.

NPTEL | Problem Solving Through Programming In C | Week 1 : Assignment 1 Answers | July-2022

netaji gandi Thursday, July 28, 2022

Graph Implementation in C

A graph is a collection of nodes and edges. These nodes are connected by links(edges).
These edges may be directed or undirected. Moreover these edges can have weights associated with them

So edges can be categorized as :

Directed, weighted edges
Directed, unweighted edges
Undirected, weighted edges
Undirected, unweighted edges

Uses of graphs

Graphs are extremely useful. Look everywhere and one can easily find use of graphs. Listed below are a few of the vast set of practical uses of graphs.

Delhi Metro Rail Map

Each station is a vertex, the distance in between is a weighted edge.

A Maze

Each corner is a vertex, Line between two corners is and edge.

A tournament fixture
Courtesy: http://www.squadtd.com/

Each team is a vertex, match between the teams is an edge.

Kind of graphs

There are numerous classifications and types of graphs available. I have collected a few of those types from various sources and organized a list of types of graphs:

Undirected Graphs

Undirected Graph

Characteristics:

Order of vertices doesn't matter
1-2 is same as 2-1

Directed Graphs

Directed Graph

Characteristics:

Order of vertices does matter
1-2 is not same as 2-1

Vertex labeled Graphs.

Vertex Labeled Graph

Characteristics:

Each vertex contains additional information. e.g {2,orange}, {4,green}

Cyclic Graphs.

Cyclic Graph

Characteristics:

Graph contains at least one cycle.

Edge labeled Graphs.

Edge Labeled Graph

Characteristics:

Edge has labels e.g an edge in the above graph will be represented as {orange,green,{blue,cyan}}

Weighted Graphs.

Weighted Graph

Characteristics:

Each edge has some weight associated with it.

Directed Acyclic Graphs.

Direct Acyclic Graph(DAG)

Characteristics:

Graph has no cycles.

Disconnected Graphs

Disconnected Graph

Characteristics:

Vertices are disconnected

Mixed graph

Mixed Graph

Characteristics:

Some edges may be directed and some may be undirected

Multigraph

Characteristics:

Multiple edges (and sometimes loops) are allowed

Quiver

Characteristics:

Directed graph which may have more than one arrow from a given source to a given target. A quiver may also have directed loops in it.

Representation of graphs:

Fig. 1: An undirected graph

Fig 2: A directed graph

In order to use Graphs programatically , they need to be somehow represented in code. Following are the most widely used methods of representing a graph.

Adjacency Matrix :

For N vertices an adjacency matrix is an NxN array A such that
A[i][j] = 1 if there is an edge E(i,j)
= 0 otherwise

For an undirected graph, A[i][j] = A[j][i]

For weighted graphs,
A[i][j] = weight of the edge, if there is an edge E(i,j)
= a constant representing no edge (e.g a very large or very small value)

For Fig 1, the adjacency matrix would be

The adjacency matrix for directed graph in Fig 2 would be:

Adjacency List :

Adjacency matrix representation consume a lot of memory (O[N²]). If the graph is complete or almost complete(i.e. contains most of the edges between the vertices), then this representation is good to use. But if there are very few edges as compared to number of vertices, it will unnecessarily consume extra space. Adjacency list can handle this situation very optimally.

Every vertex has a linked list of the vertices it is connected with.

Adjacency list for Fig 1 would be:

Adjacency list for Fig 2 would be:

Graphes

netaji gandi Sunday, July 24, 2022

15 GREAT THOUGHTS BY CHANAKYA

1) "Learn from the mistakes of others... you can't live long enough to make them all yourselves!!"

2)"A person should not be too honest. Straight trees are cut first and Honest people are screwed first."

3)"Even if a snake is not poisonous, it should pretend to be venomous."

4)"There is some self-interest behind every friendship. There is no friendship without self-interests. This is a bitter truth."

5)" Before you start some work, always ask yourself three questions - Why am I doing it, What the results might be and Will I be successful. Only when you think deeply and find satisfactory answers to these questions, go ahead."

6)"As soon as the fear approaches near, attack and destroy it."

7)"The world's biggest power is the youth and beauty of a woman."

8)"Once you start a working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest."

9)"The fragrance of flowers spreads only in the direction of the wind. But the goodness of a person spreads in all direction."

10)"God is not present in idols. Your feelings are your god. The soul is your temple."

11) "A man is great by deeds, not by birth."

12) "Never make friends with people who are above or below you in status. Such friendships will never give you any happiness."

13) "Treat your kid like a darling for the first five years. For the next five years, scold them. By the time they turn sixteen, treat them like a friend. Your grown up children are your best friends."

14) "Books are as useful to a stupid person as a mirror is useful to a blind person."

15) "Education is the Best Friend. An Educated Person is Respected Everywhere. Education beats the Beauty and the Youth."

15 GREAT THOUGHTS BY CHANAKYA

netaji gandi

DATA STRUCTURES

Course Objectives:

The objective of the course is to

Introduce the fundamental concept of data structures and abstract data types
Emphasize the importance of data structures in developing and implementing efficient algorithms
Describe how arrays, records, linked structures, stacks, queues, trees, and graphs are represented in memory and used by algorithms

Course Outcomes:

After completing this course a student will be able to:

Summarize the properties, interfaces, and behaviors of basic abstract data types
Discuss the computational efficiency of the principal algorithms for sorting & searching
Use arrays, records, linked structures, stacks, queues, trees, and Graphs in writing programs
Demonstrate different methods for traversing tree.

UNIT I

Data Structures - Definition, Classification of Data Structures, Operations on Data Structures, Abstract Data Type (ADT), Preliminaries of algorithms. Time and Space complexity. Searching - Linear search, Binary search, Fibonacci search. Sorting- Insertion sort, Selection sort, Exchange (Bubble sort, quick sort), distribution (radix sort), merging (Merge sort) algorithms.

UNIT II

Linked List: Introduction, Single linked list, Representation of Linked list in memory, Operations on Single Linked list-Insertion, Deletion, Search and Traversal ,Reversing Single Linked list, Applications on Single Linked list- Polynomial Expression Representation ,Addition and Multiplication, Sparse Matrix Representation using Linked List, Advantages and Disadvantages of Single Linked list, Double Linked list-Insertion, Deletion, Circular Linked list-Insertion, Deletion.

UNIT III

Queues: Introduction to Queues, Representation of Queues-using Arrays and using Linked list, Implementation of Queues-using Arrays and using Linked list, Application of Queues Circular Queues, Deques, Priority Queues, Multiple Queues.

Stacks: Introduction to Stacks, Array Representation of Stacks, Operations on Stacks, Linked list Representation of Stacks, Operations on Linked Stack, Applications-Reversing list, Factorial Calculation, Infix to Postfix Conversion, Evaluating Postfix Expressions.

UNIT IV

Trees: Basic Terminology in Trees, Binary Trees-Properties, Representation of Binary Trees using Arrays and Linked lists. Binary Search Trees-Basic Concepts,

BST Operations:

Insertion, Deletion, Tree Traversals, Applications-Expression Trees, Heap Sort, Balanced Binary Trees-AVL Trees, Insertion, Deletion and Rotations.

UNIT V

Graphs: Basic Concepts, Representations of Graphs-Adjacency Matrix and using Linked list, Graph Traversals (BFT & DFT), Applications-Minimum Spanning Tree Using Prims & Kruskals Algorithm, Dijkstra’s shortest path, Transitive closure, Warshall’s Algorithm.

Text Books:

Data Structures Using C. 2ndEdition.Reema Thareja, Oxford.
Data Structures and algorithm analysis in C, 2nded, Mark Allen Weiss.

ReferenceBooks:
Fundamentals of Data Structures in C, 2nd Edition, Horowitz, Sahni, Universities Press.
Data Structures: A PseudoCode Approach, 2/e, Richard F.Gilberg, Behrouz A.Forouzon, Cengage.
Data Structures with C, Seymour Lipschutz TMH
e-Resources:

http://algs4.cs.princeton.edu/home/
https://faculty.washington.edu/jstraub/dsa/Master_2_7a.pdf