History of computer generations

History of computer generations

fundamental of computer number syatem and logical Gate

What Is A Prototype?

A prototype is a rudimentary working sample, model, mock-up or just a simulation of the actual product based on which the other forms (MVP, final product, and variations) are developed.

The main motive behind prototyping is to validate the design of the actual product. Sometimes, creating a prototype is called materialization as it is the first step of transforming the virtual or conceptualized design into the real physical form.

Draw the schematic diagram of the waterfall model of software development? Also discuss its phases in brief.

(BICT,IV,sem,SAD)

What is WaterFall Model?

The Waterfall Model was first Process Model to be introduced. It is very simple to understand and use. In a Waterfall model, each phase must be completed before the next phase can begin and there is no overlapping in the phases. Waterfallmodel is the earliest SDLC approach that was used for software development.

In “The Waterfall” approach, the whole process of software development is divided into separate phases. The outcome of one phase acts as the input for the next phase sequentially. This means that any phase in the development process begins only if the previous phase is complete. The waterfall model is a sequential design process in which progress is seen as flowing steadily downwards (like a waterfall) through the phases of Conception, Initiation, Analysis, Design, Construction, Testing, Production/Implementation and Maintenance.

As the Waterfall Model illustrates the software development process in a linear sequential flow; hence it is also referred to as a Linear-Sequential Life Cycle Model.

Sequential Phases in Waterfall Model

• Requirements: The first phase involves understanding what need to be design and what is its function, purpose etc. Here, the specifications of the input and output or the final product are studied and marked.
• System Design: The requirement specifications from first phase are studied in this phase and system design is prepared. System Design helps in specifying hardware and system requirements and also helps in defining overall system architecture. The software code to be written in the next stage is created now.
• Implementation: With inputs from system design, the system is first developed in small programs called units, which are integrated in the next phase. Each unit is developed and tested for its functionality which is referred to as Unit Testing.
• Integration and Testing: All the units developed in the implementation phase are integrated into a system after testing of each unit. The software designed, needs to go through constant software testing to find out if there are any flaw or errors. Testing is done so that the client does not face any problem during the installation of the software.
• Deployment of System: Once the functional and non-functio
  nal testing is done, the product is deployed in the customer environment or released into the market.
• Maintenance: This step occurs after installation, and involves making modifications to the system or an individual component to alter attributes or improve performance.These modifications arise either due to change requests initiated by the customer, or defects uncovered during live use of the system. Client is provided with regular maintenance and support for the developed software.

All these phases are cascaded to each other in which progress is seen as flowing steadily downwards (like a waterfall) through the phases. The next phase is started only after the defined set of goals are achieved for previous phase and it is signed off, so the name “Waterfall Model“.

Data Structures and Algorithms ( BICT III sem)

Course Title: Data Structures and Algorithms

Course No. : ICT. Ed. 435                              Nature of course: Theoretical + Practical

Level: B. Ed                                                    Credit Hour: 3 hours (2T+1P)

Semester: Third                                               Teaching Hour: 80 hours (32+48)

                                                                                               

 

1.      Course Description

The purpose of this course is to provide the students with solid foundations in the basic concepts of data structures and algorithms. The main objective of the course is to teach the students how to select and design data structures and algorithms that are appropriate for problems that they might occur. This course is also about showing the correctness of algorithms and studying their computational complexities. This course offers the students a mixture of theoretical knowledge and practical experience. Programming language C will be used for practical work.

2.      General Objectives

The general objectives of this course are as follows:

• To introduce data abstraction and data representation in memory
• To describe, design and use elementary data structures such as stack, queue, linked list, tree and graph
• To decompose complex programming problems into manageable sub-problems
• To introduce algorithms and their complexity

3.   Specific Objectives and Contents

