Computer Science Master Class Study Notes - Paper 2

Principles of Computational Thinking

• Abstraction

  • Definition: The process of filtering out or ignoring information that is not needed in order to concentrate on what is necessary.

  • Purpose: It involves the filtering out of specific details to create a representation (or idea) of the problem being solved.

• Decomposition

  • Definition: Breaking a complex problem down into a number of smaller, more manageable problems.

  • Benefits:

    • If a problem is not decomposed, it is significantly harder to solve.

    • Dealing with many stages simultaneously is difficult; solving smaller problems one at a time is more efficient.

    • Allows each smaller sub-problem to be examined in much greater detail.

• Algorithmic Thinking

  • Definition: A logical, step-by-step process for solving a problem.

  • Key Concept: Algorithm production is a core part of algorithmic thinking. It focuses on how a desired solution can be reached by identifying the specific steps required to get there.

Algorithm Representation and Design

• Structure Diagrams

  • Used to identify the inputs, processes, and outputs for a particular problem in a visual hierarchy.

• Pseudocode

  • Definition: A high-level, informal description of an algorithm or program that utilizes a mix of natural language and simplified programming conventions.

  • Example Algorithm (Calculating Average):

    • START

    • OUTPUT "Enter first number"

    • INPUT num1

    • OUTPUT "Enter second number"

    • INPUT num2

    • average ← (num1 + num2) / 2

    • OUTPUT average

    • END

  • Mathematical Representation: $average \leftarrow \frac{num1 + num2}{2}$

• Flowcharts

  • Visual representation of the inputs, processes, and outputs for a problem using standardized shapes (e.g., ovals for Start/End, parallelograms for Input/Output, rectangles for Processes).

• Trace Tables

  • Used by programmers to track the value of variables line-by-line as code executes.

  • Purpose: To assist in identifying potential logic errors by displaying variable changes in a tabular format.

Boolean Logic

• Common Boolean Operators

  • AND (Conjunction): Outputs true only if both inputs are true.

  • OR (Disjunction): Outputs true if at least one input is true.

  • NOT (Negation): Reverses the input (true becomes false, false becomes true).

• Truth Tables

Character Sets and Encoding

• ASCII (American Standard Code for Information Interchange)

  • Original ASCII: Uses $7$ bits, providing $128$ characters ($2^7$).

  • Extended ASCII: Uses $8$ bits, providing $256$ characters ($2^8$).

  • Key Reference Codes:

    • The character 'A' is represented by the decimal value $65$.

    • The character 'a' is represented by the decimal value $97$.

    • Note: Character codes follow a sequential order, allowing other letters to be calculated from these base values.

• Unicode

  • Uses $32$ bits for encoding.

  • Version 15.0 Statistics: Includes $149,186$ characters.

  • Coverage: Covers $161$ modern and historical scripts, along with multiple symbol sets.

Searching and Sorting Algorithms

• Linear Search

  • Process: Examines each item in a list in sequence (in a "line") to see if it matches the target item.

  • Example: Searching for 6 in [1,2,3,4,5,6,7,8,9,10] requires checking 1, then 2, then 3, then 4, then 5, and finally 6.

• Binary Search

  • Process: "Binary" means two; the algorithm repeatedly splits the list in half to find the target.

  • Prerequisite: The list must be sorted.

  • Example: Finding 37 in a sorted list of primes. The algorithm checks the middle value, determines if 37 is higher or lower, and discards the irrelevant half.

• Bubble Sort

  • Process: Compares adjacent items and swaps them if they are in the wrong order.

  • Passes:

    • After 1 pass, the largest item is in its correct place at the end of the list (the right).

    • After 2 passes, the second largest is in place.

    • This continues until the list is sorted.

• Insertion Sort

  • Process:

    1. The first item is treated as a "sorted list" of one.

    2. The remaining items are in an "unsorted list."

    3. Each item from the unsorted list is taken in turn and inserted into the correct position within the sorted list on the left.

• Merge Sort

  • Process:

    1. Divide: Break the list down repeatedly until every item is in its own separate list.

    2. Conquer: Combine individual items into pairs in the correct order.

    3. Combine: Continue merging pairs into groups of four, then eights, etc., until one sorted list remains.

Software Testing

• Purpose of Testing:

  • To ensure the program works correctly.

  • To verify it produces expected outputs.

  • To ensure it handles errors properly.

  • To make the program reliable and robust.

• Types of Test Data:

  • Normal Data: Expected, valid inputs within the standard range.

  • Boundary Data: Values at the extreme edges of the allowable range.

  • Erroneous Data: Invalid or incorrect input used to test error handling.

• Robust Testing:

  • Checks how the program handles unexpected input.

  • Ensures validation works correctly.

  • Verifies the program does not crash under stress.

Integrated Development Environments (IDEs)

• Definition: Software used to write, test, and debug computer programs. Examples include IDLE, PyCharm, and Visual Studio Code.

• Common Tools and Facilities:

  • Editor: For writing and editing source code.

  • Syntax Highlighting: Colors keywords to improve readability and identify syntax errors.

  • Error Diagnostics: Identifies mistakes or errors in the code.

  • Auto-completion: Suggests code snippets/variables while typing.

  • Run tools: Executes the program within the environment.

  • Debugger: Assists in finding and fixing logic errors.

  • Breakpoints: Allows the programmer to pause program execution at specific lines.

  • Stepping through: Allows the code to be run one line at a time to monitor behavior.

Compilers vs. Interpreters

• Compiler

  • Method: Translates the entire source code program into machine code at once.

  • Output: Produces a standalone executable file.

  • Errors: Reports all errors only after the entire compilation process is finished.

  • Pros/Cons: Faster execution; no need for source code during runtime. However, the program must be recompiled after every change.

• Interpreter

  • Method: Translates and executes the program line-by-line.

  • Output: No executable file is produced.

  • Errors: Stops execution immediately when the first error is encountered.

  • Pros/Cons: Easier to debug and good for testing. However, it results in slower execution and requires the interpreter software to be installed on the target machine.

Databases

• Flat File Databases

  • Consist of a single table of data.

  • Users specify data attributes (columns) and data types.

  • Data is stored separately from the access application (e.g., Excel or Google Sheets).

• Relational Databases

  • Consist of multiple tables linked together by relationships.

  • Entities: Each separate "thing" (e.g., Artist, Album, Song) is an entity and gets its own table.

  • Fields: The columns in a table (e.g., Artist name, ID).

  • Records: The rows in a table (e.g., a specific artist's information).

  • Advantages:

    • Eliminates redundant/duplicated information.

    • Data is only stored once; for example, changing an artist's name only requires a single update in the Artists table, which automatically reflects across the database via ID links.

• SQL (Structured Query Language)

  • Syntax: SELECT [Fields] FROM [Table] WHERE [Criteria]

  • SELECT: Identifies which fields to display (use * for all fields).

  • FROM: Identifies the table(s) the data is coming from (e.g., FROM Artists).

  • WHERE: Specifies the criteria for the search (e.g., WHERE age > 17 or WHERE Artists.ID = 1).

  • INNER JOIN: Used in relational queries to link tables on a common field (e.g., FROM Artists INNER JOIN Albums ON Artists.ID = Albums.Artist).