MCA-4sem Computer Graphics and Animation
MCA-4sem Computer Graphics and Animation
MCA-4sem Computer Graphics and Animation
COURSE RECORD
Faculty Name:
Semester: Fourth
6. Course Syllabus 2
7. CO-PO Mapping 3
10.Lecture Plan 6
14.Assignment Questions 13
19.Attendance Register 27
Mission:
M1: Promote intellectual and skilled human capital generating employment and
entrepreneurship.
M2: Be educational center of excellence of multi ethnicity and diversity.
M3: Establish as technology driven teaching learning institution.
M4:Provide world class platform for research and innovation.
M5: Inculcate social, environmental, heritage values
Mission:
PEO3 Exhibit skills of designing and production of different products based on principles
of Computer Science.
PEO4 Exhibit strong, independent learning, analytical and problem-solving skills with
special emphasis on design, communication, and ability to work in teams.
PEO5. To pursue higher education and research in this reputed our institute at national and
international importance by level quality teaching and its accountability.
PO 3. Students in the computer science majors will be able to apply and effectively
communicate practical knowledge and development methodology and data
analysis in both written and oral forums.
Students will be able gathering information, design, programming, testing,
PO 4.
configuration and installation for investigating complex problems in the software
industries.
Students will be able to decide and apply appropriate tools and techniques.
PO 5.
Students will be able to justify conceptual and application-oriented skills of IT
PO 6.
Application in Business context practices.
Program Specific Outcomes for Bachelor in Computer Application set by Faculty in the
Department of Computer Science are as follows:
Course Outcomes:
COURSE SYLLABUS
MODULE 2: 10 L L4
Advanced Data Structure: Red-Black Trees, Augmenting Data Structure.
B Trees, Binomial Heaps, Fibonacci Heaps, Data Stricture for Disjoint
Sets.
MODULE3: 10 L L3
Advanced Design and Analysis Techniques: Dynamic programming,
Greedy Algorithm, Backtracking, Branch-and-Bound, Amortized Analysis
MODULE 4: 9L L6
Elementary Graph Algorithms, Breadth First Search, Depth First Search,
Minimum Spanning Tree, Kruskal’s Algorithms, Prim’s Algorithms, Single
Source Shortest Path, All pair Shortest Path, Maximum flow and Traveling
Salesman Problem.
MODULE 5: 8L L4
Randomized Algorithms, String Matching, NP-Hard and NP-Completeness,
Approximation Algorithms.
Text Books
1. Patrick Naughton and Herbert Schildt: The Complete Reference Java, Latest Edition, Tata
McGraw-Hill.
References
1. Hans Bergstan: Java Server Pages.
2. Bill Siggelkow, S P D O’Reilly: Jakarta Struts, Cookbook.
3. Murach: Murach’s beginning JAVA JDK 5, SPD
CO PO MAPPING
Tula's Institute, Dehradun Page9
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 3 2 1 1 2 1 0 0 0 0 1 2
CO2 3 3 2 1 2 1 0 0 1 1 2 2
CO3 3 2 2 1 2 1 0 0 1 0 2 2
CO4 2 2 2 1 2 1 0 0 1 2 2 2
CO5 2 2 0 0 0 1 0 0 0 1 1 2
13/15 11/15 7/15 4/15 8/15 5/15 0/15 0/15 3/15 4/15 8/15 10/15
88 73 46 26 53 33 0 0 20 26 53 61
3 2 1 0 1 1 0 0 0 0 1 2
1- LOW45-59
2-MODERATE 60-75
3-HIGH76-100
3. 20-Aug-18
L-3 Asymptotic notations
4. 22-Aug-18
T1 Asymptotic notations
5. 23-Aug-18
L-4 Recurrence relation
6. 24-Aug-18
L-5 Insertion sort, Merge sort
7. 27-Aug-18
L-6 Heap sort
8. 29-Aug-18
L-7 Quick sort
9. 30-Aug-18
L-8 Liner time sorting
10. 31-Aug-18
L-9 Counting sort
11. 5-Sep-18
L-10 Radix sort
12. 6-Sep-18
L-11 Bucket sort
16. 13-Sep-18
L-14 Binomial Heaps
19. 19-Sep-18
L-17 Disjoint Sets
20. 20-Sep-18
T3 Class test 1
23. 26-Sep-18 T4
Greedy Algorithms
24. 3-Oct-18
L-20 Greedy Algorithms
27. 8-Oct-18
T5 Branch and Bound
32. 24-Oct-18 T6
BFS, DFS
37. 1-Nov-18
T7 Spanning Tree and Graph Algorithms
39. 5-Nov-18
L-32 Maximum flow
40. 12-Nov-18
L-33 Traveling salesman problem
43. 16-Nov-18
L-36 NP Problem
44. 19-Nov-18
L-37 NP Problem
45. 21-Nov-18
L-38 Approximation Algorithms
46. 22-Nov-18
T8 NP Problem
47. 23-Nov-18
L-39 Class Test 2
L
Total
T
Signature of Faculty………………………..SignatureHOD…………………………………………
Question Bank
MODULE 1. [CO1 , L3, L4]
1. Define Algorithm.
2. Write a short note on Algorithm Design and Analysis of Process.
3. What are the 2 kinds of Algorithm Efficiency?
4. How can you specify Algorithms?
5. What is Pseudo Code?
Tula's Institute, Dehradun Page 17
6. What is Sorting Problem?
7. What is Stable Sorting Algorithm?
8. What is Non-Stable Algorithm?
9. What is Searching Problem?
10. Differentiate between Recursion and Iterative way of writing a program.
16. Explain the possible AVL rotations with algorithm and example.
17. Explain insertion and deletion operations on Fibonacci heap.
18. Construct a B-tree with order m=3 for the key values 2,3,7,9,5,6,4,8,1 and delete the values 4 and Show
the tree in performing all operations.
19. How Fibonacci heaps differ from binomial heap?
36. How many comparisons do we need to find the top two largest numbersin a sequence ofndistinct
numbers?
37. If random number generation algorithm, pass many Test, but do not pass monobit Test. randomness is
accepted or rejected.
38. Discuss NP, NP complete, NP Hard problem in detail.
39. Discuss the string matching algorithm with suitable example.
40. Discuss topological shorting process in detail
Assignment No01
Assignment No 02
95
/ \
40 113
/ \ / \
15 42 110 125
/ \
41 112 L4
-- 20 12 18 7 3 6 4
3 Show the red-black trees after successively inserting the keys 41, 38, 31, 12, 19, 8 into L4
and initially empty red-black tree
4 How Fibonacci heap is different from binary Heap? Discuss with suitable example. L4
Assignment No. 03
Assignment No:04
4. What is spanning tree? Discuss all the suitable method for obtaining the spanning tree L4
from the graph with suitable example.
a. What are the different methods of solving recurrences? Discuss in detail. [L4]
b. Explain the quick sort with the help of an example. [L4]
c. Illustrate the operation of heap-sort in the array A=(19,13,21,25,73,17,20,8,4) [L3]
d. Using merge sort algorithm sort the following elements:21,15,3,18,6,45,22 [L3]
Q3 (5X2=10)
Q1
a. Diffentiate divide &conquer and greedy algorithm with the help of an
example [L4].
b. Discuss the various properties of binary search?[L4]
c. Discuss different rules of insertion in a red – black tree. [L4]
d. Discuss the properties of binomial heap with suitable examples. [L4]
Q2
.
a. Diffentiate between the knapsack and fractional knapsack problem. (2.5*4=10)
b. Analyze the travelling salesman problem with the help of an example.
c. Discuss the properties of dynamic programing paradigm in detail.
d. Find out the longest common subsequence.
X= abaaba
Y= babbab
Q3
. (5*2=10)
a. Compute the minimum spanning tree of the graph below using [L4]
(i)Kruskal’s method
(ii)Prim’s method
b. Construct each step during insertion and creation of red-black tree result after
successively inserting the keys 41,38,31,12,19,8 in an initially empty red black tree
.show all rotations and red colouring at each step. [L5]
Q Solution Marks
No
4 Pass 9 1
5 Fail 0 0
6 FCD 0 0
7 FC 3 0
8 SC 4 1