2024 SchemeBETASemester S1• Computer Science and Engineering
Algorithmic Thinking with Python
2024 Scheme Syllabus & PYQ Analysis • UCEST105
Module:
Priority:
Module 1Problem Solving Strategies & Decomposition
15 MarksTop-Down Design & Modular Program Decomposition
High Priority10x in Past Papers
EXAM NOTE
Top-down stepwise refinement: Breaking a complex problem into sub-problems until each module is independently solvable. Draw structure charts illustrating modular decomposition of a Student Grade Calculation or ATM banking system.
Fundamental Python Syntax: Data Types, Type Casting & Operators
High Priority10x in Past Papers
EXAM NOTE
Python core data types (int, float, complex, str, bool). Type casting: implicit vs explicit. Operators: Arithmetic, relational, logical (short-circuit evaluation), bitwise (&, |, ^, ~), and identity (is, is not) vs membership (in, not in).
Problem-Solving Phases: Definition, Modeling & Algorithm Validation
High Priority9x in Past Papers
EXAM NOTE
Detail the 6 fundamental phases: Problem definition, mathematical/logical modeling, algorithm specification, verification, implementation, and empirical testing. Highlight difference between syntax and logical errors.
Heuristic Approaches & Means-End Analysis
Medium Priority8x in Past Papers
EXAM NOTE
Means-End Analysis: Identify the difference between the current state and goal state, then choose an operator that reduces this difference. Explain with Missionaries and Cannibals or Tower of Hanoi problem states.
Module 2Flowcharts, Selection & Iteration in Python
15 MarksFlowchart Design, Standard Symbols & Structured Pseudocode
High Priority10x in Past Papers
EXAM NOTE
Draw correct ANSI standard flowchart shapes: Oval (Terminal), Parallelogram (Input/Output), Rectangle (Process), Diamond (Decision), Circle (Connector). Write clean pseudocode alongside flowchart for finding largest of three numbers or roots of quadratic equation.
Iteration Structures: while & for Loops, Loop Invariants & Termination
High Priority10x in Past Papers
EXAM NOTE
range(start, stop, step) semantics. Control jump statements: break, continue, pass. Explain for-else and while-else construct (else executes only if loop completes without hitting break). Loop invariant proof: Initialization, Maintenance, Termination.
Conditional Branching in Python: if, if-else, nested-if & elif Chains
High Priority9x in Past Papers
EXAM NOTE
Indentation semantics in Python. Multi-way branching with if-elif-else. Implement electricity bill calculation with tiered slab tariffs or student grading system.
Number-Theoretic Algorithms: Sieve of Eratosthenes & Prime Factorization
High Priority9x in Past Papers
EXAM NOTE
Sieve of Eratosthenes algorithm: Boolean array of size ; cross out multiples of primes starting from up to . Time complexity . Compare with naive trial division. Euclidean GCD algorithm: .
Module 3Recursion & Divide-and-Conquer Algorithms
15 MarksRecursion Principles: Base Cases, Recursive Steps & Call Stack Execution
High Priority10x in Past Papers
EXAM NOTE
Every recursive function requires: (1) At least one Base Case that terminates without recursive call, (2) Recursive case that moves closer to base case. Draw call stack frame diagrams showing activation records, parameter passing, return address, and unwinding.
Divide-and-Conquer Paradigm: Binary Search & Merge Sort Analysis
High Priority10x in Past Papers
EXAM NOTE
Three steps: Divide problem into smaller sub-problems, Conquer sub-problems recursively, Combine solutions. Binary Search: . Merge Sort: in all cases.
Classic Recursive Algorithms: Fibonacci Sequence & Tower of Hanoi
High Priority9x in Past Papers
EXAM NOTE
Tower of Hanoi: moves. Algorithm: Move discs from Source to Aux using Dest; move -th disc to Dest; move discs from Aux to Dest using Source. Trace 3 discs step by step.
Python Collections: Lists, Tuples, Dictionaries & Slicing Operations
High Priority9x in Past Papers
EXAM NOTE
Mutable (List, Dict, Set) vs Immutable (Tuple, String). List slicing: list[start:stop:step] (e.g. list[::-1] for reversal). Dictionary methods: keys(), values(), items(), get(k, default). List comprehension syntax: [x**2 for x in nums if x%2==0].
Module 4Greedy Algorithms, Dynamic Programming & Backtracking
15 MarksGreedy Strategy: Core Philosophy, Fractional Knapsack & Activity Selection
High Priority10x in Past Papers
EXAM NOTE
Greedy property: Makes locally optimal choice at each step hoping for global optimum. Explain Fractional Knapsack algorithm: Sort by value/weight descending; take complete items while capacity allows; take fraction of next item. time.
Dynamic Programming Principles: Overlapping Subproblems & Optimal Substructure
High Priority10x in Past Papers
EXAM NOTE
Contrast Divide-and-Conquer (independent subproblems) with Dynamic Programming (overlapping subproblems). Compare Memoization (top-down caching of recursive calls) and Tabulation (bottom-up table construction).
0/1 Knapsack Problem & Longest Common Subsequence (LCS)
High Priority10x in Past Papers
EXAM NOTE
0/1 Knapsack recurrence: V[i, w] = max(V[i-1, w], + V[i-1, w - ]) if <= w, else V[i-1, w]. Construct 2D table step by step. Contrast why Greedy fails for 0/1 Knapsack but works for Fractional. LCS recurrence: c[i, j] = c[i-1, j-1] + 1 if X[i]==Y[j], else max(c[i-1, j], c[i, j-1]).
Backtracking Fundamentals: State-Space Tree & N-Queens Problem
High Priority9x in Past Papers
EXAM NOTE
Backtracking builds candidates incrementally and abandons ('prunes') a partial candidate as soon as it determines it cannot possibly lead to a valid solution. Draw the state-space tree for 4-Queens problem showing dead-end pruning.
Spot an error, wrong question, or missing topic? Let us know so we can fix it right away!
