CSS Computer Science Algorithms & Data Structures Syllabus

Algorithms & Data Structures syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Algorithms & Data Structures in CSS Computer Science, not a summary of it.

1. 1

   Algorithm Analysis

   3 topics

   • Properties & Criteria of Algorithms
   • Asymptotic Notation
   • Recursion
2. 2

   Linear Data Structures

   4 topics

   • Abstract Data Types
   • Lists & Linked Lists
   • Stacks
   • Queues & Circular Queues
3. 3

   Searching & Sorting

   3 topics

   • Linear & Binary Search
   • Comparison Sorts
   • Hash Tables & Hashing
4. 4

   Trees & Graphs

   4 topics

   • Binary Trees & BST
   • Balanced Trees
   • Graph Representations & Traversals
   • Heuristic & Genetic Search
5. 5

   Cryptographic Algorithms

   2 topics

   • Symmetric Encryption (DES)
   • Asymmetric Encryption (RSA)

Algorithms & Data Structures flashcards for CSS Computer Science

19 of 56 cards from the Algorithms & Data Structures deck — real questions with worked answers.

1. What are the five required properties of a well-defined algorithm?

   Input (zero or more), Output (at least one), Definiteness (each step is precise/unambiguous), Finiteness (terminates after finite steps), and Effectiveness (each step is basic enough to be carried out).

2. What distinguishes correctness, efficiency, and generality as criteria for evaluating an algorithm?

   Correctness: produces the right output for all valid inputs. Efficiency: uses minimal time and space resources. Generality: solves the whole class of problems, not just one instance.

3. Define Big-O notation formally.

   f(n) = O(g(n)) if there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0. It is an asymptotic upper bound on growth rate.

4. What does Big-Omega (Ω) notation describe?

   An asymptotic lower bound: f(n) = Ω(g(n)) if there exist constants c, n0 > 0 such that f(n) ≥ c·g(n) for all n ≥ n0.

5. What does Big-Theta (Θ) notation mean?

   A tight bound: f(n) = Θ(g(n)) means f is bounded both above and below by g asymptotically, i.e. f(n) = O(g(n)) AND f(n) = Ω(g(n)).

6. Order these complexities from fastest to slowest growth: O(n²), O(log n), O(n log n), O(1), O(2ⁿ), O(n).

   O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).

7. What is the difference between best-case, worst-case, and average-case complexity?

   Best-case: minimum running time over all inputs of size n. Worst-case: maximum running time (the usual guarantee). Average-case: expected running time over the distribution of inputs.

8. What are the two essential components every recursive algorithm must have?

   A base case (terminating condition that stops recursion) and a recursive case (which calls itself on a smaller subproblem moving toward the base case).

9. What is the difference between direct and indirect recursion?

   Direct recursion: a function calls itself. Indirect (mutual) recursion: function A calls function B, which in turn calls A.

10. What is tail recursion and why is it useful?

    Recursion where the recursive call is the last operation in the function. It can be optimized by the compiler into a loop, reusing the same stack frame (constant stack space).

11. Write the recurrence relation for the time complexity of binary search and give its solution.

    T(n) = T(n/2) + O(1), which solves to O(log n).

12. What does the Master Theorem solve, and what is its general form?

    It gives the asymptotic solution of divide-and-conquer recurrences of the form T(n) = a·T(n/b) + f(n), comparing f(n) to n^(log_b a) across three cases.

13. Define an Abstract Data Type (ADT).

    A mathematical model defining a data type by its values and the operations on them (the interface/behavior), independent of any particular implementation.

14. How does an ADT differ from a data structure?

    An ADT specifies WHAT operations exist and their behavior (logical view); a data structure specifies HOW those operations are implemented and how data is stored (physical view).

15. Name three common ADTs and one primary operation of each.

    Stack (push/pop), Queue (enqueue/dequeue), List (insert/delete/access). Others: Set, Map/Dictionary, Tree, Graph.

16. What is the difference between an array (contiguous list) and a linked list in memory layout?

    An array stores elements contiguously with index-based O(1) access; a linked list stores nodes scattered in memory connected by pointers, giving O(n) access but O(1) insertion/deletion at a known node.

17. Give the time complexity for access, search, insertion at head, and deletion at head for a singly linked list.

    Access: O(n); Search: O(n); Insertion at head: O(1); Deletion at head: O(1).

18. What does a node in a doubly linked list contain, and what advantage does it offer?

    It contains data, a pointer to the next node, and a pointer to the previous node. Advantage: it can be traversed in both directions and allows O(1) deletion given a node reference.

19. What is a circular linked list?

    A linked list where the last node's next pointer points back to the first node (head) instead of NULL, forming a closed loop.

See more Algorithms & Data Structures flashcards →

Planning Algorithms & Data Structures for CSS Computer Science

Algorithms & Data Structures (CSS Computer Science) FAQ