Business and technology qualifications, Levels 3-6, in Brussels. Explore qualifications
Portal login
Level 4 Diploma in Cyber Security

Problem classes: computability and Turing machines, P and NP, NP-completeness and NP-hardness, quantum computing and open problems

CYB404 · Algorithms and Data Structures — Week 4 of 16

CourseCYB404
Week4 of 16
SemesterII
TutorOnline in the course chat

This week’s topics

Problem classes: computability and Turing machines, P and NP, NP-completeness and NP-hardness, quantum computing and open problems

  1. The difference between P and NP
  2. Open problems in problem classification and the impacts of future technologies on the difficulty in solving different classes algorithms

What you will be able to do

  • 2.3 Explain the difference between P and NP.
  • 2.4 Evaluate open problems in problem classification and the impacts of future technologies on the difficulty in solving different classes algorithms.

Activity

Seminar, guided reading and a short written task: explain the difference between P and NP.

Study materials

The teaching notes, exercises and videos of this week are in the student portal. Your portal is set up as soon as you receive final acceptance, so you can open them before the semester starts.
Week 3Week 5
Course chat

Admitted students ask questions on this week’s page in the student portal: an AI assistant trained on the course answers first, and during the course’s timetabled classes Connect to your tutor brings your tutor into the chat, who may start a call if needed.

Open this week in the portal
Course plan
  • Week 1: Data structures: arrays, lists, stacks, queues, sets and di…
  • Week 2: Choosing data structures, with a Python refresher
  • Week 3: Measuring complexity: Big O notation
  • Week 4: Problem classes: computability and Turing machines, P and N…
  • Week 5: Recursion and memoisation (e.g. Tower of Hanoi); the memory…
  • Week 6: Algorithmic paradigms: divide and conquer, backtracking, gr…
  • Week 7: Sort, search and pathfinding algorithms compared by time an…
  • Midterm: Midterm evaluation
  • Week 9: Writing pseudocode as a universal template for algorithms
  • Week 10: Checking algorithms are correct: tracing, testing and timing
  • Week 11: Debugging and testing implementations; review and practice …
  • Week 12: Applying Algorithms and Data Structures in practice: case s…
  • Week 13: Assignment workshop: research, planning and referencing
  • Week 14: Assignment workshop: drafting, feedback and improvement
  • Week 15: Review and coursework completion
  • Final: Final assessment and submission
Back to the course
Scroll