CSIT 3rd Semester Exam Prep - Score 60/60

CSIT 3rd Semester Exam Prep – Score 60/60

Your one-stop resource to ace your board exams with comprehensive notes, exercises, quizzes, past questions, model questions, and reference videos!

Home Data Structures Numerical Methods Computer Architecture Computer Graphics Statistics II

Welcome to CSIT 3rd Semester Prep!

This website is designed to help you excel in your CSIT 3rd semester board exams at Tribhuvan University. It covers all five subjects: Data Structures and Algorithms, Numerical Methods, Computer Architecture, Computer Graphics, and Statistics II. Each subject includes detailed notes, practice exercises, interactive quizzes, past questions (2074–2078), model questions, and reference videos to ensure you’re fully prepared to score 60/60. Let’s get started!

Data Structures and Algorithms

Important Notes

Arrays: Contiguous memory allocation, O(1) access time.
Linked Lists: Dynamic structure, nodes with data and pointers, O(n) traversal.
Stacks: LIFO (Last In, First Out). Operations: push, pop, O(1).
Queues: FIFO (First In, First Out). Operations: enqueue, dequeue, O(1).
Trees: Hierarchical structure, e.g., Binary Search Tree (BST), O(log n) search.
Graphs: Vertices and edges, represented via adjacency list/matrix.
Sorting: Bubble Sort (O(n²)), Quick Sort (O(n log n)), Merge Sort (O(n log n)).
Searching: Linear Search (O(n)), Binary Search (O(log n)) for sorted data.
Hashing: Maps keys to values, average O(1) access with good hash function.
Complexity: Analyze time and space complexity for algorithm efficiency.

Exercises with Solutions (Past Questions & Model Questions)

1. (Past 2074) Implement a stack using an array.

Solution: Use an array with a top pointer. Push: increment top, add element. Pop: return element, decrement top.

2. (Past 2075) Write a program to reverse a linked list.

Solution:

struct Node* reverseList(struct Node* head) {
    struct Node *prev = NULL, *current = head, *next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

3. (Past 2076) Implement a queue using two stacks.

Solution: Use one stack for enqueue (push), another for dequeue (pop after transferring elements when empty).

4. (Past 2077) Write an algorithm for Binary Search.

Solution: For a sorted array, repeatedly divide the search interval in half. If mid element matches, return index; else, search left or right half.

5. (Past 2078) Explain DFS and BFS with their algorithms.

Solution: DFS uses a stack (recursive or explicit) to explore as far as possible along each branch. BFS uses a queue to explore level by level.

6. (Model) Write a program to detect a cycle in a linked list.

Solution: Floyd’s Cycle-Finding Algorithm:

int hasCycle(struct Node* head) {
    struct Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

7. (Model) Sort an array using Quick Sort.

Solution: Choose a pivot, partition the array, and recursively sort subarrays.

8. (Model) Implement a Binary Search Tree insertion.

Solution: Compare value with root; insert in left subtree if smaller, right if larger, recursively.

9. (Model) Find the shortest path in a graph using Dijkstra’s algorithm.

Solution: Use a priority queue to select the vertex with the minimum distance, update distances of adjacent vertices.

10. (Model) Explain the time complexity of Merge Sort.

Solution: O(n log n) due to dividing the array into halves (log n) and merging (n).

Quiz: Test Your Knowledge (10 Questions)

Answer the following questions to check your understanding of Data Structures and Algorithms. Includes past and model questions.

1. (Past 2074) What is the time complexity of Bubble Sort?

a) O(n)
b) O(n²)
c) O(n log n)

2. (Past 2075) Which data structure follows LIFO?

a) Queue
b) Stack
c) Array

3. (Past 2076) What is the time complexity of Binary Search?

a) O(n)
b) O(log n)
c) O(n²)

4. (Past 2077) Which traversal visits the root first in a tree?

a) Inorder
b) Preorder
c) Postorder

5. (Past 2078) What is the space complexity of DFS?

a) O(V)
b) O(E)
c) O(V+E)

6. (Model) Which algorithm is used for shortest path in weighted graphs?

a) BFS
b) Dijkstra’s
c) DFS

