KEMBAR78
Computer Science CPP Concepts | PDF | C++ | Time Complexity
Scribd
Upload
13 views5 pages

Computer Science CPP Concepts

The document discusses key computer science concepts using C++ examples, focusing on asymptotic notation for algorithm efficiency, recursion, and the comparison between arrays and linked lists. It highlights the advantages and limitations of recursion, and presents the Trie data structure as the best choice for dictionary applications due to its fast lookup capabilities. Additionally, it briefly mentions an alternative data structure, the hash map, for quick lookups.

Uploaded by

shreyabg890
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views5 pages

Computer Science CPP Concepts

The document discusses key computer science concepts using C++ examples, focusing on asymptotic notation for algorithm efficiency, recursion, and the comparison between arrays and linked lists. It highlights the advantages and limitations of recursion, and presents the Trie data structure as the best choice for dictionary applications due to its fast lookup capabilities. Additionally, it briefly mentions an alternative data structure, the hash map, for quick lookups.

Uploaded by

shreyabg890
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Computer Science Concepts with C++ Examples

1. Importance of Asymptotic Notation in Algorithm Efficiency

Asymptotic notation helps in analyzing how an algorithm performs as the input grows. It focuses on the

dominant term, giving us a scalable view of performance.

Examples in C++:

O(1) - Constant time:

int getFirstElement(const std::vector<int>& arr) {

return arr[0];

O(n) - Linear time:

int findElement(const std::vector<int>& arr, int target) {

for (int i : arr) {

if (i == target) return i;

return -1;

O(n^2) - Quadratic time (e.g., bubble sort):

void bubbleSort(std::vector<int>& arr) {

for (int i = 0; i < arr.size(); ++i) {

for (int j = 0; j < arr.size() - i - 1; ++j) {

if (arr[j] > arr[j + 1])

std::swap(arr[j], arr[j + 1]);

}
Computer Science Concepts with C++ Examples

2a. Recursion in Computer Science

Definition: Recursion is when a function calls itself to break a problem into smaller parts.

Advantages:

- Cleaner code for problems like tree traversal, factorial, etc.

Limitations:

- Stack overflows for large inputs.

- Can be slower due to repeated calls.

C++ Example: Factorial

int factorial(int n) {

if (n == 0) return 1;

return n * factorial(n - 1);

2b. Arrays vs. Linked Lists

Comparison Table:

Arrays:

- Fixed-size, contiguous memory

- O(1) access time

- Insertion/Deletion can be O(n)

Linked Lists:

- Dynamic-size, non-contiguous memory

- Slower access (O(n))

- Fast insertion/deletion at head (O(1))


Computer Science Concepts with C++ Examples

C++ Array Example:

int arr[5] = {1, 2, 3, 4, 5};

std::cout << arr[2]; // O(1) access

C++ Singly Linked List Node:

struct Node {

int data;

Node* next;

};

void insertAtHead(Node*& head, int val) {

Node* newNode = new Node{val, head};

head = newNode;

3. Best Data Structure for a Dictionary Application

Best Choice: Trie (Prefix Tree)

Why Trie?

- Fast lookup (O(L))

- Good for autocomplete/prefix search

- Efficient storage for words with common prefixes

C++ Trie Example:

struct TrieNode {

TrieNode* children[26];

bool isEndOfWord;

TrieNode() {
Computer Science Concepts with C++ Examples

isEndOfWord = false;

for (auto &child : children)

child = nullptr;

};

class Trie {

public:

TrieNode* root;

Trie() { root = new TrieNode(); }

void insert(std::string word) {

TrieNode* node = root;

for (char ch : word) {

int index = ch - 'a';

if (!node->children[index])

node->children[index] = new TrieNode();

node = node->children[index];

node->isEndOfWord = true;

bool search(std::string word) {

TrieNode* node = root;

for (char ch : word) {

int index = ch - 'a';

if (!node->children[index])

return false;

node = node->children[index];

return node->isEndOfWord;

};
Computer Science Concepts with C++ Examples

Alternative: Hash Map (Quick Lookups)

#include <unordered_map>

std::unordered_map<std::string, std::string> dictionary;

dictionary["apple"] = "A fruit";

You might also like