[Concepts] Paper 2
- CHAPTER 9: ALGORITHM DESIGN AND PROBLEM-SOLVING
- CHAPTER 10: DATA TYPES AND STRUCTURES
- CHAPTER 11: PROGRAMMING FUNDAMENTALS
- CHAPTER 12: SOFTWARE DEVELOPMENT
CHAPTER 9: ALGORITHM DESIGN AND PROBLEM-SOLVING
9.1 COMPUTATIONAL THINKING SKILLS
9.1.1 Abstraction
Definition: The process of removing unnecessary details to focus on essential features.
Need:
- Manage complexity
- Create models of real-world systems
Benefits:
- Focus on what matters
- Reusable solutions
9.1.2 Decomposition
Definition: Breaking down complex problems into smaller, manageable sub-problems.
Benefits:
- Easier to solve smaller problems
- Can work on different parts independently
- Leads to modular programming (procedures/functions)
9.2 ALGORITHMS
9.2.1 Algorithm Representation
Methods:
- Structured English
- Flowchart
- Pseudocode
Components:
- Input
- Process
- Output
Basic Constructs:
- Sequence (order of execution)
- Selection (IF, CASE)
- Iteration (loops)
9.2.2 Pseudocode Guidelines
Input/Output:
Assignment:
Selection:
Iteration:
9.2.3 Stepwise Refinement
Process:
- Start with general solution
- Gradually add detail
- Continue until can be programmed
CHAPTER 10: DATA TYPES AND STRUCTURES
10.1 DATA TYPES
10.1.1 Primitive Data Types
10.1.2 Records
Definition: A structure that holds a set of data of different types under one identifier.
Purpose:
Example:
10.2 ARRAYS
10.2.1 One-Dimensional Arrays
Definition: A collection of elements of the same type accessed by index.
Terms:
- Index: Position of element
- Lower bound: First index (usually 0 or 1)
- Upper bound: Last index
Declaration:
Access:
10.2.2 Two-Dimensional Arrays
Definition: Array of arrays; elements accessed by row and column.
Declaration:
10.2.3 Array Operations
Linear Search:
- Check each element sequentially
- Works on unsorted data
- O(n) time complexity
Bubble Sort:
- Compare adjacent elements
- Swap if in wrong order
- Repeat until sorted
- O(n²) time complexity
10.3 FILES
10.3.1 File Need
- Store data permanently
- Large amounts of data
- Data persistence between program runs
10.3.2 File Operations
Opening:
Reading:
Writing:
Closing:
10.4 ABSTRACT DATA TYPES (ADT)
10.4.1 Stack
Characteristics:
- LIFO (Last In, First Out)
- Add to top (push)
- Remove from top (pop)
Operations:
- Push: Add item to top
- Pop: Remove item from top
- Peek: View top item without removing
10.4.2 Queue
Characteristics:
- FIFO (First In, First Out)
- Add to rear (enqueue)
- Remove from front (dequeue)
10.4.3 Linked List
Characteristics:
- Dynamic structure
- Nodes contain data and pointer to next node
- Can grow/shrink easily
Operations:
- Add node
- Delete node
- Search
CHAPTER 11: PROGRAMMING FUNDAMENTALS
11.1 PROGRAMMING BASICS
11.1.1 Variables and Constants
Variable Declaration:
Constant Declaration:
Assignment:
11.1.2 Input/Output
Input:
Output:
11.1.3 Arithmetic Operators
11.1.4 Logical Operators
11.2 CONSTRUCTS
11.2.1 Selection Statements
IF Statement:
Nested IF:
CASE Statement:
11.2.2 Loop Structures
Count-Controlled (FOR):
Pre-Condition (WHILE):
Post-Condition (REPEAT):
Choice of Loop:
- FOR: When number of iterations known
- WHILE: When condition checked before first iteration
- REPEAT: When condition checked after at least one iteration
11.3 STRUCTURED PROGRAMMING
11.3.1 Procedures
Definition: A reusable block of code that performs a specific task.
Declaration:
Call:
Parameters:
- Passed by value: Copy of data passed
- Passed by reference: Actual data passed (can be modified)
11.3.2 Functions
Definition: Returns a value; used in expressions.
Declaration:
Use:
CHAPTER 12: SOFTWARE DEVELOPMENT
12.1 PROGRAM DEVELOPMENT LIFECYCLE
12.1.1 Stages
- Analysis: Understand problem, identify requirements
- Design: Create solution structure, algorithms
- Coding: Write actual program code
- Testing: Find and fix errors
- Maintenance: Update and improve after delivery
12.1.2 Development Models
Waterfall:
- Sequential phases
- Each phase completes before next begins
- Good for well-defined requirements
Iterative:
- Develop in cycles
- Each iteration produces working version
- Allows feedback and improvement
RAD (Rapid Application Development):
- Quick development using pre-built components
- Emphasis on prototyping
- Fast user feedback
12.2 PROGRAM DESIGN
12.2.1 Structure Chart
Purpose: Decompose problem into sub-tasks
Shows:
- Modules/procedures/functions
- Parameters passed between modules
12.2.2 State-Transition Diagrams
Purpose: Document algorithm behavior
Shows:
- Different states
- Transitions between states