🪴 BCs Computer Science

Search

SearchSearch

Learning goals

Apr 24, 202411 min read

W1 OOP & Abstract Data Structures

Readings: W1 Readings

  1. Understand the principles of ==Encapsulation, inheritance, and polymorphism== in object-oriented programming and how they can be used to create abstract data types (ADT’s)
  2. Be able to design and implement a class that represents an ADT using object-oriented programming principles
  3. Be able to use interfaces to define the behavior of an ADT and implement it using different classes
  4. Understand the difference between an ADT and a concrete implementation of that ADT
Lists:
  1. Understand the concept of a linear data structure and the differences between arrays and linked lists
  2. Be able to implement a basic singly linked list in Java
  3. Understand the limitations of array-based lists and linked-lists
  4. Understand the time and space complexities of basic operations on a singly linked list, such as insert, delete, and search
  5. Understand the concept of a doubly linked list and the time and space complexities of basic operations on a doubly linked list
Stacks and Queues:
  1. Understand the concept of a stack and a queue and the differences between them
  2. Be able to implement a basic stack and a basic queue in Java
  3. Understand the time and space complexities of basic operations on a stack and a queue, such as push, pop, and peek
  4. Understand the use cases of stacks and queues in real-world scenarios
Sets:
  1. Understand the concept of a set and the differences between sets and lists
  2. Be able to implement a basic set in Java using an array
  3. Understand the time and space complexities of basic operations on a set, such as insert, delete, and search
  4. Understand the use cases of sets in real-world scenarios
Recursion:
  1. Understand the concept of recursion and how it differs from iteration
  2. Be able to write and trace recursive functions in Java
  3. Understand the time and space complexities of recursive functions and how to analyse them
  4. Understand the use cases of recursion in real-world scenarios and be able to identify when a problem can be solved using recursion.

W2 Hashing & Algorithm Analisys

Readings: W2 Readings

Hashing
  1. Understand the Dictionary ADT, when it is appropriate and its use-cases.
  2. Understand the basic concepts of hashing and hash tables, including the hash function, collisions, and load factor.
    1. Be able to explain the advantages and disadvantages of using hash tables over other data structures.
    2. Be able to implement a basic hash table in Java, including the ability to add, remove, and search for elements.
    3. Understand the different collision resolution techniques (e.g. chaining, open addressing) and be able to implement them in Java.
    4. Understand the time and space complexity of hash tables and be able to analyze the performance of a given implementation.
    5. Understand the trade-offs involved in choosing a hash function and be able to implement a good hash function for a specific use case.
    6. Be able to implement a hash table in a real-world application.
Algorithm Analysis
  1. Understand the basic concepts of algorithm analysis, including big-O notation and time complexity.
  2. Be able to determine the time complexity of a given algorithm using big-O notation and the counting of instructions
  3. Understand the common complexity classes (e.g. O(1), O(log n), O(n), O(n log n), O(n2), O(2n)) and be able to classify a given algorithm into one of these classes.
  4. Be able to analyze the time and space complexity of a given algorithm and determine its efficiency.
  5. Understand the concept of worst-case, average-case and best-case analysis and be able to analyze an algorithm’s time complexity for each case.
  6. Understand the trade-offs between time and space complexity and be able to determine the optimal solution for a given problem based on the available resources.

W3 Trees

Readings: W3 Readings

Trees
  1. Understand the concept of a tree data structure and its basic properties such as the root, parent, and children nodes
  2. Understand the difference between a tree and a graph
  3. Understand the different types of trees, such as binary trees, binary search trees, balanced binary trees, general trees, and their specific properties and use cases
  4. Be able to implement a basic binary tree in Java
  5. Understand the time and space complexities of basic operations on a binary tree, such as insert, delete, and search
  6. Understand the concept of a binary search tree and its properties, including the relationship between the value of nodes and their position in the tree
  7. Understand the concept of balanced binary trees and how they can be used to improve the performance of a binary search tree
  8. Understand the concept of a general tree and its properties, including the relationship between the value of nodes and their position in the tree
  9. Understand the implementation of trees, such as array-based and pointer-based implementation
  10. Understand the use cases of trees in real-world scenarios and be able to identify when a problem can be solved using a tree data structure.

W4 Sorting Algorithms

Readings: W4 Readings

  1. Understand the basic concepts of sorting algorithms, including stability, in-place sorting, and comparison-based sorting.
  2. Be able to explain the advantages and disadvantages of various sorting algorithms, such as O(n2) algorithms and O(n log n) algorithms.
  3. Be able to implement common sorting algorithms in Java, such as Bubble sort, insertion sort, selection sort, merge sort, quick sort, and radix sort.
  4. Understand the time and space complexity of sorting algorithms and be able to analyse the performance of a given implementation.
  5. Understand the concept of in-place sorting and be able to implement a sorting algorithm.
  6. Understand the trade-offs between different sorting algorithms and be able to choose the appropriate algorithm for a given problem based on factors such as time complexity, space complexity, and stability.
  7. Understand the concept of sorting in linear time and be able to implement algorithms such as counting sort, bucket sort, and radix sort.
  8. Understand the concept of sorting with limited memory and be able to implement external sorting algorithms such as merge sort and multi-way merge sort.
  9. Understand the use of sorting in various applications, such as in databases and search algorithms.
  10. Be able to implement a sorting algorithm in a real-world application and explain its performance.