7. (Model) What is the average time complexity of Quick Sort?

a) O(n²)
b) O(n log n)
c) O(n)

8. (Model) Which data structure is best for fast lookups?

a) Array
b) Hash Table
c) Linked List

9. (Model) What is the time complexity of inserting into a BST?

a) O(n)
b) O(log n)
c) O(1)

10. (Model) Which sorting algorithm is stable?

a) Quick Sort
b) Merge Sort
c) Heap Sort

Past Question (2076)

Question: Implement a queue using two stacks.

Solution: Use one stack for enqueue (push), another for dequeue (pop after transferring elements when empty).

Model Question

Question: Write a program to detect a cycle in a linked list.

Solution: Floyd’s Cycle-Finding Algorithm (as shown above).

Reference Video

Data Structures Tutorial

Numerical Methods

Important Notes

Bisection Method: Finds roots by halving intervals where f(a) * f(b) < 0.
Newton-Raphson: Iterative root-finding: x₁ = x₀ - f(x₀)/f'(x₀).
Secant Method: Uses two initial guesses, avoids derivatives.
Gaussian Elimination: Solves linear systems by row reduction.
Interpolation: Lagrange, Newton’s Forward/Backward for estimating values.
Numerical Integration: Trapezoidal Rule, Simpson’s 1/3 Rule.
Runge-Kutta Method: Solves differential equations.
Eigenvalues: Power Method to find dominant eigenvalue.
Matrix Inversion: Gauss-Jordan method for inverses.
Error Analysis: Truncation and round-off errors.

Exercises with Solutions (Past Questions & Model Questions)

1. (Past 2074) Find the root of x³ - 2x - 5 = 0 using Bisection Method in [2, 3].

Solution: f(2) = -1, f(3) = 16, midpoint 2.5, f(2.5) = 1.125, continue halving until convergence.

2. (Past 2075) Apply Simpson’s 1/3 rule to integrate f(x) = x² from 0 to 2.

Solution: h = 1, points: 0, 1, 2. Result = (1/3) * (0 + 4*1 + 4) = 8/3 ≈ 2.6667.

3. (Past 2076) Use Newton-Raphson to solve x² - 4 = 0, x₀ = 3.

Solution: f(x) = x² - 4, f'(x) = 2x. x₁ = 3 - (9-4)/(6) = 2.1667, converges to 2.

4. (Past 2077) Interpolate f(3) given f(1) = 1, f(2) = 4, f(4) = 16 using Lagrange.

Solution: f(3) = 9 (using polynomial interpolation).

5. (Past 2078) Solve 2x + y = 5, x + 3y = 7 using Gaussian Elimination.

Solution: Row reduce to get x = 2, y = 1.

6. (Model) Use Trapezoidal Rule to integrate f(x) = e^x from 0 to 1, n=4.

Solution: h = 0.25, result ≈ 1.718.

7. (Model) Find the dominant eigenvalue of [[2, 1], [1, 2]] using Power Method.

Solution: After iterations, eigenvalue ≈ 3.

8. (Model) Solve dy/dx = x + y, y(0) = 1 at x = 0.1 using Runge-Kutta 4th order.

Solution: y(0.1) ≈ 1.105.

9. (Model) Use Secant Method to solve x³ - x - 1 = 0, x₀ = 1, x₁ = 2.

Solution: Iterate to approximate root ≈ 1.324.

10. (Model) Explain truncation error in numerical methods.

Solution: Error from approximating infinite processes (e.g., Taylor series cutoff).

Quiz: Test Your Knowledge (10 Questions)

Answer the following questions to check your understanding of Numerical Methods.

1. (Past 2074) What does the Bisection Method require?

a) f(a) * f(b) > 0
b) f(a) * f(b) < 0
c) f(a) = 0

2. (Past 2075) What is the order of Simpson’s 1/3 Rule?

a) 1
b) 2
c) 3

3. (Past 2076) Newton-Raphson convergence is:

a) Linear
b) Quadratic
c) Cubic

4. (Past 2077) Which method avoids derivatives?

a) Newton-Raphson
b) Secant
c) Bisection