Specific Objectives	Contents
·         Define Data structure and ADT ·         Implement dynamic memory management functions in C ·         Define algorithms, asymptotic notations and mathematical functions	Unit 1: Introduction to Data Structures & Algorithms(6)                                                                    1.1         Data types, Data structure and Abstract date type 1.2         Dynamic memory allocation in C 1.3         Introduction to Algorithms 1.4         Asymptotic notations and common functions Lab: Write  a program to implement dynamic memory management functions(malloc(),calloc(),realloc() and free())
·         Define and implement stack and stack operations ·         Convert expressions in to different forms: infix, prefix and postfix ·         Describe the applications of the stack	Unit 2: Stacks                                                           (8) 2           2.1         Definition 2.2         Stack as an ADT 2.3         Stack operation 2.4         Stack application: Conversion from infix to postfix/prefix expression, Evaluation of postfix/ prefix expressions Lab: Write a program to implement stack operations
·         Define queue and its operations ·         Implement different types of queue ·         Describe the applications of the queue	Unit 3: Queues                                                         (10) 3           3.1         Definition 3.2         Queue as an ADT 3.3         Primitive operations in queue: Enqueue and Dequeue 3.4         Linear Queue, Circular Queue, Priority Queue. Lab: Write a program to implement linear and circular queue operations
·         Define linked list its type and applications ·         Implement linked list operations ·         Implement stack and queue as circular list ·         Describe the applications of the linked list	Unit 4:Lists                                                    (12) 4           4.1         List and ADT 4.2         Array Implementation of Lists 4.3         Linked List 4.4         Types of Linked List: Singly Linked List, Doubly Linked List, Circular Linked List. 4.5         Basic operations in Linked List: creation, node insertion and deletion from beginning, end and specified position 4.6         Stack and Queue as a Linked List Lab-1: Write a program to implement singly and doubly linked list operations Lab-2: Write a program to implement stack and queue as linked list
·         Define recursion. ·         Differentiate between recursion and iteration ·         Implement recursion to solve TOH and Fibonacci series ·         Identify the applications and efficiency of recursion	Unit 5: Recursion                                                       (6) 5           5.1         Principle of recursion 5.2         Comparison between recursion and iteration 5.3         Factorial, Fibonacci sequence,  GCD,  Tower of Hanoi(TOH) 5.4         Applications and Efficiency of recursion Lab-1: Write a program to solve the problem of TOH Lab-2: Write a program to print Fibonacci series Lab-3:Write a program to calculate factorial Lab-4: Write a program to calculate gcd of two numbers
·         Define tree and tree operations ·         Create and manipulate Binary tree, BST, AVL tree and B-Tree ·         Implement Huffman algorithm ·         Identify application areas of tree ·         Describe the applications of the tree	Unit 6: Trees                                                                (10) 6           6.1         Concept and definitions 6.2         Basic operations in binary tree 6.3         Tree height, level and depth 6.4         Binary Search Tree 6.5         Insertion, Deletion, Traversals (pre-order, post-order and in-order ), Search in BST 6.6         AVL tree and Balancing algorithm 6.7         Applications of tree Lab: Write a program to insert, delete, search and display(pre-order, in-order, post-order) items in BST
·         Define sorting and its type ·         Illustrate and implement exchange sort, selection and tree sorting, insertion sort, merge and radix sort. ·         Identify and compare the efficiency of mentioned sorting algorithms	Unit 7: Sorting                                 (12) 7           7.1         Introduction and Types of sorting: Internal and External sort 7.2         Comparison Sorting Algorithms: Bubble, Selection and Insertion Sort 7.3         Divide and Conquer Sorting: Merge, Quick and Heap Sort 7.4         Efficiency of Sorting Algorithms Lab: Write a program to implement:            a) Bubble sort b) Selection sort c) Insertion sort d) Quick sort e) Merge sort f) Heap sort
·         Identify different searching algorithms and implement them. ·         Identify the efficiency of mentioned searching algorithms	Unit 8: Searching                                                     (8) 8           8.1         Introduction to searching 8.2         Search Algorithms: Sequential search, Binary search 8.3         Efficiency of  search algorithms 8.4         Hashing : Hash function and hash tables, Collision resolution technique Lab: Write a program to implement: a)      Sequential search b)      Binary search
·         Define graph, graph terminologies, and graph as a ADT ·         Illustrate transitive closure, Warshall's algorithm and shortest path algorithm ·         Find the shortest path using Dijkstra's Algorithm ·         Explain and implement graph traversal algorithms ·         Define MST and implement prim's, kruskal's and round-robin algorithm ·         Describe the applications of the graph	Unit 9: Graphs                                                        (8) 9           9.1         Definition and Representation 9.2         Graph Traversal: BFS and DFS 9.3         Minimum Spanning Trees: Kruskal and Prims Algorithm 9.4         Shortest Path Algorithms: Dijksrtra Algorithm Lab: Write a program to implement graph traversal algorithms(BFS and DFS)