W5 Graphs and Graph Traversal

Readings: W5 Readings

Graph data structure
  1. Understand the concept of a graph data structure and its basic properties such as vertices, edges, and the relationship between them
  2. Understand the different types of graphs, such as directed and undirected, weighted and unweighted, and their specific properties and use cases
  3. Understand the different representations of graphs, such as adjacency matrix and adjacency list, and their time and space complexities
  4. Be able to implement basic graph operations in Java, such as adding and removing vertices and edges, traversing the graph, and finding the shortest path
Graph traversal algorithms
  1. Understand the concept of graph traversal algorithms, such as depth-first search and breadth-first search, and their time and space complexities
    1. Depth-first search
    2. Breadth-first search
  2. Understand the concept of shortest path algorithms, such as Dijkstra’s Algorithm, and their time and space complexities
  3. Understand the use cases of graphs in real-world scenarios, such as networking, routing, and data analysis and be able to identify when a problem can be solved using a graph data structure
Graph theory
  1. Understand the concept of graph theory and it’s relation to computer science and data structures

W6 Tries, String Algorithms & Algorithmic Methods

Readings: W6 Readings

Tries
  1. Understand the basic concepts of trees and be able to explain its use in data structures and algorithms.
  2. Be able to implement a basic trie in Java and understand its time and space complexity.
  3. Understand the concepts of prefix tries and be able to implement them in Java. Understand their time and space complexity and how they improve over basic tries.
  4. Understand the compression of tries and how to implement this concept.
  5. Understand the use of tries in various fields such as natural language processing, computer science and bioinformatics.
  6. Be able to apply tries to solve real-world problems and explain their performance.
  7. Understand the basic concepts of Trie data structure and be able to explain the advantages and disadvantages of Trie data structure.
  8. Be able to implement various Trie operations such as insertion, deletion, search, and traversal in Java
  9. Understand the time and space complexity of Trie operations and be able to analyse the performance of a given implementation.
  10. Understand the use of Trie in various fields such as text completion, spell checking, IP routing, and DNA sequence analysis.
String Algorithms
  1. Understand the basic concepts of pattern matching algorithms and be able to explain the advantages and disadvantages of different pattern matching techniques.
  2. Be able to implement the brute-force pattern matching algorithm in Java and understand its time and space complexity.
  3. Understand the concepts of the KMP algorithm and be able to implement it in Java. Understand its time and space complexity and how it improves over the brute force algorithm.
  4. Understand the concepts of the Boyer-Moore algorithm and be able to implement it in Java. Understand its time and space complexity and how it improves over the KMP algorithm.
  5. Understand the use of pattern matching algorithms in various fields such as natural language processing, computer science and bioinformatics.
  6. Be able to apply pattern matching algorithms to solve real-world problems and explain their performance.
  7. Understand the basic concepts of string matching algorithm and be able to explain the advantages and disadvantages of different string matching techniques.
  8. Understand the time and space complexity of string matching algorithms and be able to analyse the performance of a given implementation.
Algorithmic Methods
  1. Understand the basic concepts of greedy algorithms and be able to explain the advantages and disadvantages of using greedy algorithms over other problem-solving techniques.
  2. Understand the time and space complexity of greedy algorithms and be able to analyse the performance of a given implementation.
  3. Understand the concept of a greedy choice and be able to identify it in a problem and apply it to solve it.
  4. Understand the concept of optimal substructure and be able to identify it in a problem and apply it to solve it.
  5. Understand the concept of greedy versus dynamic programming and be able to choose between them based on the problem statement.
  6. Be able to implement a greedy algorithm in a real-world application and explain its performance.
  7. Understand the basic concepts of divide-and-conquer and be able to explain the advantages and disadvantages of using divide-and-conquer over other problem-solving techniques.
  8. Understand the time and space complexity of divide-and-conquer algorithms and be able to analyze the performance of a given implementation.
  9. Understand the concept of breaking down a problem into smaller subproblems and be able to apply it to solve a problem.
  10. Understand the concept of recursion and how it is used in divide-and-conquer algorithms.
  11. Understand the concept of merge step and be able to implement it in divide-and-conquer algorithms such as merge sort.
  12. Understand the concept of base case and be able to identify it and implement it in divide-and-conquer algorithms.
  13. Be able to implement a divide-and-conquer algorithm in a real-world application and explain its performance.
  14. Understand the basic concepts of dynamic programming and be able to explain the advantages and disadvantages of using dynamic programming over other problem-solving techniques.
  15. Understand the time and space complexity of dynamic programming algorithms and be able to analyse the performance of a given implementation.
  16. Understand the concept of overlapping subproblems and be able to identify it in a problem and apply dynamic programming to solve it.
  17. Understand the concept of optimal substructure and be able to identify it in a problem and apply dynamic programming to solve it.
  18. Understand the concept of memoization and be able to implement it in dynamic programming algorithms.
  19. Understand the concept of tabulation and be able to implement it in dynamic programming algorithms
  20. Understand the use of dynamic programming in various fields such as operations research, computer science, and mathematics.
  21. Be able to implement a dynamic programming algorithm in a real-world application and explain its performance.

Graph View

Backlinks