5. (Past 2078) What does Gaussian Elimination solve?

a) Integrals
b) Linear systems
c) Roots

6. (Model) What is the error in Trapezoidal Rule?

a) O(h)
b) O(h²)
c) O(h³)

7. (Model) Which method solves ODEs?

a) Runge-Kutta
b) Lagrange
c) Power Method

8. (Model) What does the Power Method find?

a) Inverse
b) Eigenvalue
c) Integral

9. (Model) Which interpolation uses divided differences?

a) Lagrange
b) Newton
c) Simpson

10. (Model) What is round-off error?

a) Truncation
b) Finite precision
c) Integration

Past Question (2075)

Question: Apply Simpson’s 1/3 rule to integrate f(x) = x² from 0 to 2.

Solution: As shown above, result = 8/3 ≈ 2.6667.

Model Question

Question: Solve x³ - x - 1 = 0 using the Secant Method.

Solution: As shown above, root ≈ 1.324.

Reference Video

Numerical Methods Basics

Computer Architecture

Important Notes

Instruction Set: Commands the CPU understands (RISC vs. CISC).
Micro-Architecture: Internal CPU design (registers, ALU, control unit).
Memory Hierarchy: Registers → Cache → RAM → Disk (speed vs. size).
Pipelining: Overlaps Fetch, Decode, Execute, Memory, Write-back.
Cache Memory: Reduces main memory access time (hit/miss ratio).
Interrupts: Signals to handle events (e.g., I/O completion).
Addressing Modes: Immediate, Direct, Indirect, Indexed.
ALU: Performs arithmetic and logical operations.
Control Unit: Directs operations using signals.
I/O Systems: DMA, interrupts for efficient data transfer.

Exercises with Solutions (Past Questions & Model Questions)

1. (Past 2074) Explain the stages of a 5-stage pipeline.

Solution: Fetch, Decode, Execute, Memory Access, Write-back.

2. (Past 2075) Calculate the hit ratio for a cache with 10 hits and 2 misses.

Solution: Hit ratio = 10/(10+2) = 0.8333 or 83.33%.

3. (Past 2076) Differentiate RISC and CISC.

Solution: RISC: Simple instructions, fixed length, pipelining-friendly. CISC: Complex instructions, variable length, more hardware-oriented.

4. (Past 2077) Explain the role of the Program Counter (PC).

Solution: PC holds the address of the next instruction to fetch.

5. (Past 2078) What is DMA in I/O systems?

Solution: Direct Memory Access allows devices to transfer data to/from memory without CPU intervention.

6. (Model) Describe direct-mapped vs. fully associative cache.

Solution: Direct-mapped: Each block maps to one cache slot. Fully associative: Any block can go to any slot.

7. (Model) Explain the working of the ALU.

Solution: ALU performs arithmetic (add, subtract) and logical operations (AND, OR) on operands.

8. (Model) What are addressing modes? List four types.

Solution: Ways to specify operand locations: Immediate, Direct, Indirect, Indexed.

9. (Model) How does pipelining improve performance?

Solution: Overlaps instruction stages, reducing cycle time per instruction.

10. (Model) Explain the role of interrupts in CPU operation.

Solution: Interrupts allow the CPU to handle events (e.g., I/O completion) by pausing current execution.

Quiz: Test Your Knowledge (10 Questions)

Answer the following questions to check your understanding of Computer Architecture.

1. (Past 2074) How many stages in a 5-stage pipeline?

a) 4
b) 5
c) 6

2. (Past 2075) What does the Program Counter do?

a) Store data
b) Track next instruction
c) Manage cache

3. (Past 2076) RISC instructions are:

a) Complex
b) Simple
c) Variable length

4. (Past 2077) What is the topmost level of memory hierarchy?

a) RAM
b) Cache
c) Registers

5. (Past 2078) What does DMA stand for?

a) Direct Memory Access
b) Data Memory Address
c) Direct Machine Access

6. (Model) What improves CPU performance?

a) Pipelining
b) Single cycle
c) Serial execution

7. (Model) Which addressing mode uses a register?

a) Immediate
b) Indirect
c) Direct

8. (Model) What does the ALU perform?

