CS301 Midterm Solved Subjective with References by Ashfaq

This version of file contains: ·  Content of the Course ·  FAQ updated version.(These must be read once because some · very basic definition and question are being answered) ·  Glossary updated version.(These must be read once because · some very basic terms are being explained which you even · might not found in the book)

 Solved Past Assignment Selected for MID Term. (Coming Soon)

 Solved Question From Mid-Term Papers (Coming Soon) ·  MCQs GIGA File (in Compilation) · (will be shared as Separate File) (Coming Soon)

Note: Use Table of Content to view the Topics, In PDF mode , you can check Bookmarks menu. I have tried to provide maximum data on less pages. SOLVED PAST ASSIGNMENTS (UPDATED VERSION).................................................................................................................... 12

MID-TERM PAST PAPERS (UPDATED VERSION) ......................................................................................................................... 12

SOLVED: ................................................................................................................................................................................... 12 UNSOLVED: ............................................................................................................................................................................... 12

Introduction, the Array data type, the List abstract data type (ADT), Linked lists, Stacks, Queues, Trees, AVL Trees ,Huffman encoding , The Heap ADT, Priority queue implementation using the heap ADT, The Disjoint Sets ADT, The Table ADT, implementation using arrays, Skip lists, Table ADT implementation using Hashing, Collision resolution in Hashing, Other uses of Hashing, Sorting, and Selection sort, insertion sort, bubble sort algorithms, Divide and conquer strategy: merge sort, quick sort.

Define Abstract Base Class?

Answer: An abstract base class is C++ 's way of defining an interface. It is a class which declares that all child classes derived from it must implement a certain set of methods. It is abstract because an instance of the abstract base class may not be created (only concrete implementations of the interface may be instantiated).

What is Instance?

Answer: A class is a definition of a set of data and member functions. When space for the data is actually allocated, we say that a member of the class has been instantiated. The instantiation is called an instance of the class. Each instance has its own set of data (there is also a mechanism in C++ to define data that is only allocated once per class, and shared amongst all instances of the class).

Define Concrete Class?

Answer: A concrete class is a class that is not abstract. An instance of the class may be created, which contains copies of all the data members of the class, and member functions which may be invoked.

Name the Properties of a Binary Tree?

Answer: Since binary tree nodes can only have a maximum of two children, this fact introduces several properties that do not make sense on general trees. There are three important properties that a binary tree can have: fullness, balance, and leftness.

Define Binary Search Trees (BST) with example?

Answer: The most popular variation of the Binary Tree is the Binary Search Tree (BST). BSTs are used to quickly and efficiently search for an item in a collection. Say, for example, that you had a linked list of 1000 items, and you wanted to find if a single item exists within the list. You would be required to linearly look at every node starting from the beginning until you found it. If you're lucky, you might find it at the beginning of the list. However, it might also be at the end of the list, which means that you must search every item before it. This might not seem like such a big problem, especially nowadays with our super fast computers, but imagine if the list was much larger, and the search was repeated many times. Such searches frequently happen on web servers and huge databases, which makes the need for a much faster searching technique much more apparent. Binary Search Trees aim to Divide and Conquer the data, reducing the search time of the collection and making it several times faster than any linear sequential search.

Define Heap?

1. A portion of memory reserved for a program to use for the temporary storage of data structures whose existence or size cannot be determined until the program is running. To build and use such elements, programming languages such as C and Pascal include functions and procedures for requesting free memory from the heap, accessing it, and freeing it when it is no longer needed. In contrast to stack memory, heap memory blocks are not freed in reverse of the order in which they were allocated, so free blocks may be interspersed with blocks that are in use. As the program continues running, the blocks may have to be moved around so that small free blocks can be merged together into larger ones to meet the program's needs.
2. A complete binary tree in which the value of any node is not exceeded by the value of either of its children.

Define Binary Trees?

Answer: As the name implies, a binary tree is simply a recursively-defined tree that can have a maximum of two children. The two children are commonly given the names left child and right child, and binary trees have an additional traversal called the in-depth traversal. Binary trees are used for many things, ranging from efficient searching techniques, data compression, and even arithmetic expression parsers (simple compilers). Note that some people refer to binary trees as ‘B-Trees’, which is incorrect! BTrees are a special kind of multi-data per node tree used for advanced balancing algorithms, and Apple Macintoshes even use B-trees for their file systems. Be careful to not call a ‘Binary Tree’ a ‘B-Tree’!

How can we differentiate among database, data communication and data structure?

Answer: Database: A collection of data arranged for ease and speed of search and retrieval. Data Communication: Communications involves data transfer from one computer to another through a communications medium, such as a telephone, microwave relay, satellite link, or physical cable. Two primary methods of computer communications exist: temporary connection of two computers through a switched network, such as the public telephone system, and permanent or semipermanent linking of multiple workstations or computers in a network. The line between the two is indistinct, however, because microcomputers equipped with modems are often used to access both privately-owned and public-access network computers.

Data Structure: An organizational scheme, such as a record or array, that can be applied to data to facilitate interpreting the data or performing operations on it.

Describe 32bit programming and 16 bit programming and difference between them? Is there 64 bit programming available?

Answer: 16 bits programming was done using 16-bits registers which is now obsolete. Now 32-bit programming is done using 32-bits registers which is now a days used for constructing windows application. These are the cases of IBM compatible PCs which consists of 32 bits register until now. There are other architecture which are consists of 64 bits registers e.g. Sun Sparc Machines are 64 bits Machines. So it depends upon the architecture of the Machine and softwares are written accordingly.

What is difference between Pseudo code and Algorithm?

Answer: Pseudo code:Any informal, transparent notation in which a program or algorithm description is written. Many programmers write their programs first in a pseudocode that looks much like a mixture of English and their favorite programming language, such as C or Pascal, and then translate it line by line into the actual language being used. Algorithm:A step-by-step problem-solving procedure, especially an established, recursive computational procedure for solving a problem in a finite number of steps.

What is external node?

Answer: A terminal or "bottom" item of a tree,i.e.an item with no child known as external node.

How Data Compression Works?

Answer: The goal of data compression is to represent an information source (e.g. a data file, a speech signal, an image, or a video signal) as accurately as possible using the fewest number of bits.

Differentiate between Greedy Algorithm and Huffman Algorithm?

Answer: Greedy Algorithm:An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems.