CS502 Computational Complexity
CS502 Computational Complexity
Syllabus | International University of Sarajevo - Last Update on Mar 03, 2026
Syllabus Quick Jump
Search and navigate to any syllabus instantly
Computer Sciences and Engineering
Course Objectives
Computational Complexity course will cover important concepts from computability and complexity theories such as languages, computation models, decidability problems, P and NP problems, techniques for designing efficient algorithms for complex problems as well as approximation and randomized algorithms when problems are computationally intractable.
Learning Outcomes
After successful completion of the course, the student will be able to:
Course Materials
Required Textbook
1. Michael Sipser (2013) Introduction to the Theory of Computation, 3Ed, Cengage Learning, ISBN 978-1-133-18779-0 2. Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein (2009) Introduction to Algorithms, 3Ed, MIT Press, ISBN 978-0-262-03384-8
Additional Literature
Teaching Methods
Class lecturing and discussions with examples
Active practical sessions for engaged learning and continuous feedback on progress
Home assignments for analyzing the obtained knowledge in the classes
Programming assignments and projects for applying obtained experience in the classes for real-life problems
Weekly Topics
| Week | Topic | Readings / References |
|---|---|---|
| 1 | Languages and Computability: Countability, Computability, Functions and Languages | Sipser Chapters 0, 1 |
| 2 | Turing Machines: Formal Description, Configuration and Computation, Examples | Sipser Chapter 3.1 |
| 3 | Church-Turing Thesis: Variation of Turing Machines, RAM Model, Equivalence | Sipser Chapter 3.2 |
| 4 | Universality: Encoding, Universal Turing Machines, Recognizability and Decidability | Sipser Chapter 3.3 |
| 5 | Undecidability: Diagonalization, Mapping Reduction, Halting Problem, Rice Theorem | Sipser Chapters 4. 5 |
| 6 | P and NP: Asypmtotic Analysis, P-Class, Nondeterministic Turing Machines, NP-Class | Sipser Chapters 7.1-7.3 |
| 7 | NP-Completeness I: The Hardest Problems, Polynomial Reductions | Sipser Chapter 7.4 |
| 8 | Midterm Examination: Revision, Preparation, Exam | |
| 9 | NP-Completeness II: Independent Set, Vertex Cover, NP Completeness, Cook-Levin Theorem | Sipser Chapters 7.4, 7.5 |
| 10 | NP Complete Problems: 3CNF, INDSET, Subset Sum | Sipser Chapters 7.5, 7.6 |
| 11 | Dynamic Programming: Edit Distance Problem, Chain Matrix Multiplication, All Pairs Shortest Path | CLRS Chapter 15 |
| 12 | Fast Fourier Transform: Convolution, Multiplying Polynomials, Butterfly Network | CLRS Chapter 30 |
| 13 | Maximum Flow: Flow Networks, Residual Networks, Ford-Fulkerson, Edmonds-Karp Algorithms | CLRS Chapter 26 |
| 14 | Approximation Algorithms: Min Vertex Cover, Maximum Independent Set, TSP, Metric TSP | CLRS Chapter 35 |
| 15 | Randomized Algorithms: Verifying Polynomial Identities, Monte-Carlo vs. Las Vegas, Min-Cut | CLRS Chapter 35 |
Course Schedule (All Sections)
Office Hours & Room
Assessment Methods and Criteria
Assessment Components
Final Exam
AI: Not AllowedAlignment with Learning Outcomes : 1 2 4
Projects
AI: Not AllowedAlignment with Learning Outcomes : 3 5
Class assignments
AI: Not AllowedAlignment with Learning Outcomes : 1 2
Home assignments
AI: Not AllowedAlignment with Learning Outcomes : 2 4
IUS Grading System
| Grading Scale | IUS Grading System | IUS Coeff. | Letter (B&H) | Numerical (B&H) |
|---|---|---|---|---|
| 0 - 44 | F | 0 | F | 5 |
| 45 - 54 | E | 1 | ||
| 55 - 64 | C | 2 | E | 6 |
| 65 - 69 | C+ | 2.3 | D | 7 |
| 70 -74 | B- | 2.7 | ||
| 75 - 79 | B | 3 | C | 8 |
| 80 - 84 | B+ | 3.3 | ||
| 85 - 94 | A- | 3.7 | B | 9 |
| 95 - 100 | A | 4 | A | 10 |
Late Work Policy
Information about late submission policies will be shared during class and posted in this section. Please check back for official guidelines.
ECTS Credit Calculation
📚 Student Workload
This 6 ECTS credit course corresponds to 150 hours of total student workload, distributed as follows:
Lecture hours
45 hours ⏳ (15 week × 3 h)
Active tutorials
30 hours ⏳ (15 week × 2 h)
Home studies
30 hours ⏳ (15 week × 2 h)
In-term exam study
10 hours ⏳ (1 week × 10 h)
Final exam study
15 hours ⏳ (1 week × 15 h)
Home assignment study
20 hours ⏳ (10 week × 2 h)
150 Total Workload Hours
6 ECTS Credits
Course Policies
Academic Integrity
All work submitted must be your own. Plagiarism, cheating, or any form of academic dishonesty will result in disciplinary action according to university policies. When in doubt about citation practices, consult the instructor.
Attendance Policy
Students are expected to adhere to the attendance requirements as outlined in the International University of Sarajevo Study Rules and Regulations. Excessive absences, whether excused or unexcused, may impact academic performance and eligibility for assessment. Mandatory sessions (e.g., labs, workshops) require attendance unless formally exempted. For detailed policies on absences, documentation, and penalties, please refer to the official university regulations.
Technology & AI Policy
Laptops/tablets may be used for note-taking only during lectures. Phones should be silenced and put away during all class sessions. Audio/video recording requires prior permission from the instructor.
Artificial Intelligence (AI) Usage: The use of AI tools (e.g., ChatGPT, Copilot, Gemini) varies by assessment component. Please refer to the AI usage indicator next to each assessment item in the Assessment Methods and Criteria section above. Submitting AI-generated content as your own work, where AI is not explicitly allowed, constitutes an academic integrity violation.
Communication Policy
All course-related communication should occur through official university channels (institutional email or SIS). Emails should include [CS502] in the subject line.
Academic Quality Assurance Policy
Course Academic Quality Assurance is achieved through Semester Student Survey. At the end of each academic year, the institution of higher education is obliged to evaluate work of the academic staff, or the success of realization of the curricula.
Learning Tips
Be prepared to contribute thoughtfully during class discussions, labs, or collaborative work. Active participation deepens understanding and encourages critical thinking.
Complete assigned readings or prep materials before class. Take notes, highlight key ideas, and jot down questions. Aim to grasp core concepts and their applications—not just facts.
Use course frameworks or methodologies to analyze problems, case studies, or projects. Begin early to allow time for reflection and refinement. Seek feedback to improve your work.
Don’t hesitate to reach out when something is unclear. Use office hours, discussion boards, or peer networks to clarify concepts and stay on track.
Syllabus Last Updated on Mar 03, 2026 | International University of Sarajevo
Print Syllabus
Referencing Curricula Print this page
| Assessment Methods and Criteria | Evaluation Tool | Quantity | Weight | Alignment with LOs | AI Usage |
| Final Exam | 1 | 35 | 1,2,4 | Not Allowed | |
| Semester Evaluation Components | |||||
| Projects | 1 | 15 | 3,5 | Not Allowed | |
| Class assignments | 6 | 30 | 1,2 | Not Allowed | |
| Home assignments | 4 | 20 | 2,4 | Not Allowed | |
| *** ECTS Credit Calculation *** | |||||
| Activity | Hours | Weeks | Student Workload Hours | Activity | Hours | Weeks | Student Workload Hours | |||
| Lecture hours | 3 | 15 | 45 | Active tutorials | 2 | 15 | 30 | |||
| Home studies | 2 | 15 | 30 | In-term exam study | 10 | 1 | 10 | |||
| Final exam study | 15 | 1 | 15 | Home assignment study | 2 | 10 | 20 | |||
| Total Workload Hours = | 150 | |||||||||
| *T= Teaching, P= Practice | ECTS Credit = | 6 | ||||||||
| Course Academic Quality Assurance: Semester Student Survey | Last Update Date: 27/03/2026 | |||||||||