4.  Instructional Techniques

The instructional techniques for this course are divided into two groups.  First group consists of general instructional techniques applicable to most of the units. The second group consists of specific instructional techniques applicable to particular units.

4.1 General Techniques

Reading materials will be provided to students in each unit. Lecture, Discussion, use of multi-media projector, brain storming, and problem solving methods are used in all units.

4.2 Specific Instructional Techniques

Demonstration is an essential instructional technique for all units in this course during teaching learning process. Specifically, demonstration with practical works will be specific instructional technique in this course. The details of suggested instructional techniques are presented below:

Units	Activities
Unit 1: Introduction to Data Structures & Algorithms	·     Define and Describe the different types of data structures ·     State different operations occurring in data structures ·     Write a program to implement dynamic memory management functions ·     Explain asymptotic notations and complexity on time and space of algorithm ·     Monitor of students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 2: Stacks	·     Illustrate the algorithms of stack operations ·     Lab works in pair to implement stack operations ·     Convert expression in other from one form to another making group and individually ·     Monitoring of students' work by reaching each pair and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 3: Queues	·     Demonstrate queue and queue operations with algorithms ·     Lab work in pairs to implement queue operations ·     Group discussion in advantages and limitations of queues ·     Monitoring of students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 4: List	·     Demonstrate operations of linked list with algorithms ·     Lab work in pairs to implement linked list operations ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 6: Trees	·     Demonstrate operations and types of tree ·     Lab work in pairs to implement BST ·     Trace a working principle of AVL and B-Tree ·     Assign students to create AVL and B-Tree in group ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 7: Sorting	·     Trace the working principle of different sorting algorithms ·     Lab work in pair to implement sorting algorithms ·     Analyze efficiency of sorting algorithms ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 8: Searching and Hashing	·     Demonstrate the working principle of different searching algorithms ·     Lab work in pair to implement searching algorithms ·     Analyze efficiency of searching algorithms ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback
Unit 9: Graphs	·     Explain the graph and graph terminology ·     Solve the practical problems of shortest path and spanning tree using different algorithms ·     Assign student to solve graph problems ·     Lab work in pair to implement graph traversing algorithms ·     Monitor students' work by reaching each student and providing feedback for improvement ·     Presentation by students followed by peers' comments and teacher's feedback

5.      Evaluation :

Internal Assessment	External Practical Exam/Viva	Semester Examination	Total Marks
40 Points	20 Points	40 Points	100 Points

Note: Students must pass separately in internal assessment, external practical exam and semester examination.

5.1   Internal Evaluation (40 Points):

Internal evaluation will be conducted by subject teacher based on following criteria:

1)      Class Attendance                                                                              5 points

2)      Learning activities and class performance                                                5 points

3)      First assignment ( written assignment)                                         10 points

4)      Second assignment (Case Study/project work with presentation )          10 points

5)      Terminal Examination                                                                               10 Points

Total                                                                                              40  points

5.2        Semester Examination (40 Points) 

Examination Division, Dean office will conduct final examination at the end of semester. 1)      Objective question (Multiple choice 10 questions x 1mark)  10 Points 2)      Subjective answer questions  (6 questions x 5 marks)             30 Points

Total                                                                                                   40  points

5.3  External Practical Exam/Viva (20 Points):

Examination Division, Dean Office will conduct final practical examination at the end of semester.

Recommended Books and References

Recommended Books

1           G. S. Baluja, “Data structure Through C, A Practical Approach", Fourth Ed. Dhanpat Rai & Co., 2009-10.

2           Y Langsam , MJ , Augenstein and A.M , Tanenbaum  Data Structures using C and C++ , Prentice Hall India.

References

3           G.W Rowe, Introduction to Data Structure and Algroithms with C and C++ , prentice Hall  India.

4           T.H Corman, C.E Leiserson, R.L Rivest, C Stein, Introduction to Algorithms, 3^rd Ed, The MIT Press Cambridge, Massachusetts London, England,2010

5           R.L Kruse, B.P. Leung, C.L. Tondo, data structure and program Design in C Prentice-Hall India.

6           G. Brassard and P. Bratley fundamentals of Algroithms, Prentice-Hall India.