a) I/O operations
b) Arithmetic operations
c) Memory access

9. (Model) What is a cache miss?

a) Data found
b) Data not found
c) Cache full

10. (Model) What handles external events?

a) ALU
b) Interrupts
c) Cache

Past Question (2074)

Question: Explain the stages of a 5-stage pipeline.

Solution: As shown above, Fetch, Decode, Execute, Memory Access, Write-back.

Model Question

Question: Differentiate direct-mapped and fully associative cache.

Solution: As shown above.

Reference Video

Computer Architecture Basics

Computer Graphics

Important Notes

2D Transformations: Translation, Rotation, Scaling, Reflection.
3D Transformations: Similar to 2D but with z-axis.
Clipping: Cohen-Sutherland algorithm for line clipping.
Scan Conversion: Rasterizes lines, circles (e.g., Bresenham’s).
Rendering: Converts 3D models to 2D images.
Illumination Models: Phong model for lighting.
Projection: Orthographic vs. Perspective projection.
Shading: Flat, Gouraud, Phong shading techniques.
Visible Surface Detection: Z-buffer, Painter’s algorithm.
Curves: Bezier, B-Spline for smooth curves.

Exercises with Solutions (Past Questions & Model Questions)

1. (Past 2074) Translate point (2, 3) by (4, 5).

Solution: New point = (2+4, 3+5) = (6, 8).

2. (Past 2075) Rotate point (1, 1) by 90° counterclockwise about origin.

Solution: New point = (-1, 1) using rotation matrix.

3. (Past 2076) Apply midpoint circle algorithm for radius 5.

Solution: Iteratively calculate pixel positions using decision parameter.

4. (Past 2077) Explain Cohen-Sutherland line clipping algorithm.

Solution: Assign region codes, clip lines outside the viewport iteratively.

5. (Past 2078) Draw a line from (1, 1) to (5, 3) using Bresenham’s algorithm.

Solution: Calculate decision parameter, plot pixels incrementally.

6. (Model) Scale point (3, 4) with Sx=2, Sy=3.

Solution: New point = (3*2, 4*3) = (6, 12).

7. (Model) Explain the Phong illumination model.

Solution: Combines ambient, diffuse, and specular lighting components.

8. (Model) What is the Z-buffer algorithm?

Solution: Stores depth values to determine visible surfaces.

9. (Model) Define a Bezier curve for 3 control points.

Solution: Quadratic Bezier: P(t) = (1-t)²P₀ + 2(1-t)tP₁ + t²P₂, t ∈ [0,1].

10. (Model) Differentiate orthographic and perspective projection.

Solution: Orthographic: Parallel projection, no depth scaling. Perspective: Converging projection, objects smaller with distance.

Quiz: Test Your Knowledge (10 Questions)

Answer the following questions to check your understanding of Computer Graphics.

1. (Past 2074) What does translation do?

a) Rotates
b) Moves
c) Scales

2. (Past 2075) What angle rotates (1, 1) to (-1, 1)?

a) 90°
b) 180°
c) 270°

3. (Past 2076) Which algorithm draws lines?

a) Cohen-Sutherland
b) Bresenham’s
c) Phong

4. (Past 2077) What does clipping do?

a) Renders
b) Removes outside parts
c) Scales

5. (Past 2078) What does the Phong model calculate?

a) Clipping
b) Lighting
c) Projection

6. (Model) What is orthographic projection?

a) Parallel
b) Converging
c) Curved

7. (Model) What does the Z-buffer store?

a) Color
b) Depth
c) Texture

8. (Model) Which shading is per-pixel?

a) Flat
b) Gouraud
c) Phong

9. (Model) What defines a Bezier curve?

a) Pixels
b) Control points
c) Lines

10. (Model) What does perspective projection do?

a) No scaling
b) Depth scaling
c) Flat projection

Past Question (2076)

Question: Apply the midpoint circle algorithm for radius 5.

Solution: As shown above.

Model Question

Question: Scale point (3, 4) with Sx=2, Sy=3.

Solution: As shown above.

Reference Video

Computer Graphics Intro

Statistics II

Important Notes

Probability: P(A) = favorable outcomes / total outcomes.
Random Variables: Discrete (e.g., dice roll), Continuous (e.g., height).
Distributions: Binomial (n trials), Poisson (events in interval), Normal (bell curve).
Hypothesis Testing: Null (H₀) vs. Alternative (H₁), p-value < α to reject.
ANOVA: Compares means across groups (F-test).
Regression: Linear: y = mx + c, Multiple: y = b₀ + b₁x₁ + b₂x₂.
Correlation: Pearson’s r measures linear relationship (-1 to 1).
Confidence Intervals: Range for parameter (e.g., μ ± z(σ/√n)).
Non-Parametric Tests: Chi-Square, Mann-Whitney U for non-normal data.
Queuing Theory: M/M/1 model, L = λ/(μ-λ).

Exercises with Solutions (Past Questions & Model Questions)

1. (Past 2074) Find P(X=2) for a Binomial distribution, n=5, p=0.4.

Solution: P(X=2) = (5 choose 2) * (0.4)² * (0.6)³ = 10 * 0.16 * 0.216 = 0.3456.

2. (Past 2075) Perform a chi-square test on a 2x2 table: Males (35X, 25Y), Females (20X, 20Y), α=0.05.

Solution: χ² = 0.673 < 3.841, independent.

3. (Past 2076) Test H₀: μ = 100 with n=16, x̄=105, s=8, α=0.05.

Solution: t = (105-100)/(8/√16) = 2.5, t₀.₀₂₅,₁₅ ≈ 2.131, reject H₀.

4. (Past 2077) Compute r for (1,2), (2,3), (3,5).

Solution: r = 0.98 (using Pearson’s formula).

5. (Past 2078) Find 95% CI for n=25, x̄=100, s=15.

Solution: (93.81, 106.19).

6. (Model) Fit a linear regression for (1,2), (2,4), (3,6).

Solution: y = 2x (slope = 2, intercept = 0).

7. (Model) In M/M/1 queue, λ=10/hr, service time=5min, find L.

Solution: μ = 12/hr, L = 10/(12-10) = 5.

8. (Model) Use Mann-Whitney U test for two samples (simplified).

Solution: U = n₁n₂ + (n₁(n₁+1))/2 - R₁ (as per formula).

9. (Model) Perform ANOVA for a 3x3 Latin Square (A:10,13,18; B:12,15,16; C:14,17,20).

Solution: F_treatment = 7 < 19, no significant difference.

10. (Model) Find P(X ≥ 3) for Poisson with λ=4.

Solution: P(X ≥ 3) = 1 - P(X < 3) = 0.762.

Quiz: Test Your Knowledge (10 Questions)

Answer the following questions to check your understanding of Statistics II.

1. (Past 2074) What does p-value < 0.05 indicate?

a) Accept H₀
b) Reject H₀
c) No conclusion

2. (Past 2075) What test uses χ² statistic?

a) t-test
b) Chi-Square
c) ANOVA

3. (Past 2076) What is the mean of a Poisson distribution?

a) λ
b) λ²
c) 1/λ

4. (Past 2077) Pearson’s r ranges from:

a) 0 to 1
b) -1 to 1
c) -∞ to ∞

5. (Past 2078) What does ANOVA compare?

a) Variances
b) Means
c) Medians

6. (Model) What is the formula for CI of mean?

a) x̄ ± z(σ/√n)
b) x̄ ± σ
c) x̄ ± z

7. (Model) In M/M/1, what is L?

a) λ/(μ-λ)
b) μ/λ
c) λ/μ

8. (Model) Which test is non-parametric?

a) t-test
b) Mann-Whitney U
c) ANOVA

9. (Model) What does linear regression predict?

a) Categorical
b) Continuous
c) Binary

10. (Model) What is the variance of Binomial?

a) np
b) np(1-p)
c) n²p

Past Question (2075)

Question: Perform a chi-square test on a 2x2 contingency table.

Solution: As shown above.

Model Question

Question: Fit a linear regression for y = 2x + 3 with given data.

Solution: As shown above.

Reference Video

Statistics Basics

Follow for more resources: https://linktr.ee/fyaste